LCOV - code coverage report
Current view: top level - gcc - store-motion.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 482 517 93.2 %
Date: 2020-03-28 11:57:23 Functions: 25 27 92.6 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Store motion via Lazy Code Motion on the reverse CFG.
       2                 :            :    Copyright (C) 1997-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify it under
       7                 :            : the terms of the GNU General Public License as published by the Free
       8                 :            : Software Foundation; either version 3, or (at your option) any later
       9                 :            : version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "backend.h"
      24                 :            : #include "rtl.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "predict.h"
      27                 :            : #include "df.h"
      28                 :            : #include "toplev.h"
      29                 :            : 
      30                 :            : #include "cfgrtl.h"
      31                 :            : #include "cfganal.h"
      32                 :            : #include "lcm.h"
      33                 :            : #include "cfgcleanup.h"
      34                 :            : #include "expr.h"
      35                 :            : #include "tree-pass.h"
      36                 :            : #include "dbgcnt.h"
      37                 :            : #include "rtl-iter.h"
      38                 :            : #include "print-rtl.h"
      39                 :            : 
      40                 :            : /* This pass implements downward store motion.
      41                 :            :    As of May 1, 2009, the pass is not enabled by default on any target,
      42                 :            :    but bootstrap completes on ia64 and x86_64 with the pass enabled.  */
      43                 :            : 
      44                 :            : /* TODO:
      45                 :            :    - remove_reachable_equiv_notes is an incomprehensible pile of goo and
      46                 :            :      a compile time hog that needs a rewrite (maybe cache st_exprs to
      47                 :            :      invalidate REG_EQUAL/REG_EQUIV notes for?).
      48                 :            :    - pattern_regs in st_expr should be a regset (on its own obstack).
      49                 :            :    - store_motion_mems should be a vec instead of a list.
      50                 :            :    - there should be an alloc pool for struct st_expr objects.
      51                 :            :    - investigate whether it is helpful to make the address of an st_expr
      52                 :            :      a cselib VALUE.
      53                 :            :    - when GIMPLE alias information is exported, the effectiveness of this
      54                 :            :      pass should be re-evaluated.
      55                 :            : */
      56                 :            : 
      57                 :            : /* This is a list of store expressions (MEMs).  The structure is used
      58                 :            :    as an expression table to track stores which look interesting, and
      59                 :            :    might be moveable towards the exit block.  */
      60                 :            : 
      61                 :            : struct st_expr
      62                 :            : {
      63                 :            :   /* Pattern of this mem.  */
      64                 :            :   rtx pattern;
      65                 :            :   /* List of registers mentioned by the mem.  */
      66                 :            :   vec<rtx> pattern_regs;
      67                 :            :   /* INSN list of stores that are locally anticipatable.  */
      68                 :            :   vec<rtx_insn *> antic_stores;
      69                 :            :   /* INSN list of stores that are locally available.  */
      70                 :            :   vec<rtx_insn *> avail_stores;
      71                 :            :   /* Next in the list.  */
      72                 :            :   struct st_expr * next;
      73                 :            :   /* Store ID in the dataflow bitmaps.  */
      74                 :            :   int index;
      75                 :            :   /* Hash value for the hash table.  */
      76                 :            :   unsigned int hash_index;
      77                 :            :   /* Register holding the stored expression when a store is moved.
      78                 :            :      This field is also used as a cache in find_moveable_store, see
      79                 :            :      LAST_AVAIL_CHECK_FAILURE below.  */
      80                 :            :   rtx reaching_reg;
      81                 :            : };
      82                 :            : 
      83                 :            : /* Head of the list of load/store memory refs.  */
      84                 :            : static struct st_expr * store_motion_mems = NULL;
      85                 :            : 
      86                 :            : /* These bitmaps will hold the local dataflow properties per basic block.  */
      87                 :            : static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
      88                 :            : 
      89                 :            : /* Nonzero for expressions which should be inserted on a specific edge.  */
      90                 :            : static sbitmap *st_insert_map;
      91                 :            : 
      92                 :            : /* Nonzero for expressions which should be deleted in a specific block.  */
      93                 :            : static sbitmap *st_delete_map;
      94                 :            : 
      95                 :            : /* Global holding the number of store expressions we are dealing with.  */
      96                 :            : static int num_stores;
      97                 :            : 
      98                 :            : /* Contains the edge_list returned by pre_edge_lcm.  */
      99                 :            : static struct edge_list *edge_list;
     100                 :            : 
     101                 :            : /* Hashtable helpers.  */
     102                 :            : 
     103                 :            : struct st_expr_hasher : nofree_ptr_hash <st_expr>
     104                 :            : {
     105                 :            :   static inline hashval_t hash (const st_expr *);
     106                 :            :   static inline bool equal (const st_expr *, const st_expr *);
     107                 :            : };
     108                 :            : 
     109                 :            : inline hashval_t
     110                 :        333 : st_expr_hasher::hash (const st_expr *x)
     111                 :            : {
     112                 :        333 :   int do_not_record_p = 0;
     113                 :        333 :   return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
     114                 :            : }
     115                 :            : 
     116                 :            : inline bool
     117                 :        345 : st_expr_hasher::equal (const st_expr *ptr1, const st_expr *ptr2)
     118                 :            : {
     119                 :        345 :   return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
     120                 :            : }
     121                 :            : 
     122                 :            : /* Hashtable for the load/store memory refs.  */
     123                 :            : static hash_table<st_expr_hasher> *store_motion_mems_table;
     124                 :            : 
     125                 :            : /* This will search the st_expr list for a matching expression. If it
     126                 :            :    doesn't find one, we create one and initialize it.  */
     127                 :            : 
     128                 :            : static struct st_expr *
     129                 :        118 : st_expr_entry (rtx x)
     130                 :            : {
     131                 :        118 :   int do_not_record_p = 0;
     132                 :        118 :   struct st_expr * ptr;
     133                 :        118 :   unsigned int hash;
     134                 :        118 :   st_expr **slot;
     135                 :        118 :   struct st_expr e;
     136                 :            : 
     137                 :        118 :   hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
     138                 :            :                    NULL,  /*have_reg_qty=*/false);
     139                 :            : 
     140                 :        118 :   e.pattern = x;
     141                 :        118 :   slot = store_motion_mems_table->find_slot_with_hash (&e, hash, INSERT);
     142                 :        118 :   if (*slot)
     143                 :            :     return *slot;
     144                 :            : 
     145                 :        113 :   ptr = XNEW (struct st_expr);
     146                 :            : 
     147                 :        113 :   ptr->next         = store_motion_mems;
     148                 :        113 :   ptr->pattern      = x;
     149                 :        113 :   ptr->pattern_regs.create (0);
     150                 :        113 :   ptr->antic_stores.create (0);
     151                 :        113 :   ptr->avail_stores.create (0);
     152                 :        113 :   ptr->reaching_reg = NULL_RTX;
     153                 :        113 :   ptr->index        = 0;
     154                 :        113 :   ptr->hash_index   = hash;
     155                 :        113 :   store_motion_mems = ptr;
     156                 :        113 :   *slot = ptr;
     157                 :            : 
     158                 :        113 :   return ptr;
     159                 :            : }
     160                 :            : 
     161                 :            : /* Free up an individual st_expr entry.  */
     162                 :            : 
     163                 :            : static void
     164                 :        113 : free_st_expr_entry (struct st_expr * ptr)
     165                 :            : {
     166                 :        113 :   ptr->antic_stores.release ();
     167                 :        113 :   ptr->avail_stores.release ();
     168                 :        113 :   ptr->pattern_regs.release ();
     169                 :            : 
     170                 :        113 :   free (ptr);
     171                 :        113 : }
     172                 :            : 
     173                 :            : /* Free up all memory associated with the st_expr list.  */
     174                 :            : 
     175                 :            : static void
     176                 :         21 : free_store_motion_mems (void)
     177                 :            : {
     178                 :         21 :   delete store_motion_mems_table;
     179                 :         21 :   store_motion_mems_table = NULL;
     180                 :            : 
     181                 :        115 :   while (store_motion_mems)
     182                 :            :     {
     183                 :         94 :       struct st_expr * tmp = store_motion_mems;
     184                 :         94 :       store_motion_mems = store_motion_mems->next;
     185                 :         94 :       free_st_expr_entry (tmp);
     186                 :            :     }
     187                 :         21 :   store_motion_mems = NULL;
     188                 :         21 : }
     189                 :            : 
     190                 :            : /* Assign each element of the list of mems a monotonically increasing value.  */
     191                 :            : 
     192                 :            : static int
     193                 :         46 : enumerate_store_motion_mems (void)
     194                 :            : {
     195                 :         46 :   struct st_expr * ptr;
     196                 :         46 :   int n = 0;
     197                 :            : 
     198                 :        140 :   for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
     199                 :         94 :     ptr->index = n++;
     200                 :            : 
     201                 :         46 :   return n;
     202                 :            : }
     203                 :            : 
     204                 :            : /* Return first item in the list.  */
     205                 :            : 
     206                 :            : static inline struct st_expr *
     207                 :        308 : first_st_expr (void)
     208                 :            : {
     209                 :        308 :   return store_motion_mems;
     210                 :            : }
     211                 :            : 
     212                 :            : /* Return the next item in the list after the specified one.  */
     213                 :            : 
     214                 :            : static inline struct st_expr *
     215                 :       1584 : next_st_expr (struct st_expr * ptr)
     216                 :            : {
     217                 :       1584 :   return ptr->next;
     218                 :            : }
     219                 :            : 
     220                 :            : /* Dump debugging info about the store_motion_mems list.  */
     221                 :            : 
     222                 :            : static void
     223                 :          2 : print_store_motion_mems (FILE * file)
     224                 :            : {
     225                 :          2 :   struct st_expr * ptr;
     226                 :            : 
     227                 :          2 :   fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
     228                 :            : 
     229                 :          3 :   for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
     230                 :            :     {
     231                 :          1 :       fprintf (file, "  Pattern (%3d): ", ptr->index);
     232                 :            : 
     233                 :          1 :       print_rtl (file, ptr->pattern);
     234                 :            : 
     235                 :          1 :       fprintf (file, "\n    ANTIC stores : ");
     236                 :          1 :       print_rtx_insn_vec (file, ptr->antic_stores);
     237                 :            : 
     238                 :          1 :       fprintf (file, "\n    AVAIL stores : ");
     239                 :            : 
     240                 :          1 :         print_rtx_insn_vec (file, ptr->avail_stores);
     241                 :            : 
     242                 :          1 :       fprintf (file, "\n\n");
     243                 :            :     }
     244                 :            : 
     245                 :          2 :   fprintf (file, "\n");
     246                 :          2 : }
     247                 :            : 
     248                 :            : /* Return zero if some of the registers in list X are killed
     249                 :            :    due to set of registers in bitmap REGS_SET.  */
     250                 :            : 
     251                 :            : static bool
     252                 :        895 : store_ops_ok (const vec<rtx> &x, int *regs_set)
     253                 :            : {
     254                 :        895 :   unsigned int i;
     255                 :        895 :   rtx temp;
     256                 :       1550 :   FOR_EACH_VEC_ELT (x, i, temp)
     257                 :        680 :     if (regs_set[REGNO (temp)])
     258                 :            :       return false;
     259                 :            : 
     260                 :            :   return true;
     261                 :            : }
     262                 :            : 
     263                 :            : /* Returns a list of registers mentioned in X.
     264                 :            :    FIXME: A regset would be prettier and less expensive.  */
     265                 :            : 
     266                 :            : static void
     267                 :        113 : extract_mentioned_regs (rtx x, vec<rtx> *mentioned_regs)
     268                 :            : {
     269                 :        113 :   subrtx_var_iterator::array_type array;
     270                 :        493 :   FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
     271                 :            :     {
     272                 :        380 :       rtx x = *iter;
     273                 :        380 :       if (REG_P (x))
     274                 :         90 :         mentioned_regs->safe_push (x);
     275                 :            :     }
     276                 :        113 : }
     277                 :            : 
     278                 :            : /* Check to see if the load X is aliased with STORE_PATTERN.
     279                 :            :    AFTER is true if we are checking the case when STORE_PATTERN occurs
     280                 :            :    after the X.  */
     281                 :            : 
     282                 :            : static bool
     283                 :        462 : load_kills_store (const_rtx x, const_rtx store_pattern, int after)
     284                 :            : {
     285                 :        462 :   if (after)
     286                 :         58 :     return anti_dependence (x, store_pattern);
     287                 :            :   else
     288                 :        404 :     return true_dependence (store_pattern, GET_MODE (store_pattern), x);
     289                 :            : }
     290                 :            : 
     291                 :            : /* Go through the entire rtx X, looking for any loads which might alias
     292                 :            :    STORE_PATTERN.  Return true if found.
     293                 :            :    AFTER is true if we are checking the case when STORE_PATTERN occurs
     294                 :            :    after the insn X.  */
     295                 :            : 
     296                 :            : static bool
     297                 :       9751 : find_loads (const_rtx x, const_rtx store_pattern, int after)
     298                 :            : {
     299                 :       9751 :   const char * fmt;
     300                 :       9751 :   int i, j;
     301                 :       9751 :   int ret = false;
     302                 :            : 
     303                 :       9751 :   if (!x)
     304                 :            :     return false;
     305                 :            : 
     306                 :       9751 :   if (GET_CODE (x) == SET)
     307                 :       3546 :     x = SET_SRC (x);
     308                 :            : 
     309                 :       9751 :   if (MEM_P (x))
     310                 :            :     {
     311                 :        462 :       if (load_kills_store (x, store_pattern, after))
     312                 :            :         return true;
     313                 :            :     }
     314                 :            : 
     315                 :            :   /* Recursively process the insn.  */
     316                 :       9652 :   fmt = GET_RTX_FORMAT (GET_CODE (x));
     317                 :            : 
     318                 :      22029 :   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
     319                 :            :     {
     320                 :      12377 :       if (fmt[i] == 'e')
     321                 :       5499 :         ret |= find_loads (XEXP (x, i), store_pattern, after);
     322                 :       6878 :       else if (fmt[i] == 'E')
     323                 :         48 :         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
     324                 :         24 :           ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
     325                 :            :     }
     326                 :            :   return ret;
     327                 :            : }
     328                 :            : 
     329                 :            : /* Go through pattern PAT looking for any loads which might kill the
     330                 :            :    store in X.  Return true if found.
     331                 :            :    AFTER is true if we are checking the case when loads kill X occurs
     332                 :            :    after the insn for PAT.  */
     333                 :            : 
     334                 :            : static inline bool
     335                 :       4128 : store_killed_in_pat (const_rtx x, const_rtx pat, int after)
     336                 :            : {
     337                 :       4128 :   if (GET_CODE (pat) == SET)
     338                 :            :     {
     339                 :       3560 :       rtx dest = SET_DEST (pat);
     340                 :            : 
     341                 :       3560 :       if (GET_CODE (dest) == ZERO_EXTRACT)
     342                 :          0 :         dest = XEXP (dest, 0);
     343                 :            : 
     344                 :            :       /* Check for memory stores to aliased objects.  */
     345                 :       3560 :       if (MEM_P (dest)
     346                 :       3560 :           && !exp_equiv_p (dest, x, 0, true))
     347                 :            :         {
     348                 :       1228 :           if (after)
     349                 :            :             {
     350                 :        184 :               if (output_dependence (dest, x))
     351                 :            :                 return true;
     352                 :            :             }
     353                 :            :           else
     354                 :            :             {
     355                 :       1044 :               if (output_dependence (x, dest))
     356                 :            :                 return true;
     357                 :            :             }
     358                 :            :         }
     359                 :            :     }
     360                 :            : 
     361                 :       4114 :   if (find_loads (pat, x, after))
     362                 :         94 :     return true;
     363                 :            : 
     364                 :            :   return false;
     365                 :            : }
     366                 :            : 
     367                 :            : /* Check if INSN kills the store pattern X (is aliased with it).
     368                 :            :    AFTER is true if we are checking the case when store X occurs
     369                 :            :    after the insn.  Return true if it does.  */
     370                 :            : 
     371                 :            : static bool
     372                 :       4670 : store_killed_in_insn (const_rtx x, const vec<rtx> &x_regs,
     373                 :            :                       const rtx_insn *insn, int after)
     374                 :            : {
     375                 :       4670 :   const_rtx note, pat;
     376                 :            : 
     377                 :       4670 :   if (! NONDEBUG_INSN_P (insn))
     378                 :            :     return false;
     379                 :            : 
     380                 :       3579 :   if (CALL_P (insn))
     381                 :            :     {
     382                 :            :       /* A normal or pure call might read from pattern,
     383                 :            :          but a const call will not.  */
     384                 :         23 :       if (!RTL_CONST_CALL_P (insn))
     385                 :            :         return true;
     386                 :            : 
     387                 :            :       /* But even a const call reads its parameters.  Check whether the
     388                 :            :          base of some of registers used in mem is stack pointer.  */
     389                 :            :       rtx temp;
     390                 :            :       unsigned int i;
     391                 :          0 :       FOR_EACH_VEC_ELT (x_regs, i, temp)
     392                 :          0 :         if (may_be_sp_based_p (temp))
     393                 :            :           return true;
     394                 :            : 
     395                 :            :       return false;
     396                 :            :     }
     397                 :            : 
     398                 :       3556 :   pat = PATTERN (insn);
     399                 :       3556 :   if (GET_CODE (pat) == SET)
     400                 :            :     {
     401                 :       2984 :       if (store_killed_in_pat (x, pat, after))
     402                 :            :         return true;
     403                 :            :     }
     404                 :        572 :   else if (GET_CODE (pat) == PARALLEL)
     405                 :            :     {
     406                 :            :       int i;
     407                 :            : 
     408                 :       1712 :       for (i = 0; i < XVECLEN (pat, 0); i++)
     409                 :       1144 :         if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
     410                 :            :           return true;
     411                 :            :     }
     412                 :          2 :   else if (find_loads (PATTERN (insn), x, after))
     413                 :            :     return true;
     414                 :            : 
     415                 :            :   /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
     416                 :            :      location aliased with X, then this insn kills X.  */
     417                 :       3448 :   note = find_reg_equal_equiv_note (insn);
     418                 :       3448 :   if (! note)
     419                 :            :     return false;
     420                 :        112 :   note = XEXP (note, 0);
     421                 :            : 
     422                 :            :   /* However, if the note represents a must alias rather than a may
     423                 :            :      alias relationship, then it does not kill X.  */
     424                 :        112 :   if (exp_equiv_p (note, x, 0, true))
     425                 :            :     return false;
     426                 :            : 
     427                 :            :   /* See if there are any aliased loads in the note.  */
     428                 :        112 :   return find_loads (note, x, after);
     429                 :            : }
     430                 :            : 
     431                 :            : /* Returns true if the expression X is loaded or clobbered on or after INSN
     432                 :            :    within basic block BB.  REGS_SET_AFTER is bitmap of registers set in
     433                 :            :    or after the insn.  X_REGS is list of registers mentioned in X. If the store
     434                 :            :    is killed, return the last insn in that it occurs in FAIL_INSN.  */
     435                 :            : 
     436                 :            : static bool
     437                 :        777 : store_killed_after (const_rtx x, const vec<rtx> &x_regs,
     438                 :            :                     const rtx_insn *insn, const_basic_block bb,
     439                 :            :                     int *regs_set_after, rtx *fail_insn)
     440                 :            : {
     441                 :        777 :   rtx_insn *last = BB_END (bb), *act;
     442                 :            : 
     443                 :       1554 :   if (!store_ops_ok (x_regs, regs_set_after))
     444                 :            :     {
     445                 :            :       /* We do not know where it will happen.  */
     446                 :         16 :       if (fail_insn)
     447                 :          0 :         *fail_insn = NULL_RTX;
     448                 :         16 :       return true;
     449                 :            :     }
     450                 :            : 
     451                 :            :   /* Scan from the end, so that fail_insn is determined correctly.  */
     452                 :       4739 :   for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
     453                 :       4098 :     if (store_killed_in_insn (x, x_regs, act, false))
     454                 :            :       {
     455                 :        120 :         if (fail_insn)
     456                 :         19 :           *fail_insn = act;
     457                 :        120 :         return true;
     458                 :            :       }
     459                 :            : 
     460                 :            :   return false;
     461                 :            : }
     462                 :            : 
     463                 :            : /* Returns true if the expression X is loaded or clobbered on or before INSN
     464                 :            :    within basic block BB. X_REGS is list of registers mentioned in X.
     465                 :            :    REGS_SET_BEFORE is bitmap of registers set before or in this insn.  */
     466                 :            : static bool
     467                 :        118 : store_killed_before (const_rtx x, const vec<rtx> &x_regs,
     468                 :            :                      const rtx_insn *insn, const_basic_block bb,
     469                 :            :                      int *regs_set_before)
     470                 :            : {
     471                 :        118 :   rtx_insn *first = BB_HEAD (bb);
     472                 :            : 
     473                 :        236 :   if (!store_ops_ok (x_regs, regs_set_before))
     474                 :            :     return true;
     475                 :            : 
     476                 :       1221 :   for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
     477                 :        572 :     if (store_killed_in_insn (x, x_regs, insn, true))
     478                 :            :       return true;
     479                 :            : 
     480                 :            :   return false;
     481                 :            : }
     482                 :            : 
     483                 :            : /* The last insn in the basic block that compute_store_table is processing,
     484                 :            :    where store_killed_after is true for X.
     485                 :            :    Since we go through the basic block from BB_END to BB_HEAD, this is
     486                 :            :    also the available store at the end of the basic block.  Therefore
     487                 :            :    this is in effect a cache, to avoid calling store_killed_after for
     488                 :            :    equivalent aliasing store expressions.
     489                 :            :    This value is only meaningful during the computation of the store
     490                 :            :    table.  We hi-jack the REACHING_REG field of struct st_expr to save
     491                 :            :    a bit of memory.  */
     492                 :            : #define LAST_AVAIL_CHECK_FAILURE(x)     ((x)->reaching_reg)
     493                 :            : 
     494                 :            : /* Determine whether INSN is MEM store pattern that we will consider moving.
     495                 :            :    REGS_SET_BEFORE is bitmap of registers set before (and including) the
     496                 :            :    current insn, REGS_SET_AFTER is bitmap of registers set after (and
     497                 :            :    including) the insn in this basic block.  We must be passing through BB from
     498                 :            :    head to end, as we are using this fact to speed things up.
     499                 :            : 
     500                 :            :    The results are stored this way:
     501                 :            : 
     502                 :            :    -- the first anticipatable expression is added into ANTIC_STORES
     503                 :            :    -- if the processed expression is not anticipatable, NULL_RTX is added
     504                 :            :       there instead, so that we can use it as indicator that no further
     505                 :            :       expression of this type may be anticipatable
     506                 :            :    -- if the expression is available, it is added as head of AVAIL_STORES;
     507                 :            :       consequently, all of them but this head are dead and may be deleted.
     508                 :            :    -- if the expression is not available, the insn due to that it fails to be
     509                 :            :       available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
     510                 :            : 
     511                 :            :    The things are complicated a bit by fact that there already may be stores
     512                 :            :    to the same MEM from other blocks; also caller must take care of the
     513                 :            :    necessary cleanup of the temporary markers after end of the basic block.
     514                 :            :    */
     515                 :            : 
     516                 :            : static void
     517                 :        678 : find_moveable_store (rtx_insn *insn, int *regs_set_before, int *regs_set_after)
     518                 :            : {
     519                 :        678 :   struct st_expr * ptr;
     520                 :        678 :   rtx dest, set;
     521                 :        678 :   int check_anticipatable, check_available;
     522                 :        678 :   basic_block bb = BLOCK_FOR_INSN (insn);
     523                 :            : 
     524                 :        678 :   set = single_set (insn);
     525                 :        678 :   if (!set)
     526                 :            :     return;
     527                 :            : 
     528                 :        644 :   dest = SET_DEST (set);
     529                 :            : 
     530                 :        142 :   if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
     531                 :        784 :       || GET_MODE (dest) == BLKmode)
     532                 :            :     return;
     533                 :            : 
     534                 :        139 :   if (side_effects_p (dest))
     535                 :            :     return;
     536                 :            : 
     537                 :            :   /* If we are handling exceptions, we must be careful with memory references
     538                 :            :      that may trap.  If we are not, the behavior is undefined, so we may just
     539                 :            :      continue.  */
     540                 :        118 :   if (cfun->can_throw_non_call_exceptions && may_trap_p (dest))
     541                 :            :     return;
     542                 :            : 
     543                 :            :   /* Even if the destination cannot trap, the source may.  In this case we'd
     544                 :            :      need to handle updating the REG_EH_REGION note.  */
     545                 :        118 :   if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
     546                 :            :     return;
     547                 :            : 
     548                 :            :   /* Make sure that the SET_SRC of this store insns can be assigned to
     549                 :            :      a register, or we will fail later on in replace_store_insn, which
     550                 :            :      assumes that we can do this.  But sometimes the target machine has
     551                 :            :      oddities like MEM read-modify-write instruction.  See for example
     552                 :            :      PR24257.  */
     553                 :        118 :   if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set),
     554                 :        118 :                                               GET_MODE (SET_SRC (set))))
     555                 :            :     return;
     556                 :            : 
     557                 :        118 :   ptr = st_expr_entry (dest);
     558                 :        118 :   if (ptr->pattern_regs.is_empty ())
     559                 :        113 :     extract_mentioned_regs (dest, &ptr->pattern_regs);
     560                 :            : 
     561                 :            :   /* Do not check for anticipatability if we either found one anticipatable
     562                 :            :      store already, or tested for one and found out that it was killed.  */
     563                 :        118 :   check_anticipatable = 0;
     564                 :        118 :   if (ptr->antic_stores.is_empty ())
     565                 :            :     check_anticipatable = 1;
     566                 :            :   else
     567                 :            :     {
     568                 :          0 :       rtx_insn *tmp = ptr->antic_stores.last ();
     569                 :          0 :       if (tmp != NULL_RTX
     570                 :          0 :           && BLOCK_FOR_INSN (tmp) != bb)
     571                 :            :         check_anticipatable = 1;
     572                 :            :     }
     573                 :            :   if (check_anticipatable)
     574                 :            :     {
     575                 :        118 :       rtx_insn *tmp;
     576                 :        118 :       if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
     577                 :         25 :         tmp = NULL;
     578                 :            :       else
     579                 :         93 :         tmp = insn;
     580                 :        118 :       ptr->antic_stores.safe_push (tmp);
     581                 :            :     }
     582                 :            : 
     583                 :            :   /* It is not necessary to check whether store is available if we did
     584                 :            :      it successfully before; if we failed before, do not bother to check
     585                 :            :      until we reach the insn that caused us to fail.  */
     586                 :        118 :   check_available = 0;
     587                 :        118 :   if (ptr->avail_stores.is_empty ())
     588                 :            :     check_available = 1;
     589                 :            :   else
     590                 :            :     {
     591                 :          5 :       rtx_insn *tmp = ptr->avail_stores.last ();
     592                 :          5 :       if (BLOCK_FOR_INSN (tmp) != bb)
     593                 :            :         check_available = 1;
     594                 :            :     }
     595                 :            :   if (check_available)
     596                 :            :     {
     597                 :            :       /* Check that we have already reached the insn at that the check
     598                 :            :          failed last time.  */
     599                 :        118 :       if (LAST_AVAIL_CHECK_FAILURE (ptr))
     600                 :            :         {
     601                 :          0 :           rtx_insn *tmp;
     602                 :          0 :           for (tmp = BB_END (bb);
     603                 :          0 :                tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
     604                 :          0 :                tmp = PREV_INSN (tmp))
     605                 :          0 :             continue;
     606                 :          0 :           if (tmp == insn)
     607                 :            :             check_available = 0;
     608                 :            :         }
     609                 :            :       else
     610                 :        118 :         check_available = store_killed_after (dest, ptr->pattern_regs, insn,
     611                 :            :                                               bb, regs_set_after,
     612                 :            :                                               &LAST_AVAIL_CHECK_FAILURE (ptr));
     613                 :            :     }
     614                 :        118 :   if (!check_available)
     615                 :         99 :     ptr->avail_stores.safe_push (insn);
     616                 :            : }
     617                 :            : 
     618                 :            : /* Find available and anticipatable stores.  */
     619                 :            : 
     620                 :            : static int
     621                 :         46 : compute_store_table (void)
     622                 :            : {
     623                 :         46 :   int ret;
     624                 :         46 :   basic_block bb;
     625                 :         46 :   rtx_insn *insn;
     626                 :         46 :   rtx_insn *tmp;
     627                 :         46 :   df_ref def;
     628                 :         46 :   int *last_set_in, *already_set;
     629                 :         46 :   struct st_expr * ptr, **prev_next_ptr_ptr;
     630                 :         46 :   unsigned int max_gcse_regno = max_reg_num ();
     631                 :            : 
     632                 :         46 :   store_motion_mems = NULL;
     633                 :         46 :   store_motion_mems_table = new hash_table<st_expr_hasher> (13);
     634                 :         46 :   last_set_in = XCNEWVEC (int, max_gcse_regno);
     635                 :         46 :   already_set = XNEWVEC (int, max_gcse_regno);
     636                 :            : 
     637                 :            :   /* Find all the stores we care about.  */
     638                 :        215 :   FOR_EACH_BB_FN (bb, cfun)
     639                 :            :     {
     640                 :            :       /* First compute the registers set in this block.  */
     641                 :       2093 :       FOR_BB_INSNS (bb, insn)
     642                 :            :         {
     643                 :            : 
     644                 :        962 :           if (! NONDEBUG_INSN_P (insn))
     645                 :        284 :             continue;
     646                 :            : 
     647                 :       2762 :           FOR_EACH_INSN_DEF (def, insn)
     648                 :       2084 :             last_set_in[DF_REF_REGNO (def)] = INSN_UID (insn);
     649                 :            :         }
     650                 :            : 
     651                 :            :       /* Now find the stores.  */
     652                 :        169 :       memset (already_set, 0, sizeof (int) * max_gcse_regno);
     653                 :       2093 :       FOR_BB_INSNS (bb, insn)
     654                 :            :         {
     655                 :        962 :           if (! NONDEBUG_INSN_P (insn))
     656                 :        284 :             continue;
     657                 :            : 
     658                 :       2762 :           FOR_EACH_INSN_DEF (def, insn)
     659                 :       2084 :             already_set[DF_REF_REGNO (def)] = INSN_UID (insn);
     660                 :            : 
     661                 :            :           /* Now that we've marked regs, look for stores.  */
     662                 :        678 :           find_moveable_store (insn, already_set, last_set_in);
     663                 :            : 
     664                 :            :           /* Unmark regs that are no longer set.  */
     665                 :       2762 :           FOR_EACH_INSN_DEF (def, insn)
     666                 :       2084 :             if (last_set_in[DF_REF_REGNO (def)] == INSN_UID (insn))
     667                 :       1933 :               last_set_in[DF_REF_REGNO (def)] = 0;
     668                 :            :         }
     669                 :            : 
     670                 :        169 :       if (flag_checking)
     671                 :            :         {
     672                 :            :           /* last_set_in should now be all-zero.  */
     673                 :      24315 :           for (unsigned regno = 0; regno < max_gcse_regno; regno++)
     674                 :      24146 :             gcc_assert (!last_set_in[regno]);
     675                 :            :         }
     676                 :            : 
     677                 :            :       /* Clear temporary marks.  */
     678                 :        905 :       for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
     679                 :            :         {
     680                 :        736 :           LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
     681                 :        736 :           if (!ptr->antic_stores.is_empty ()
     682                 :        695 :               && (tmp = ptr->antic_stores.last ()) == NULL)
     683                 :         25 :             ptr->antic_stores.pop ();
     684                 :            :         }
     685                 :            :     }
     686                 :            : 
     687                 :            :   /* Remove the stores that are not available anywhere, as there will
     688                 :            :      be no opportunity to optimize them.  */
     689                 :         46 :   for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
     690                 :        159 :        ptr != NULL;
     691                 :        113 :        ptr = *prev_next_ptr_ptr)
     692                 :            :     {
     693                 :        113 :       if (ptr->avail_stores.is_empty ())
     694                 :            :         {
     695                 :         19 :           *prev_next_ptr_ptr = ptr->next;
     696                 :         19 :           store_motion_mems_table->remove_elt_with_hash (ptr, ptr->hash_index);
     697                 :         19 :           free_st_expr_entry (ptr);
     698                 :            :         }
     699                 :            :       else
     700                 :         94 :         prev_next_ptr_ptr = &ptr->next;
     701                 :            :     }
     702                 :            : 
     703                 :         46 :   ret = enumerate_store_motion_mems ();
     704                 :            : 
     705                 :         46 :   if (dump_file)
     706                 :          2 :     print_store_motion_mems (dump_file);
     707                 :            : 
     708                 :         46 :   free (last_set_in);
     709                 :         46 :   free (already_set);
     710                 :         46 :   return ret;
     711                 :            : }
     712                 :            : 
     713                 :            : /* In all code following after this, REACHING_REG has its original
     714                 :            :    meaning again.  Avoid confusion, and undef the accessor macro for
     715                 :            :    the temporary marks usage in compute_store_table.  */
     716                 :            : #undef LAST_AVAIL_CHECK_FAILURE
     717                 :            : 
     718                 :            : /* Insert an instruction at the beginning of a basic block, and update
     719                 :            :    the BB_HEAD if needed.  */
     720                 :            : 
     721                 :            : static void
     722                 :          2 : insert_insn_start_basic_block (rtx_insn *insn, basic_block bb)
     723                 :            : {
     724                 :            :   /* Insert at start of successor block.  */
     725                 :          2 :   rtx_insn *prev = PREV_INSN (BB_HEAD (bb));
     726                 :          2 :   rtx_insn *before = BB_HEAD (bb);
     727                 :          4 :   while (before != 0)
     728                 :            :     {
     729                 :          4 :       if (! LABEL_P (before)
     730                 :          4 :           && !NOTE_INSN_BASIC_BLOCK_P (before))
     731                 :            :         break;
     732                 :          2 :       prev = before;
     733                 :          2 :       if (prev == BB_END (bb))
     734                 :            :         break;
     735                 :          2 :       before = NEXT_INSN (before);
     736                 :            :     }
     737                 :            : 
     738                 :          2 :   insn = emit_insn_after_noloc (insn, prev, bb);
     739                 :            : 
     740                 :          2 :   if (dump_file)
     741                 :            :     {
     742                 :          0 :       fprintf (dump_file, "STORE_MOTION  insert store at start of BB %d:\n",
     743                 :            :                bb->index);
     744                 :          0 :       print_inline_rtx (dump_file, insn, 6);
     745                 :          0 :       fprintf (dump_file, "\n");
     746                 :            :     }
     747                 :          2 : }
     748                 :            : 
     749                 :            : /* This routine will insert a store on an edge. EXPR is the st_expr entry for
     750                 :            :    the memory reference, and E is the edge to insert it on.  Returns nonzero
     751                 :            :    if an edge insertion was performed.  */
     752                 :            : 
     753                 :            : static int
     754                 :         20 : insert_store (struct st_expr * expr, edge e)
     755                 :            : {
     756                 :         20 :   rtx reg;
     757                 :         20 :   rtx_insn *insn;
     758                 :         20 :   basic_block bb;
     759                 :         20 :   edge tmp;
     760                 :         20 :   edge_iterator ei;
     761                 :            : 
     762                 :            :   /* We did all the deleted before this insert, so if we didn't delete a
     763                 :            :      store, then we haven't set the reaching reg yet either.  */
     764                 :         20 :   if (expr->reaching_reg == NULL_RTX)
     765                 :            :     return 0;
     766                 :            : 
     767                 :         20 :   if (e->flags & EDGE_FAKE)
     768                 :            :     return 0;
     769                 :            : 
     770                 :         20 :   reg = expr->reaching_reg;
     771                 :         20 :   insn = gen_move_insn (copy_rtx (expr->pattern), reg);
     772                 :            : 
     773                 :            :   /* If we are inserting this expression on ALL predecessor edges of a BB,
     774                 :            :      insert it at the start of the BB, and reset the insert bits on the other
     775                 :            :      edges so we don't try to insert it on the other edges.  */
     776                 :         20 :   bb = e->dest;
     777                 :         29 :   FOR_EACH_EDGE (tmp, ei, e->dest->preds)
     778                 :         27 :     if (!(tmp->flags & EDGE_FAKE))
     779                 :            :       {
     780                 :         27 :         int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
     781                 :            : 
     782                 :         27 :         gcc_assert (index != EDGE_INDEX_NO_EDGE);
     783                 :         27 :         if (! bitmap_bit_p (st_insert_map[index], expr->index))
     784                 :            :           break;
     785                 :            :       }
     786                 :            : 
     787                 :            :   /* If tmp is NULL, we found an insertion on every edge, blank the
     788                 :            :      insertion vector for these edges, and insert at the start of the BB.  */
     789                 :         20 :   if (!tmp && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
     790                 :            :     {
     791                 :          4 :       FOR_EACH_EDGE (tmp, ei, e->dest->preds)
     792                 :            :         {
     793                 :          2 :           int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
     794                 :          2 :           bitmap_clear_bit (st_insert_map[index], expr->index);
     795                 :            :         }
     796                 :          2 :       insert_insn_start_basic_block (insn, bb);
     797                 :          2 :       return 0;
     798                 :            :     }
     799                 :            : 
     800                 :            :   /* We can't put stores in the front of blocks pointed to by abnormal
     801                 :            :      edges since that may put a store where one didn't used to be.  */
     802                 :         18 :   gcc_assert (!(e->flags & EDGE_ABNORMAL));
     803                 :            : 
     804                 :         18 :   insert_insn_on_edge (insn, e);
     805                 :            : 
     806                 :         18 :   if (dump_file)
     807                 :            :     {
     808                 :          1 :       fprintf (dump_file, "STORE_MOTION  insert insn on edge (%d, %d):\n",
     809                 :          1 :                e->src->index, e->dest->index);
     810                 :          1 :       print_inline_rtx (dump_file, insn, 6);
     811                 :          1 :       fprintf (dump_file, "\n");
     812                 :            :     }
     813                 :            : 
     814                 :            :   return 1;
     815                 :            : }
     816                 :            : 
     817                 :            : /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
     818                 :            :    memory location in SMEXPR set in basic block BB.
     819                 :            : 
     820                 :            :    This could be rather expensive.  */
     821                 :            : 
     822                 :            : static void
     823                 :         20 : remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
     824                 :            : {
     825                 :         20 :   edge_iterator *stack, ei;
     826                 :         20 :   int sp;
     827                 :         20 :   edge act;
     828                 :         40 :   auto_sbitmap visited (last_basic_block_for_fn (cfun));
     829                 :         20 :   rtx note;
     830                 :         20 :   rtx_insn *insn;
     831                 :         20 :   rtx mem = smexpr->pattern;
     832                 :            : 
     833                 :         20 :   stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun));
     834                 :         20 :   sp = 0;
     835                 :         20 :   ei = ei_start (bb->succs);
     836                 :            : 
     837                 :         20 :   bitmap_clear (visited);
     838                 :            : 
     839                 :         20 :   act = (EDGE_COUNT (ei_container (ei))
     840                 :         20 :          ? EDGE_I (ei_container (ei), 0)
     841                 :            :          : NULL);
     842                 :        137 :   for (;;)
     843                 :            :     {
     844                 :        137 :       if (!act)
     845                 :            :         {
     846                 :         42 :           if (!sp)
     847                 :            :             {
     848                 :         20 :               free (stack);
     849                 :         20 :               return;
     850                 :            :             }
     851                 :         22 :           act = ei_edge (stack[--sp]);
     852                 :            :         }
     853                 :        117 :       bb = act->dest;
     854                 :            : 
     855                 :        174 :       if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
     856                 :        117 :           || bitmap_bit_p (visited, bb->index))
     857                 :            :         {
     858                 :        114 :           if (!ei_end_p (ei))
     859                 :         43 :               ei_next (&ei);
     860                 :        114 :           act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
     861                 :         57 :           continue;
     862                 :            :         }
     863                 :         60 :       bitmap_set_bit (visited, bb->index);
     864                 :            : 
     865                 :         60 :       rtx_insn *last;
     866                 :         60 :       if (bitmap_bit_p (st_antloc[bb->index], smexpr->index))
     867                 :            :         {
     868                 :         20 :           unsigned int i;
     869                 :         40 :           FOR_EACH_VEC_ELT_REVERSE (smexpr->antic_stores, i, last)
     870                 :         20 :             if (BLOCK_FOR_INSN (last) == bb)
     871                 :            :               break;
     872                 :            :         }
     873                 :            :       else
     874                 :         40 :         last = NEXT_INSN (BB_END (bb));
     875                 :            : 
     876                 :        604 :       for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
     877                 :        272 :         if (NONDEBUG_INSN_P (insn))
     878                 :            :           {
     879                 :        167 :             note = find_reg_equal_equiv_note (insn);
     880                 :        167 :             if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
     881                 :        167 :               continue;
     882                 :            : 
     883                 :          0 :             if (dump_file)
     884                 :          0 :               fprintf (dump_file,
     885                 :            :                        "STORE_MOTION  drop REG_EQUAL note at insn %d:\n",
     886                 :          0 :                        INSN_UID (insn));
     887                 :          0 :             remove_note (insn, note);
     888                 :            :           }
     889                 :            : 
     890                 :        120 :       if (!ei_end_p (ei))
     891                 :         52 :         ei_next (&ei);
     892                 :        120 :       act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
     893                 :            : 
     894                 :        197 :       if (EDGE_COUNT (bb->succs) > 0)
     895                 :            :         {
     896                 :         60 :           if (act)
     897                 :         22 :             stack[sp++] = ei;
     898                 :         60 :           ei = ei_start (bb->succs);
     899                 :         60 :           act = (EDGE_COUNT (ei_container (ei))
     900                 :         60 :                  ? EDGE_I (ei_container (ei), 0)
     901                 :            :                  : NULL);
     902                 :            :         }
     903                 :            :     }
     904                 :            : }
     905                 :            : 
     906                 :            : /* This routine will replace a store with a SET to a specified register.  */
     907                 :            : 
     908                 :            : static void
     909                 :         20 : replace_store_insn (rtx reg, rtx_insn *del, basic_block bb,
     910                 :            :                     struct st_expr *smexpr)
     911                 :            : {
     912                 :         20 :   rtx_insn *insn;
     913                 :         20 :   rtx mem, note, set;
     914                 :            : 
     915                 :         20 :   insn = prepare_copy_insn (reg, SET_SRC (single_set (del)));
     916                 :            : 
     917                 :         20 :   unsigned int i;
     918                 :         20 :   rtx_insn *temp;
     919                 :         45 :   FOR_EACH_VEC_ELT_REVERSE (smexpr->antic_stores, i, temp)
     920                 :         20 :     if (temp == del)
     921                 :            :       {
     922                 :         15 :         smexpr->antic_stores[i] = insn;
     923                 :         15 :         break;
     924                 :            :       }
     925                 :            : 
     926                 :            :   /* Move the notes from the deleted insn to its replacement.  */
     927                 :         20 :   REG_NOTES (insn) = REG_NOTES (del);
     928                 :            : 
     929                 :            :   /* Emit the insn AFTER all the notes are transferred.
     930                 :            :      This is cheaper since we avoid df rescanning for the note change.  */
     931                 :         20 :   insn = emit_insn_after (insn, del);
     932                 :            : 
     933                 :         20 :   if (dump_file)
     934                 :            :     {
     935                 :          1 :       fprintf (dump_file,
     936                 :            :                "STORE_MOTION  delete insn in BB %d:\n      ", bb->index);
     937                 :          1 :       print_inline_rtx (dump_file, del, 6);
     938                 :          1 :       fprintf (dump_file, "\nSTORE_MOTION  replaced with insn:\n      ");
     939                 :          1 :       print_inline_rtx (dump_file, insn, 6);
     940                 :          1 :       fprintf (dump_file, "\n");
     941                 :            :     }
     942                 :            : 
     943                 :         20 :   delete_insn (del);
     944                 :            : 
     945                 :            :   /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
     946                 :            :      they are no longer accurate provided that they are reached by this
     947                 :            :      definition, so drop them.  */
     948                 :         20 :   mem = smexpr->pattern;
     949                 :        242 :   for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
     950                 :        111 :     if (NONDEBUG_INSN_P (insn))
     951                 :            :       {
     952                 :        104 :         set = single_set (insn);
     953                 :        104 :         if (!set)
     954                 :          0 :           continue;
     955                 :        104 :         if (exp_equiv_p (SET_DEST (set), mem, 0, true))
     956                 :         20 :           return;
     957                 :        104 :         note = find_reg_equal_equiv_note (insn);
     958                 :        104 :         if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
     959                 :        104 :           continue;
     960                 :            : 
     961                 :          0 :         if (dump_file)
     962                 :          0 :           fprintf (dump_file, "STORE_MOTION  drop REG_EQUAL note at insn %d:\n",
     963                 :          0 :                    INSN_UID (insn));
     964                 :          0 :         remove_note (insn, note);
     965                 :            :       }
     966                 :         20 :   remove_reachable_equiv_notes (bb, smexpr);
     967                 :            : }
     968                 :            : 
     969                 :            : 
     970                 :            : /* Delete a store, but copy the value that would have been stored into
     971                 :            :    the reaching_reg for later storing.  */
     972                 :            : 
     973                 :            : static void
     974                 :         20 : delete_store (struct st_expr * expr, basic_block bb)
     975                 :            : {
     976                 :         20 :   rtx reg;
     977                 :            : 
     978                 :         20 :   if (expr->reaching_reg == NULL_RTX)
     979                 :         20 :     expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
     980                 :            : 
     981                 :         20 :   reg = expr->reaching_reg;
     982                 :            : 
     983                 :         20 :   unsigned int len = expr->avail_stores.length ();
     984                 :         25 :   for (unsigned int i = len - 1; i < len; i--)
     985                 :            :     {
     986                 :         25 :       rtx_insn *del = expr->avail_stores[i];
     987                 :         25 :       if (BLOCK_FOR_INSN (del) == bb)
     988                 :            :         {
     989                 :            :           /* We know there is only one since we deleted redundant
     990                 :            :              ones during the available computation.  */
     991                 :         20 :           replace_store_insn (reg, del, bb, expr);
     992                 :         20 :           break;
     993                 :            :         }
     994                 :            :     }
     995                 :         20 : }
     996                 :            : 
     997                 :            : /* Fill in available, anticipatable, transparent and kill vectors in
     998                 :            :    STORE_DATA, based on lists of available and anticipatable stores.  */
     999                 :            : static void
    1000                 :         21 : build_store_vectors (void)
    1001                 :            : {
    1002                 :         21 :   basic_block bb;
    1003                 :         21 :   int *regs_set_in_block;
    1004                 :         21 :   rtx_insn *insn;
    1005                 :         21 :   struct st_expr * ptr;
    1006                 :         21 :   unsigned int max_gcse_regno = max_reg_num ();
    1007                 :            : 
    1008                 :            :   /* Build the gen_vector. This is any store in the table which is not killed
    1009                 :            :      by aliasing later in its block.  */
    1010                 :         21 :   st_avloc = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
    1011                 :            :                                    num_stores);
    1012                 :         21 :   bitmap_vector_clear (st_avloc, last_basic_block_for_fn (cfun));
    1013                 :            : 
    1014                 :         21 :   st_antloc = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
    1015                 :            :                                     num_stores);
    1016                 :         21 :   bitmap_vector_clear (st_antloc, last_basic_block_for_fn (cfun));
    1017                 :            : 
    1018                 :        115 :   for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
    1019                 :            :     {
    1020                 :         94 :       unsigned int len = ptr->avail_stores.length ();
    1021                 :        193 :       for (unsigned int i = len - 1; i < len; i--)
    1022                 :            :         {
    1023                 :         99 :           insn = ptr->avail_stores[i];
    1024                 :         99 :           bb = BLOCK_FOR_INSN (insn);
    1025                 :            : 
    1026                 :            :           /* If we've already seen an available expression in this block,
    1027                 :            :              we can delete this one (It occurs earlier in the block). We'll
    1028                 :            :              copy the SRC expression to an unused register in case there
    1029                 :            :              are any side effects.  */
    1030                 :         99 :           if (bitmap_bit_p (st_avloc[bb->index], ptr->index))
    1031                 :            :             {
    1032                 :          0 :               rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
    1033                 :          0 :               if (dump_file)
    1034                 :          0 :                 fprintf (dump_file, "Removing redundant store:\n");
    1035                 :          0 :               replace_store_insn (r, insn, bb, ptr);
    1036                 :          0 :               continue;
    1037                 :            :             }
    1038                 :        198 :           bitmap_set_bit (st_avloc[bb->index], ptr->index);
    1039                 :            :         }
    1040                 :            : 
    1041                 :         94 :       unsigned int i;
    1042                 :        357 :       FOR_EACH_VEC_ELT_REVERSE (ptr->antic_stores, i, insn)
    1043                 :            :         {
    1044                 :         75 :           bb = BLOCK_FOR_INSN (insn);
    1045                 :         75 :           bitmap_set_bit (st_antloc[bb->index], ptr->index);
    1046                 :            :         }
    1047                 :            :     }
    1048                 :            : 
    1049                 :         21 :   st_kill = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), num_stores);
    1050                 :         21 :   bitmap_vector_clear (st_kill, last_basic_block_for_fn (cfun));
    1051                 :            : 
    1052                 :         21 :   st_transp = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), num_stores);
    1053                 :         21 :   bitmap_vector_clear (st_transp, last_basic_block_for_fn (cfun));
    1054                 :         21 :   regs_set_in_block = XNEWVEC (int, max_gcse_regno);
    1055                 :            : 
    1056                 :        116 :   FOR_EACH_BB_FN (bb, cfun)
    1057                 :            :     {
    1058                 :         95 :       memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
    1059                 :            : 
    1060                 :       1215 :       FOR_BB_INSNS (bb, insn)
    1061                 :        560 :         if (NONDEBUG_INSN_P (insn))
    1062                 :            :           {
    1063                 :        384 :             df_ref def;
    1064                 :        893 :             FOR_EACH_INSN_DEF (def, insn)
    1065                 :            :               {
    1066                 :        509 :                 unsigned int ref_regno = DF_REF_REGNO (def);
    1067                 :        509 :                 if (ref_regno < max_gcse_regno)
    1068                 :        509 :                   regs_set_in_block[DF_REF_REGNO (def)] = 1;
    1069                 :            :               }
    1070                 :            :           }
    1071                 :            : 
    1072                 :        754 :       for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
    1073                 :            :         {
    1074                 :        659 :           if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
    1075                 :            :                                   bb, regs_set_in_block, NULL))
    1076                 :            :             {
    1077                 :            :               /* It should not be necessary to consider the expression
    1078                 :            :                  killed if it is both anticipatable and available.  */
    1079                 :        117 :               if (!bitmap_bit_p (st_antloc[bb->index], ptr->index)
    1080                 :        117 :                   || !bitmap_bit_p (st_avloc[bb->index], ptr->index))
    1081                 :        117 :                 bitmap_set_bit (st_kill[bb->index], ptr->index);
    1082                 :            :             }
    1083                 :            :           else
    1084                 :       1201 :             bitmap_set_bit (st_transp[bb->index], ptr->index);
    1085                 :            :         }
    1086                 :            :     }
    1087                 :            : 
    1088                 :         21 :   free (regs_set_in_block);
    1089                 :            : 
    1090                 :         21 :   if (dump_file)
    1091                 :            :     {
    1092                 :          1 :       dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc,
    1093                 :          1 :                           last_basic_block_for_fn (cfun));
    1094                 :          1 :       dump_bitmap_vector (dump_file, "st_kill", "", st_kill,
    1095                 :          1 :                           last_basic_block_for_fn (cfun));
    1096                 :          1 :       dump_bitmap_vector (dump_file, "st_transp", "", st_transp,
    1097                 :          1 :                           last_basic_block_for_fn (cfun));
    1098                 :          1 :       dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc,
    1099                 :          1 :                           last_basic_block_for_fn (cfun));
    1100                 :            :     }
    1101                 :         21 : }
    1102                 :            : 
    1103                 :            : /* Free memory used by store motion.  */
    1104                 :            : 
    1105                 :            : static void
    1106                 :         21 : free_store_memory (void)
    1107                 :            : {
    1108                 :         21 :   free_store_motion_mems ();
    1109                 :            : 
    1110                 :         21 :   if (st_avloc)
    1111                 :         21 :     sbitmap_vector_free (st_avloc);
    1112                 :         21 :   if (st_kill)
    1113                 :         21 :     sbitmap_vector_free (st_kill);
    1114                 :         21 :   if (st_transp)
    1115                 :         21 :     sbitmap_vector_free (st_transp);
    1116                 :         21 :   if (st_antloc)
    1117                 :         21 :     sbitmap_vector_free (st_antloc);
    1118                 :         21 :   if (st_insert_map)
    1119                 :         21 :     sbitmap_vector_free (st_insert_map);
    1120                 :         21 :   if (st_delete_map)
    1121                 :         21 :     sbitmap_vector_free (st_delete_map);
    1122                 :            : 
    1123                 :         21 :   st_avloc = st_kill = st_transp = st_antloc = NULL;
    1124                 :         21 :   st_insert_map = st_delete_map = NULL;
    1125                 :         21 : }
    1126                 :            : 
    1127                 :            : /* Perform store motion. Much like gcse, except we move expressions the
    1128                 :            :    other way by looking at the flowgraph in reverse.
    1129                 :            :    Return non-zero if transformations are performed by the pass.  */
    1130                 :            : 
    1131                 :            : static int
    1132                 :         46 : one_store_motion_pass (void)
    1133                 :            : {
    1134                 :         46 :   basic_block bb;
    1135                 :         46 :   int x;
    1136                 :         46 :   struct st_expr * ptr;
    1137                 :         46 :   int did_edge_inserts = 0;
    1138                 :         46 :   int n_stores_deleted = 0;
    1139                 :         46 :   int n_stores_created = 0;
    1140                 :            : 
    1141                 :         46 :   init_alias_analysis ();
    1142                 :            : 
    1143                 :            :   /* Find all the available and anticipatable stores.  */
    1144                 :         46 :   num_stores = compute_store_table ();
    1145                 :         46 :   if (num_stores == 0)
    1146                 :            :     {
    1147                 :         25 :       delete store_motion_mems_table;
    1148                 :         25 :       store_motion_mems_table = NULL;
    1149                 :         25 :       end_alias_analysis ();
    1150                 :         25 :       return 0;
    1151                 :            :     }
    1152                 :            : 
    1153                 :            :   /* Now compute kill & transp vectors.  */
    1154                 :         21 :   build_store_vectors ();
    1155                 :         21 :   add_noreturn_fake_exit_edges ();
    1156                 :         21 :   connect_infinite_loops_to_exit ();
    1157                 :            : 
    1158                 :         21 :   edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
    1159                 :            :                                 st_antloc, st_kill, &st_insert_map,
    1160                 :            :                                 &st_delete_map);
    1161                 :            : 
    1162                 :            :   /* Now we want to insert the new stores which are going to be needed.  */
    1163                 :        115 :   for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
    1164                 :            :     {
    1165                 :            :       /* If any of the edges we have above are abnormal, we can't move this
    1166                 :            :          store.  */
    1167                 :       1163 :       for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
    1168                 :       1069 :         if (bitmap_bit_p (st_insert_map[x], ptr->index)
    1169                 :       1069 :             && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
    1170                 :            :           break;
    1171                 :            : 
    1172                 :         94 :       if (x >= 0)
    1173                 :            :         {
    1174                 :          0 :           if (dump_file != NULL)
    1175                 :          0 :             fprintf (dump_file,
    1176                 :            :                      "Can't replace store %d: abnormal edge from %d to %d\n",
    1177                 :          0 :                      ptr->index, INDEX_EDGE (edge_list, x)->src->index,
    1178                 :          0 :                      INDEX_EDGE (edge_list, x)->dest->index);
    1179                 :          0 :           continue;
    1180                 :            :         }
    1181                 :            : 
    1182                 :            :       /* Now we want to insert the new stores which are going to be needed.  */
    1183                 :            : 
    1184                 :        753 :       FOR_EACH_BB_FN (bb, cfun)
    1185                 :        659 :         if (bitmap_bit_p (st_delete_map[bb->index], ptr->index))
    1186                 :            :           {
    1187                 :         20 :             delete_store (ptr, bb);
    1188                 :         20 :             n_stores_deleted++;
    1189                 :            :           }
    1190                 :            : 
    1191                 :       1163 :       for (x = 0; x < NUM_EDGES (edge_list); x++)
    1192                 :       1069 :         if (bitmap_bit_p (st_insert_map[x], ptr->index))
    1193                 :            :           {
    1194                 :         20 :             did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
    1195                 :         20 :             n_stores_created++;
    1196                 :            :           }
    1197                 :            :     }
    1198                 :            : 
    1199                 :         21 :   if (did_edge_inserts)
    1200                 :         11 :     commit_edge_insertions ();
    1201                 :            : 
    1202                 :         21 :   free_store_memory ();
    1203                 :         21 :   free_edge_list (edge_list);
    1204                 :         21 :   remove_fake_exit_edges ();
    1205                 :         21 :   end_alias_analysis ();
    1206                 :            : 
    1207                 :         21 :   if (dump_file)
    1208                 :            :     {
    1209                 :          1 :       fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
    1210                 :          1 :                current_function_name (), n_basic_blocks_for_fn (cfun));
    1211                 :          1 :       fprintf (dump_file, "%d insns deleted, %d insns created\n",
    1212                 :            :                n_stores_deleted, n_stores_created);
    1213                 :            :     }
    1214                 :            : 
    1215                 :         21 :   return (n_stores_deleted > 0 || n_stores_created > 0);
    1216                 :            : }
    1217                 :            : 
    1218                 :            : 
    1219                 :            : static unsigned int
    1220                 :         46 : execute_rtl_store_motion (void)
    1221                 :            : {
    1222                 :         46 :   delete_unreachable_blocks ();
    1223                 :         46 :   df_analyze ();
    1224                 :         46 :   flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
    1225                 :         46 :   return 0;
    1226                 :            : }
    1227                 :            : 
    1228                 :            : namespace {
    1229                 :            : 
    1230                 :            : const pass_data pass_data_rtl_store_motion =
    1231                 :            : {
    1232                 :            :   RTL_PASS, /* type */
    1233                 :            :   "store_motion", /* name */
    1234                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    1235                 :            :   TV_LSM, /* tv_id */
    1236                 :            :   PROP_cfglayout, /* properties_required */
    1237                 :            :   0, /* properties_provided */
    1238                 :            :   0, /* properties_destroyed */
    1239                 :            :   0, /* todo_flags_start */
    1240                 :            :   TODO_df_finish, /* todo_flags_finish */
    1241                 :            : };
    1242                 :            : 
    1243                 :            : class pass_rtl_store_motion : public rtl_opt_pass
    1244                 :            : {
    1245                 :            : public:
    1246                 :     200540 :   pass_rtl_store_motion (gcc::context *ctxt)
    1247                 :     401080 :     : rtl_opt_pass (pass_data_rtl_store_motion, ctxt)
    1248                 :            :   {}
    1249                 :            : 
    1250                 :            :   /* opt_pass methods: */
    1251                 :            :   virtual bool gate (function *);
    1252                 :         46 :   virtual unsigned int execute (function *)
    1253                 :            :     {
    1254                 :         46 :       return execute_rtl_store_motion ();
    1255                 :            :     }
    1256                 :            : 
    1257                 :            : }; // class pass_rtl_store_motion
    1258                 :            : 
    1259                 :            : bool
    1260                 :     942964 : pass_rtl_store_motion::gate (function *fun)
    1261                 :            : {
    1262                 :     687426 :   return optimize > 0 && flag_gcse_sm
    1263                 :         47 :     && !fun->calls_setjmp
    1264                 :         47 :     && optimize_function_for_speed_p (fun)
    1265                 :     943010 :     && dbg_cnt (store_motion);
    1266                 :            : }
    1267                 :            : 
    1268                 :            : } // anon namespace
    1269                 :            : 
    1270                 :            : rtl_opt_pass *
    1271                 :     200540 : make_pass_rtl_store_motion (gcc::context *ctxt)
    1272                 :            : {
    1273                 :     200540 :   return new pass_rtl_store_motion (ctxt);
    1274                 :            : }

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.