LCOV - code coverage report
Current view: top level - gcc - fwprop.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 635 667 95.2 %
Date: 2020-04-04 11:58:09 Functions: 34 35 97.1 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* RTL-based forward propagation pass for GNU compiler.
       2                 :            :    Copyright (C) 2005-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Paolo Bonzini and Steven Bosscher.
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "target.h"
      26                 :            : #include "rtl.h"
      27                 :            : #include "predict.h"
      28                 :            : #include "df.h"
      29                 :            : #include "memmodel.h"
      30                 :            : #include "tm_p.h"
      31                 :            : #include "insn-config.h"
      32                 :            : #include "emit-rtl.h"
      33                 :            : #include "recog.h"
      34                 :            : 
      35                 :            : #include "sparseset.h"
      36                 :            : #include "cfgrtl.h"
      37                 :            : #include "cfgcleanup.h"
      38                 :            : #include "cfgloop.h"
      39                 :            : #include "tree-pass.h"
      40                 :            : #include "domwalk.h"
      41                 :            : #include "rtl-iter.h"
      42                 :            : 
      43                 :            : 
      44                 :            : /* This pass does simple forward propagation and simplification when an
      45                 :            :    operand of an insn can only come from a single def.  This pass uses
      46                 :            :    df.c, so it is global.  However, we only do limited analysis of
      47                 :            :    available expressions.
      48                 :            : 
      49                 :            :    1) The pass tries to propagate the source of the def into the use,
      50                 :            :    and checks if the result is independent of the substituted value.
      51                 :            :    For example, the high word of a (zero_extend:DI (reg:SI M)) is always
      52                 :            :    zero, independent of the source register.
      53                 :            : 
      54                 :            :    In particular, we propagate constants into the use site.  Sometimes
      55                 :            :    RTL expansion did not put the constant in the same insn on purpose,
      56                 :            :    to satisfy a predicate, and the result will fail to be recognized;
      57                 :            :    but this happens rarely and in this case we can still create a
      58                 :            :    REG_EQUAL note.  For multi-word operations, this
      59                 :            : 
      60                 :            :       (set (subreg:SI (reg:DI 120) 0) (const_int 0))
      61                 :            :       (set (subreg:SI (reg:DI 120) 4) (const_int -1))
      62                 :            :       (set (subreg:SI (reg:DI 122) 0)
      63                 :            :          (ior:SI (subreg:SI (reg:DI 119) 0) (subreg:SI (reg:DI 120) 0)))
      64                 :            :       (set (subreg:SI (reg:DI 122) 4)
      65                 :            :          (ior:SI (subreg:SI (reg:DI 119) 4) (subreg:SI (reg:DI 120) 4)))
      66                 :            : 
      67                 :            :    can be simplified to the much simpler
      68                 :            : 
      69                 :            :       (set (subreg:SI (reg:DI 122) 0) (subreg:SI (reg:DI 119)))
      70                 :            :       (set (subreg:SI (reg:DI 122) 4) (const_int -1))
      71                 :            : 
      72                 :            :    This particular propagation is also effective at putting together
      73                 :            :    complex addressing modes.  We are more aggressive inside MEMs, in
      74                 :            :    that all definitions are propagated if the use is in a MEM; if the
      75                 :            :    result is a valid memory address we check address_cost to decide
      76                 :            :    whether the substitution is worthwhile.
      77                 :            : 
      78                 :            :    2) The pass propagates register copies.  This is not as effective as
      79                 :            :    the copy propagation done by CSE's canon_reg, which works by walking
      80                 :            :    the instruction chain, it can help the other transformations.
      81                 :            : 
      82                 :            :    We should consider removing this optimization, and instead reorder the
      83                 :            :    RTL passes, because GCSE does this transformation too.  With some luck,
      84                 :            :    the CSE pass at the end of rest_of_handle_gcse could also go away.
      85                 :            : 
      86                 :            :    3) The pass looks for paradoxical subregs that are actually unnecessary.
      87                 :            :    Things like this:
      88                 :            : 
      89                 :            :      (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
      90                 :            :      (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
      91                 :            :      (set (reg:SI 122) (plus:SI (subreg:SI (reg:QI 120) 0)
      92                 :            :                                 (subreg:SI (reg:QI 121) 0)))
      93                 :            : 
      94                 :            :    are very common on machines that can only do word-sized operations.
      95                 :            :    For each use of a paradoxical subreg (subreg:WIDER (reg:NARROW N) 0),
      96                 :            :    if it has a single def and it is (subreg:NARROW (reg:WIDE M) 0),
      97                 :            :    we can replace the paradoxical subreg with simply (reg:WIDE M).  The
      98                 :            :    above will simplify this to
      99                 :            : 
     100                 :            :      (set (reg:QI 120) (subreg:QI (reg:SI 118) 0))
     101                 :            :      (set (reg:QI 121) (subreg:QI (reg:SI 119) 0))
     102                 :            :      (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119)))
     103                 :            : 
     104                 :            :    where the first two insns are now dead.
     105                 :            : 
     106                 :            :    We used to use reaching definitions to find which uses have a
     107                 :            :    single reaching definition (sounds obvious...), but this is too
     108                 :            :    complex a problem in nasty testcases like PR33928.  Now we use the
     109                 :            :    multiple definitions problem in df-problems.c.  The similarity
     110                 :            :    between that problem and SSA form creation is taken further, in
     111                 :            :    that fwprop does a dominator walk to create its chains; however,
     112                 :            :    instead of creating a PHI function where multiple definitions meet
     113                 :            :    I just punt and record only singleton use-def chains, which is
     114                 :            :    all that is needed by fwprop.  */
     115                 :            : 
     116                 :            : 
     117                 :            : static int num_changes;
     118                 :            : 
     119                 :            : static vec<df_ref> use_def_ref;
     120                 :            : static vec<df_ref> reg_defs;
     121                 :            : static vec<df_ref> reg_defs_stack;
     122                 :            : 
     123                 :            : /* The maximum number of propagations that are still allowed.  If we do
     124                 :            :    more propagations than originally we had uses, we must have ended up
     125                 :            :    in a propagation loop, as in PR79405.  Until the algorithm fwprop
     126                 :            :    uses can obviously not get into such loops we need a workaround like
     127                 :            :    this.  */
     128                 :            : static int propagations_left;
     129                 :            : 
     130                 :            : /* The MD bitmaps are trimmed to include only live registers to cut
     131                 :            :    memory usage on testcases like insn-recog.c.  Track live registers
     132                 :            :    in the basic block and do not perform forward propagation if the
     133                 :            :    destination is a dead pseudo occurring in a note.  */
     134                 :            : static bitmap local_md;
     135                 :            : static bitmap local_lr;
     136                 :            : 
     137                 :            : /* Return the only def in USE's use-def chain, or NULL if there is
     138                 :            :    more than one def in the chain.  */
     139                 :            : 
     140                 :            : static inline df_ref
     141                 :  119454000 : get_def_for_use (df_ref use)
     142                 :            : {
     143                 :  238908000 :   return use_def_ref[DF_REF_ID (use)];
     144                 :            : }
     145                 :            : 
     146                 :            : 
     147                 :            : /* Update the reg_defs vector with non-partial definitions in DEF_REC.
     148                 :            :    TOP_FLAG says which artificials uses should be used, when DEF_REC
     149                 :            :    is an artificial def vector.  LOCAL_MD is modified as after a
     150                 :            :    df_md_simulate_* function; we do more or less the same processing
     151                 :            :    done there, so we do not use those functions.  */
     152                 :            : 
     153                 :            : #define DF_MD_GEN_FLAGS \
     154                 :            :         (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
     155                 :            : 
     156                 :            : static void
     157                 :  165999000 : process_defs (df_ref def, int top_flag)
     158                 :            : {
     159                 :  701091000 :   for (; def; def = DF_REF_NEXT_LOC (def))
     160                 :            :     {
     161                 :  535092000 :       df_ref curr_def = reg_defs[DF_REF_REGNO (def)];
     162                 :  535092000 :       unsigned int dregno;
     163                 :            : 
     164                 :  535092000 :       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
     165                 :   25403600 :         continue;
     166                 :            : 
     167                 :  509688000 :       dregno = DF_REF_REGNO (def);
     168                 :  509688000 :       if (curr_def)
     169                 :   60102700 :         reg_defs_stack.safe_push (curr_def);
     170                 :            :       else
     171                 :            :         {
     172                 :            :           /* Do not store anything if "transitioning" from NULL to NULL.  But
     173                 :            :              otherwise, push a special entry on the stack to tell the
     174                 :            :              leave_block callback that the entry in reg_defs was NULL.  */
     175                 :  449585000 :           if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
     176                 :            :             ;
     177                 :            :           else
     178                 :   68131800 :             reg_defs_stack.safe_push (def);
     179                 :            :         }
     180                 :            : 
     181                 :  509688000 :       if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
     182                 :            :         {
     183                 :  413343000 :           bitmap_set_bit (local_md, dregno);
     184                 :  413343000 :           reg_defs[dregno] = NULL;
     185                 :            :         }
     186                 :            :       else
     187                 :            :         {
     188                 :   96345200 :           bitmap_clear_bit (local_md, dregno);
     189                 :   96345200 :           reg_defs[dregno] = def;
     190                 :            :         }
     191                 :            :     }
     192                 :  165999000 : }
     193                 :            : 
     194                 :            : 
     195                 :            : /* Fill the use_def_ref vector with values for the uses in USE_REC,
     196                 :            :    taking reaching definitions info from LOCAL_MD and REG_DEFS.
     197                 :            :    TOP_FLAG says which artificials uses should be used, when USE_REC
     198                 :            :    is an artificial use vector.  */
     199                 :            : 
     200                 :            : static void
     201                 :  302033000 : process_uses (df_ref use, int top_flag)
     202                 :            : {
     203                 :  524602000 :   for (; use; use = DF_REF_NEXT_LOC (use))
     204                 :  222570000 :     if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
     205                 :            :       {
     206                 :  168147000 :         unsigned int uregno = DF_REF_REGNO (use);
     207                 :  168147000 :         if (reg_defs[uregno]
     208                 :  165253000 :             && !bitmap_bit_p (local_md, uregno)
     209                 :  325064000 :             && bitmap_bit_p (local_lr, uregno))
     210                 :  156677000 :           use_def_ref[DF_REF_ID (use)] = reg_defs[uregno];
     211                 :            :       }
     212                 :  302033000 : }
     213                 :            : 
     214                 :    1377020 : class single_def_use_dom_walker : public dom_walker
     215                 :            : {
     216                 :            : public:
     217                 :    1377020 :   single_def_use_dom_walker (cdi_direction direction)
     218                 :    2754040 :     : dom_walker (direction) {}
     219                 :            :   virtual edge before_dom_children (basic_block);
     220                 :            :   virtual void after_dom_children (basic_block);
     221                 :            : };
     222                 :            : 
     223                 :            : edge
     224                 :   14982700 : single_def_use_dom_walker::before_dom_children (basic_block bb)
     225                 :            : {
     226                 :   14982700 :   int bb_index = bb->index;
     227                 :   14982700 :   class df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index);
     228                 :   14982700 :   class df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
     229                 :   14982700 :   rtx_insn *insn;
     230                 :            : 
     231                 :   14982700 :   bitmap_copy (local_md, &md_bb_info->in);
     232                 :   14982700 :   bitmap_copy (local_lr, &lr_bb_info->in);
     233                 :            : 
     234                 :            :   /* Push a marker for the leave_block callback.  */
     235                 :   14982700 :   reg_defs_stack.safe_push (NULL);
     236                 :            : 
     237                 :   29965400 :   process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
     238                 :   29965400 :   process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
     239                 :            : 
     240                 :            :   /* We don't call df_simulate_initialize_forwards, as it may overestimate
     241                 :            :      the live registers if there are unused artificial defs.  We prefer
     242                 :            :      liveness to be underestimated.  */
     243                 :            : 
     244                 :  330057000 :   FOR_BB_INSNS (bb, insn)
     245                 :  157537000 :     if (INSN_P (insn))
     246                 :            :       {
     247                 :  136034000 :         unsigned int uid = INSN_UID (insn);
     248                 :  136034000 :         process_uses (DF_INSN_UID_USES (uid), 0);
     249                 :  136034000 :         process_uses (DF_INSN_UID_EQ_USES (uid), 0);
     250                 :  136034000 :         process_defs (DF_INSN_UID_DEFS (uid), 0);
     251                 :  136034000 :         df_simulate_one_insn_forwards (bb, insn, local_lr);
     252                 :            :       }
     253                 :            : 
     254                 :   29965400 :   process_uses (df_get_artificial_uses (bb_index), 0);
     255                 :   29965400 :   process_defs (df_get_artificial_defs (bb_index), 0);
     256                 :            : 
     257                 :   14982700 :   return NULL;
     258                 :            : }
     259                 :            : 
     260                 :            : /* Pop the definitions created in this basic block when leaving its
     261                 :            :    dominated parts.  */
     262                 :            : 
     263                 :            : void
     264                 :   14982700 : single_def_use_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
     265                 :            : {
     266                 :  143217000 :   df_ref saved_def;
     267                 :  143217000 :   while ((saved_def = reg_defs_stack.pop ()) != NULL)
     268                 :            :     {
     269                 :  128235000 :       unsigned int dregno = DF_REF_REGNO (saved_def);
     270                 :            : 
     271                 :            :       /* See also process_defs.  */
     272                 :  128235000 :       if (saved_def == reg_defs[dregno])
     273                 :   68131800 :         reg_defs[dregno] = NULL;
     274                 :            :       else
     275                 :   60102700 :         reg_defs[dregno] = saved_def;
     276                 :            :     }
     277                 :   14982700 : }
     278                 :            : 
     279                 :            : 
     280                 :            : /* Build a vector holding the reaching definitions of uses reached by a
     281                 :            :    single dominating definition.  */
     282                 :            : 
     283                 :            : static void
     284                 :    1377020 : build_single_def_use_links (void)
     285                 :            : {
     286                 :            :   /* We use the multiple definitions problem to compute our restricted
     287                 :            :      use-def chains.  */
     288                 :    1377020 :   df_set_flags (DF_EQ_NOTES);
     289                 :    1377020 :   df_md_add_problem ();
     290                 :    1377020 :   df_note_add_problem ();
     291                 :    1377020 :   df_analyze ();
     292                 :    1377020 :   df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
     293                 :            : 
     294                 :    1377020 :   use_def_ref.create (DF_USES_TABLE_SIZE ());
     295                 :    1377020 :   use_def_ref.safe_grow_cleared (DF_USES_TABLE_SIZE ());
     296                 :            : 
     297                 :    1377020 :   reg_defs.create (max_reg_num ());
     298                 :    1377020 :   reg_defs.safe_grow_cleared (max_reg_num ());
     299                 :            : 
     300                 :    1377020 :   reg_defs_stack.create (n_basic_blocks_for_fn (cfun) * 10);
     301                 :    1377020 :   local_md = BITMAP_ALLOC (NULL);
     302                 :    1377020 :   local_lr = BITMAP_ALLOC (NULL);
     303                 :            : 
     304                 :            :   /* Walk the dominator tree looking for single reaching definitions
     305                 :            :      dominating the uses.  This is similar to how SSA form is built.  */
     306                 :    1377020 :   single_def_use_dom_walker (CDI_DOMINATORS)
     307                 :    1377020 :     .walk (cfun->cfg->x_entry_block_ptr);
     308                 :            : 
     309                 :    1377020 :   BITMAP_FREE (local_lr);
     310                 :    1377020 :   BITMAP_FREE (local_md);
     311                 :    1377020 :   reg_defs.release ();
     312                 :    1377020 :   reg_defs_stack.release ();
     313                 :    1377020 : }
     314                 :            : 
     315                 :            : 
     316                 :            : /* Do not try to replace constant addresses or addresses of local and
     317                 :            :    argument slots.  These MEM expressions are made only once and inserted
     318                 :            :    in many instructions, as well as being used to control symbol table
     319                 :            :    output.  It is not safe to clobber them.
     320                 :            : 
     321                 :            :    There are some uncommon cases where the address is already in a register
     322                 :            :    for some reason, but we cannot take advantage of that because we have
     323                 :            :    no easy way to unshare the MEM.  In addition, looking up all stack
     324                 :            :    addresses is costly.  */
     325                 :            : 
     326                 :            : static bool
     327                 :    1574480 : can_simplify_addr (rtx addr)
     328                 :            : {
     329                 :    1574480 :   rtx reg;
     330                 :            : 
     331                 :    1574480 :   if (CONSTANT_ADDRESS_P (addr))
     332                 :            :     return false;
     333                 :            : 
     334                 :    1515610 :   if (GET_CODE (addr) == PLUS)
     335                 :     885713 :     reg = XEXP (addr, 0);
     336                 :            :   else
     337                 :            :     reg = addr;
     338                 :            : 
     339                 :    1515610 :   return (!REG_P (reg)
     340                 :    1515610 :           || (REGNO (reg) != FRAME_POINTER_REGNUM
     341                 :    1266580 :               && REGNO (reg) != HARD_FRAME_POINTER_REGNUM
     342                 :    1266580 :               && REGNO (reg) != ARG_POINTER_REGNUM));
     343                 :            : }
     344                 :            : 
     345                 :            : /* Returns a canonical version of X for the address, from the point of view,
     346                 :            :    that all multiplications are represented as MULT instead of the multiply
     347                 :            :    by a power of 2 being represented as ASHIFT.
     348                 :            : 
     349                 :            :    Every ASHIFT we find has been made by simplify_gen_binary and was not
     350                 :            :    there before, so it is not shared.  So we can do this in place.  */
     351                 :            : 
     352                 :            : static void
     353                 :    1710840 : canonicalize_address (rtx x)
     354                 :            : {
     355                 :    3579390 :   for (;;)
     356                 :    3579390 :     switch (GET_CODE (x))
     357                 :            :       {
     358                 :     185074 :       case ASHIFT:
     359                 :     185074 :         if (CONST_INT_P (XEXP (x, 1))
     360                 :     370140 :             && INTVAL (XEXP (x, 1)) < GET_MODE_UNIT_BITSIZE (GET_MODE (x))
     361                 :     370144 :             && INTVAL (XEXP (x, 1)) >= 0)
     362                 :            :           {
     363                 :     185070 :             HOST_WIDE_INT shift = INTVAL (XEXP (x, 1));
     364                 :     185070 :             PUT_CODE (x, MULT);
     365                 :     185070 :             XEXP (x, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift,
     366                 :            :                                         GET_MODE (x));
     367                 :            :           }
     368                 :            : 
     369                 :     185074 :         x = XEXP (x, 0);
     370                 :     185074 :         break;
     371                 :            : 
     372                 :    1316840 :       case PLUS:
     373                 :    1316840 :         if (GET_CODE (XEXP (x, 0)) == PLUS
     374                 :    1316840 :             || GET_CODE (XEXP (x, 0)) == ASHIFT
     375                 :     949908 :             || GET_CODE (XEXP (x, 0)) == CONST)
     376                 :     366932 :           canonicalize_address (XEXP (x, 0));
     377                 :            : 
     378                 :    1316840 :         x = XEXP (x, 1);
     379                 :    1316840 :         break;
     380                 :            : 
     381                 :     366631 :       case CONST:
     382                 :     366631 :         x = XEXP (x, 0);
     383                 :     366631 :         break;
     384                 :            : 
     385                 :    1710840 :       default:
     386                 :    1710840 :         return;
     387                 :            :       }
     388                 :            : }
     389                 :            : 
     390                 :            : /* OLD is a memory address.  Return whether it is good to use NEW instead,
     391                 :            :    for a memory access in the given MODE.  */
     392                 :            : 
     393                 :            : static bool
     394                 :    1286050 : should_replace_address (rtx old_rtx, rtx new_rtx, machine_mode mode,
     395                 :            :                         addr_space_t as, bool speed)
     396                 :            : {
     397                 :    1286050 :   int gain;
     398                 :            : 
     399                 :    1286050 :   if (rtx_equal_p (old_rtx, new_rtx)
     400                 :    1286050 :       || !memory_address_addr_space_p (mode, new_rtx, as))
     401                 :     243016 :     return false;
     402                 :            : 
     403                 :            :   /* Copy propagation is always ok.  */
     404                 :    1043030 :   if (REG_P (old_rtx) && REG_P (new_rtx))
     405                 :            :     return true;
     406                 :            : 
     407                 :            :   /* Prefer the new address if it is less expensive.  */
     408                 :    1043030 :   gain = (address_cost (old_rtx, mode, as, speed)
     409                 :    1043030 :           - address_cost (new_rtx, mode, as, speed));
     410                 :            : 
     411                 :            :   /* If the addresses have equivalent cost, prefer the new address
     412                 :            :      if it has the highest `set_src_cost'.  That has the potential of
     413                 :            :      eliminating the most insns without additional costs, and it
     414                 :            :      is the same that cse.c used to do.  */
     415                 :    1043030 :   if (gain == 0)
     416                 :     126824 :     gain = (set_src_cost (new_rtx, VOIDmode, speed)
     417                 :     126824 :             - set_src_cost (old_rtx, VOIDmode, speed));
     418                 :            : 
     419                 :    1043030 :   return (gain > 0);
     420                 :            : }
     421                 :            : 
     422                 :            : 
     423                 :            : /* Flags for the last parameter of propagate_rtx_1.  */
     424                 :            : 
     425                 :            : enum {
     426                 :            :   /* If PR_CAN_APPEAR is true, propagate_rtx_1 always returns true;
     427                 :            :      if it is false, propagate_rtx_1 returns false if, for at least
     428                 :            :      one occurrence OLD, it failed to collapse the result to a constant.
     429                 :            :      For example, (mult:M (reg:M A) (minus:M (reg:M B) (reg:M A))) may
     430                 :            :      collapse to zero if replacing (reg:M B) with (reg:M A).
     431                 :            : 
     432                 :            :      PR_CAN_APPEAR is disregarded inside MEMs: in that case,
     433                 :            :      propagate_rtx_1 just tries to make cheaper and valid memory
     434                 :            :      addresses.  */
     435                 :            :   PR_CAN_APPEAR = 1,
     436                 :            : 
     437                 :            :   /* If PR_HANDLE_MEM is not set, propagate_rtx_1 won't attempt any replacement
     438                 :            :      outside memory addresses.  This is needed because propagate_rtx_1 does
     439                 :            :      not do any analysis on memory; thus it is very conservative and in general
     440                 :            :      it will fail if non-read-only MEMs are found in the source expression.
     441                 :            : 
     442                 :            :      PR_HANDLE_MEM is set when the source of the propagation was not
     443                 :            :      another MEM.  Then, it is safe not to treat non-read-only MEMs as
     444                 :            :      ``opaque'' objects.  */
     445                 :            :   PR_HANDLE_MEM = 2,
     446                 :            : 
     447                 :            :   /* Set when costs should be optimized for speed.  */
     448                 :            :   PR_OPTIMIZE_FOR_SPEED = 4
     449                 :            : };
     450                 :            : 
     451                 :            : /* Check that X has a single def.  */
     452                 :            : 
     453                 :            : static bool
     454                 :   31272900 : reg_single_def_p (rtx x)
     455                 :            : {
     456                 :   31272900 :   if (!REG_P (x))
     457                 :            :     return false;
     458                 :            : 
     459                 :    7295940 :   int regno = REGNO (x);
     460                 :    7295940 :   return (DF_REG_DEF_COUNT (regno) == 1
     461                 :    8738900 :           && !bitmap_bit_p (DF_LR_OUT (ENTRY_BLOCK_PTR_FOR_FN (cfun)), regno));
     462                 :            : }
     463                 :            : 
     464                 :            : /* Replace all occurrences of OLD in *PX with NEW and try to simplify the
     465                 :            :    resulting expression.  Replace *PX with a new RTL expression if an
     466                 :            :    occurrence of OLD was found.
     467                 :            : 
     468                 :            :    This is only a wrapper around simplify-rtx.c: do not add any pattern
     469                 :            :    matching code here.  (The sole exception is the handling of LO_SUM, but
     470                 :            :    that is because there is no simplify_gen_* function for LO_SUM).  */
     471                 :            : 
     472                 :            : static bool
     473                 :   41318100 : propagate_rtx_1 (rtx *px, rtx old_rtx, rtx new_rtx, int flags)
     474                 :            : {
     475                 :   41318100 :   rtx x = *px, tem = NULL_RTX, op0, op1, op2;
     476                 :   41318100 :   enum rtx_code code = GET_CODE (x);
     477                 :   41318100 :   machine_mode mode = GET_MODE (x);
     478                 :   41318100 :   machine_mode op_mode;
     479                 :   41318100 :   bool can_appear = (flags & PR_CAN_APPEAR) != 0;
     480                 :   41318100 :   bool valid_ops = true;
     481                 :            : 
     482                 :   41318100 :   if (!(flags & PR_HANDLE_MEM) && MEM_P (x) && !MEM_READONLY_P (x))
     483                 :            :     {
     484                 :            :       /* If unsafe, change MEMs to CLOBBERs or SCRATCHes (to preserve whether
     485                 :            :          they have side effects or not).  */
     486                 :    1005940 :       *px = (side_effects_p (x)
     487                 :    1005940 :              ? gen_rtx_CLOBBER (GET_MODE (x), const0_rtx)
     488                 :    1001050 :              : gen_rtx_SCRATCH (GET_MODE (x)));
     489                 :    1005940 :       return false;
     490                 :            :     }
     491                 :            : 
     492                 :            :   /* If X is OLD_RTX, return NEW_RTX.  But not if replacing only within an
     493                 :            :      address, and we are *not* inside one.  */
     494                 :   40312200 :   if (x == old_rtx)
     495                 :            :     {
     496                 :   16567500 :       *px = new_rtx;
     497                 :   16567500 :       return can_appear;
     498                 :            :     }
     499                 :            : 
     500                 :            :   /* If this is an expression, try recursive substitution.  */
     501                 :   23744700 :   switch (GET_RTX_CLASS (code))
     502                 :            :     {
     503                 :     847712 :     case RTX_UNARY:
     504                 :     847712 :       op0 = XEXP (x, 0);
     505                 :     847712 :       op_mode = GET_MODE (op0);
     506                 :     847712 :       valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
     507                 :     847712 :       if (op0 == XEXP (x, 0))
     508                 :            :         return true;
     509                 :     676032 :       tem = simplify_gen_unary (code, mode, op0, op_mode);
     510                 :     676032 :       break;
     511                 :            : 
     512                 :    8145360 :     case RTX_BIN_ARITH:
     513                 :    8145360 :     case RTX_COMM_ARITH:
     514                 :    8145360 :       op0 = XEXP (x, 0);
     515                 :    8145360 :       op1 = XEXP (x, 1);
     516                 :    8145360 :       valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
     517                 :    8145360 :       valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
     518                 :    8145360 :       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
     519                 :            :         return true;
     520                 :    7887780 :       tem = simplify_gen_binary (code, mode, op0, op1);
     521                 :    7887780 :       break;
     522                 :            : 
     523                 :     366553 :     case RTX_COMPARE:
     524                 :     366553 :     case RTX_COMM_COMPARE:
     525                 :     366553 :       op0 = XEXP (x, 0);
     526                 :     366553 :       op1 = XEXP (x, 1);
     527                 :     366553 :       op_mode = GET_MODE (op0) != VOIDmode ? GET_MODE (op0) : GET_MODE (op1);
     528                 :     366553 :       valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
     529                 :     366553 :       valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
     530                 :     366553 :       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
     531                 :            :         return true;
     532                 :     121598 :       tem = simplify_gen_relational (code, mode, op_mode, op0, op1);
     533                 :     121598 :       break;
     534                 :            : 
     535                 :     405887 :     case RTX_TERNARY:
     536                 :     405887 :     case RTX_BITFIELD_OPS:
     537                 :     405887 :       op0 = XEXP (x, 0);
     538                 :     405887 :       op1 = XEXP (x, 1);
     539                 :     405887 :       op2 = XEXP (x, 2);
     540                 :     405887 :       op_mode = GET_MODE (op0);
     541                 :     405887 :       valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
     542                 :     405887 :       valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
     543                 :     405887 :       valid_ops &= propagate_rtx_1 (&op2, old_rtx, new_rtx, flags);
     544                 :     405887 :       if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1) && op2 == XEXP (x, 2))
     545                 :            :         return true;
     546                 :     397391 :       if (op_mode == VOIDmode)
     547                 :     243927 :         op_mode = GET_MODE (op0);
     548                 :     397391 :       tem = simplify_gen_ternary (code, mode, op_mode, op0, op1, op2);
     549                 :     397391 :       break;
     550                 :            : 
     551                 :    1769300 :     case RTX_EXTRA:
     552                 :            :       /* The only case we try to handle is a SUBREG.  */
     553                 :    1769300 :       if (code == SUBREG)
     554                 :            :         {
     555                 :    1132300 :           op0 = XEXP (x, 0);
     556                 :    1132300 :           valid_ops &= propagate_rtx_1 (&op0, old_rtx, new_rtx, flags);
     557                 :    1132300 :           if (op0 == XEXP (x, 0))
     558                 :            :             return true;
     559                 :     795359 :           tem = simplify_gen_subreg (mode, op0, GET_MODE (SUBREG_REG (x)),
     560                 :     795359 :                                      SUBREG_BYTE (x));
     561                 :            :         }
     562                 :            : 
     563                 :            :       else
     564                 :            :         {
     565                 :     636994 :           rtvec vec;
     566                 :     636994 :           rtvec newvec;
     567                 :     636994 :           const char *fmt = GET_RTX_FORMAT (code);
     568                 :     636994 :           rtx op;
     569                 :            : 
     570                 :    1693960 :           for (int i = 0; fmt[i]; i++)
     571                 :    1056960 :             switch (fmt[i])
     572                 :            :               {
     573                 :     563780 :               case 'E':
     574                 :     563780 :                 vec = XVEC (x, i);
     575                 :     563780 :                 newvec = vec;
     576                 :    2055270 :                 for (int j = 0; j < GET_NUM_ELEM (vec); j++)
     577                 :            :                   {
     578                 :    1491490 :                     op = RTVEC_ELT (vec, j);
     579                 :    1491490 :                     valid_ops &= propagate_rtx_1 (&op, old_rtx, new_rtx, flags);
     580                 :    1491490 :                     if (op != RTVEC_ELT (vec, j))
     581                 :            :                       {
     582                 :     327171 :                         if (newvec == vec)
     583                 :            :                           {
     584                 :     324437 :                             newvec = shallow_copy_rtvec (vec);
     585                 :     324437 :                             if (!tem)
     586                 :     324437 :                               tem = shallow_copy_rtx (x);
     587                 :     324437 :                             XVEC (tem, i) = newvec;
     588                 :            :                           }
     589                 :     327171 :                         RTVEC_ELT (newvec, j) = op;
     590                 :            :                       }
     591                 :            :                   }
     592                 :            :                 break;
     593                 :            : 
     594                 :     146428 :               case 'e':
     595                 :     146428 :                 if (XEXP (x, i))
     596                 :            :                   {
     597                 :     146428 :                     op = XEXP (x, i);
     598                 :     146428 :                     valid_ops &= propagate_rtx_1 (&op, old_rtx, new_rtx, flags);
     599                 :     146428 :                     if (op != XEXP (x, i))
     600                 :            :                       {
     601                 :      66339 :                         if (!tem)
     602                 :      66339 :                           tem = shallow_copy_rtx (x);
     603                 :      66339 :                         XEXP (tem, i) = op;
     604                 :            :                       }
     605                 :            :                   }
     606                 :            :                 break;
     607                 :            :               }
     608                 :            :         }
     609                 :            : 
     610                 :            :       break;
     611                 :            : 
     612                 :    7115140 :     case RTX_OBJ:
     613                 :    7115140 :       if (code == MEM && x != new_rtx)
     614                 :            :         {
     615                 :    1574480 :           rtx new_op0;
     616                 :    1574480 :           op0 = XEXP (x, 0);
     617                 :            : 
     618                 :            :           /* There are some addresses that we cannot work on.  */
     619                 :    1574480 :           if (!can_simplify_addr (op0))
     620                 :     696871 :             return true;
     621                 :            : 
     622                 :    1495280 :           op0 = new_op0 = targetm.delegitimize_address (op0);
     623                 :    1495280 :           valid_ops &= propagate_rtx_1 (&new_op0, old_rtx, new_rtx,
     624                 :            :                                         flags | PR_CAN_APPEAR);
     625                 :            : 
     626                 :            :           /* Dismiss transformation that we do not want to carry on.  */
     627                 :    1495280 :           if (!valid_ops
     628                 :    1495280 :               || new_op0 == op0
     629                 :    1343910 :               || !(GET_MODE (new_op0) == GET_MODE (op0)
     630                 :            :                    || GET_MODE (new_op0) == VOIDmode))
     631                 :            :             return true;
     632                 :            : 
     633                 :    1343910 :           canonicalize_address (new_op0);
     634                 :            : 
     635                 :            :           /* Copy propagations are always ok.  Otherwise check the costs.  */
     636                 :    1343910 :           if (!(REG_P (old_rtx) && REG_P (new_rtx))
     637                 :    2629960 :               && !should_replace_address (op0, new_op0, GET_MODE (x),
     638                 :    1286050 :                                           MEM_ADDR_SPACE (x),
     639                 :    1286050 :                                           flags & PR_OPTIMIZE_FOR_SPEED))
     640                 :            :             return true;
     641                 :            : 
     642                 :     877613 :           tem = replace_equiv_address_nv (x, new_op0);
     643                 :            :         }
     644                 :            : 
     645                 :    5540660 :       else if (code == LO_SUM)
     646                 :            :         {
     647                 :          0 :           op0 = XEXP (x, 0);
     648                 :          0 :           op1 = XEXP (x, 1);
     649                 :            : 
     650                 :            :           /* The only simplification we do attempts to remove references to op0
     651                 :            :              or make it constant -- in both cases, op0's invalidity will not
     652                 :            :              make the result invalid.  */
     653                 :          0 :           propagate_rtx_1 (&op0, old_rtx, new_rtx, flags | PR_CAN_APPEAR);
     654                 :          0 :           valid_ops &= propagate_rtx_1 (&op1, old_rtx, new_rtx, flags);
     655                 :          0 :           if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
     656                 :            :             return true;
     657                 :            : 
     658                 :            :           /* (lo_sum (high x) x) -> x  */
     659                 :          0 :           if (GET_CODE (op0) == HIGH && rtx_equal_p (XEXP (op0, 0), op1))
     660                 :          0 :             tem = op1;
     661                 :            :           else
     662                 :          0 :             tem = gen_rtx_LO_SUM (mode, op0, op1);
     663                 :            : 
     664                 :            :           /* OP1 is likely not a legitimate address, otherwise there would have
     665                 :            :              been no LO_SUM.  We want it to disappear if it is invalid, return
     666                 :            :              false in that case.  */
     667                 :          0 :           return memory_address_p (mode, tem);
     668                 :            :         }
     669                 :            : 
     670                 :    5540660 :       else if (code == REG)
     671                 :            :         {
     672                 :    5490700 :           if (rtx_equal_p (x, old_rtx))
     673                 :            :             {
     674                 :     549569 :               *px = new_rtx;
     675                 :     549569 :               return can_appear;
     676                 :            :             }
     677                 :            :         }
     678                 :            :       break;
     679                 :            : 
     680                 :            :     default:
     681                 :            :       break;
     682                 :            :     }
     683                 :            : 
     684                 :            :   /* No change, no trouble.  */
     685                 :   11392800 :   if (tem == NULL_RTX)
     686                 :   10335100 :     return true;
     687                 :            : 
     688                 :   11143500 :   *px = tem;
     689                 :            : 
     690                 :            :   /* Allow replacements that simplify operations on a vector or complex
     691                 :            :      value to a component.  The most prominent case is
     692                 :            :      (subreg ([vec_]concat ...)).   */
     693                 :      21676 :   if (REG_P (tem) && !HARD_REGISTER_P (tem)
     694                 :      20572 :       && (VECTOR_MODE_P (GET_MODE (new_rtx))
     695                 :      18994 :           || COMPLEX_MODE_P (GET_MODE (new_rtx)))
     696                 :   11146700 :       && GET_MODE (tem) == GET_MODE_INNER (GET_MODE (new_rtx)))
     697                 :            :     return true;
     698                 :            : 
     699                 :            :   /* The replacement we made so far is valid, if all of the recursive
     700                 :            :      replacements were valid, or we could simplify everything to
     701                 :            :      a constant.  */
     702                 :   11143200 :   return valid_ops || can_appear || CONSTANT_P (tem);
     703                 :            : }
     704                 :            : 
     705                 :            : 
     706                 :            : /* Return true if X constains a non-constant mem.  */
     707                 :            : 
     708                 :            : static bool
     709                 :   17963400 : varying_mem_p (const_rtx x)
     710                 :            : {
     711                 :   17963400 :   subrtx_iterator::array_type array;
     712                 :   47226800 :   FOR_EACH_SUBRTX (iter, array, x, NONCONST)
     713                 :   36752800 :     if (MEM_P (*iter) && !MEM_READONLY_P (*iter))
     714                 :    7489480 :       return true;
     715                 :   10473900 :   return false;
     716                 :            : }
     717                 :            : 
     718                 :            : 
     719                 :            : /* Replace all occurrences of OLD in X with NEW and try to simplify the
     720                 :            :    resulting expression (in mode MODE).  Return a new expression if it is
     721                 :            :    a constant, otherwise X.
     722                 :            : 
     723                 :            :    Simplifications where occurrences of NEW collapse to a constant are always
     724                 :            :    accepted.  All simplifications are accepted if NEW is a pseudo too.
     725                 :            :    Otherwise, we accept simplifications that have a lower or equal cost.  */
     726                 :            : 
     727                 :            : static rtx
     728                 :   21560400 : propagate_rtx (rtx x, machine_mode mode, rtx old_rtx, rtx new_rtx,
     729                 :            :                bool speed)
     730                 :            : {
     731                 :   21560400 :   rtx tem;
     732                 :   21560400 :   bool collapsed;
     733                 :   21560400 :   int flags;
     734                 :            : 
     735                 :   21560400 :   if (REG_P (new_rtx) && REGNO (new_rtx) < FIRST_PSEUDO_REGISTER)
     736                 :            :     return NULL_RTX;
     737                 :            : 
     738                 :   17963400 :   flags = 0;
     739                 :   17963400 :   if (REG_P (new_rtx)
     740                 :   17082200 :       || CONSTANT_P (new_rtx)
     741                 :   33699000 :       || (GET_CODE (new_rtx) == SUBREG
     742                 :     408069 :           && REG_P (SUBREG_REG (new_rtx))
     743                 :     407407 :           && !paradoxical_subreg_p (new_rtx)))
     744                 :            :     flags |= PR_CAN_APPEAR;
     745                 :   17963400 :   if (!varying_mem_p (new_rtx))
     746                 :   10473900 :     flags |= PR_HANDLE_MEM;
     747                 :            : 
     748                 :   17963400 :   if (speed)
     749                 :   16383300 :     flags |= PR_OPTIMIZE_FOR_SPEED;
     750                 :            : 
     751                 :   17963400 :   tem = x;
     752                 :   17963400 :   collapsed = propagate_rtx_1 (&tem, old_rtx, copy_rtx (new_rtx), flags);
     753                 :   17963400 :   if (tem == x || !collapsed)
     754                 :            :     return NULL_RTX;
     755                 :            : 
     756                 :            :   /* gen_lowpart_common will not be able to process VOIDmode entities other
     757                 :            :      than CONST_INTs.  */
     758                 :    2669590 :   if (GET_MODE (tem) == VOIDmode && !CONST_INT_P (tem))
     759                 :            :     return NULL_RTX;
     760                 :            : 
     761                 :    2668350 :   if (GET_MODE (tem) == VOIDmode)
     762                 :     196623 :     tem = rtl_hooks.gen_lowpart_no_emit (mode, tem);
     763                 :            :   else
     764                 :    2471730 :     gcc_assert (GET_MODE (tem) == mode);
     765                 :            : 
     766                 :    2668350 :   return tem;
     767                 :            : }
     768                 :            : 
     769                 :            : 
     770                 :            : 
     771                 :            : 
     772                 :            : /* Return true if the register from reference REF is killed
     773                 :            :    between FROM to (but not including) TO.  */
     774                 :            : 
     775                 :            : static bool
     776                 :    5540090 : local_ref_killed_between_p (df_ref ref, rtx_insn *from, rtx_insn *to)
     777                 :            : {
     778                 :    5540090 :   rtx_insn *insn;
     779                 :            : 
     780                 :  202928000 :   for (insn = from; insn != to; insn = NEXT_INSN (insn))
     781                 :            :     {
     782                 :   99126600 :       df_ref def;
     783                 :   99126600 :       if (!INSN_P (insn))
     784                 :    1609560 :         continue;
     785                 :            : 
     786                 :  371097000 :       FOR_EACH_INSN_DEF (def, insn)
     787                 :  274013000 :         if (DF_REF_REGNO (ref) == DF_REF_REGNO (def))
     788                 :            :           return true;
     789                 :            :     }
     790                 :            :   return false;
     791                 :            : }
     792                 :            : 
     793                 :            : 
     794                 :            : /* Check if USE is killed between DEF_INSN and TARGET_INSN.  This would
     795                 :            :    require full computation of available expressions; we check only a few
     796                 :            :    restricted conditions:
     797                 :            :    - if the reg in USE has only one definition, go ahead;
     798                 :            :    - in the same basic block, we check for no definitions killing the use;
     799                 :            :    - if TARGET_INSN's basic block has DEF_INSN's basic block as its sole
     800                 :            :      predecessor, we check if the use is killed after DEF_INSN or before
     801                 :            :      TARGET_INSN insn, in their respective basic blocks.  */
     802                 :            : 
     803                 :            : static bool
     804                 :   19322000 : use_killed_between (df_ref use, rtx_insn *def_insn, rtx_insn *target_insn)
     805                 :            : {
     806                 :   19322000 :   basic_block def_bb = BLOCK_FOR_INSN (def_insn);
     807                 :   19322000 :   basic_block target_bb = BLOCK_FOR_INSN (target_insn);
     808                 :   19322000 :   int regno;
     809                 :   19322000 :   df_ref def;
     810                 :            : 
     811                 :            :   /* We used to have a def reaching a use that is _before_ the def,
     812                 :            :      with the def not dominating the use even though the use and def
     813                 :            :      are in the same basic block, when a register may be used
     814                 :            :      uninitialized in a loop.  This should not happen anymore since
     815                 :            :      we do not use reaching definitions, but still we test for such
     816                 :            :      cases and assume that DEF is not available.  */
     817                 :   19322000 :   if (def_bb == target_bb
     818                 :   28385000 :       ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn)
     819                 :    9063040 :       : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb))
     820                 :            :     return true;
     821                 :            : 
     822                 :            :   /* Check if the reg in USE has only one definition.  We already
     823                 :            :      know that this definition reaches use, or we wouldn't be here.
     824                 :            :      However, this is invalid for hard registers because if they are
     825                 :            :      live at the beginning of the function it does not mean that we
     826                 :            :      have an uninitialized access.  And we have to check for the case
     827                 :            :      where a register may be used uninitialized in a loop as above.  */
     828                 :   19316900 :   regno = DF_REF_REGNO (use);
     829                 :   19316900 :   def = DF_REG_DEF_CHAIN (regno);
     830                 :   19316900 :   if (def
     831                 :   19220900 :       && DF_REF_NEXT_REG (def) == NULL
     832                 :   12626600 :       && regno >= FIRST_PSEUDO_REGISTER
     833                 :   27438900 :       && (BLOCK_FOR_INSN (DF_REF_INSN (def)) == def_bb
     834                 :    8122000 :           ? DF_INSN_LUID (DF_REF_INSN (def)) < DF_INSN_LUID (def_insn)
     835                 :    2396180 :           : dominated_by_p (CDI_DOMINATORS,
     836                 :    2396180 :                             def_bb, BLOCK_FOR_INSN (DF_REF_INSN (def)))))
     837                 :    8115860 :     return false;
     838                 :            : 
     839                 :            :   /* Check locally if we are in the same basic block.  */
     840                 :   11201000 :   if (def_bb == target_bb)
     841                 :    5540090 :     return local_ref_killed_between_p (use, def_insn, target_insn);
     842                 :            : 
     843                 :            :   /* Finally, if DEF_BB is the sole predecessor of TARGET_BB.  */
     844                 :    5660930 :   if (single_pred_p (target_bb)
     845                 :   10021500 :       && single_pred (target_bb) == def_bb)
     846                 :            :     {
     847                 :    2219040 :       df_ref x;
     848                 :            : 
     849                 :            :       /* See if USE is killed between DEF_INSN and the last insn in the
     850                 :            :          basic block containing DEF_INSN.  */
     851                 :    2219040 :       x = df_bb_regno_last_def_find (def_bb, regno);
     852                 :    2219040 :       if (x && DF_INSN_LUID (DF_REF_INSN (x)) >= DF_INSN_LUID (def_insn))
     853                 :            :         return true;
     854                 :            : 
     855                 :            :       /* See if USE is killed between TARGET_INSN and the first insn in the
     856                 :            :          basic block containing TARGET_INSN.  */
     857                 :    2011710 :       x = df_bb_regno_first_def_find (target_bb, regno);
     858                 :    2011710 :       if (x && DF_INSN_LUID (DF_REF_INSN (x)) < DF_INSN_LUID (target_insn))
     859                 :     134741 :         return true;
     860                 :            : 
     861                 :            :       return false;
     862                 :            :     }
     863                 :            : 
     864                 :            :   /* Otherwise assume the worst case.  */
     865                 :            :   return true;
     866                 :            : }
     867                 :            : 
     868                 :            : 
     869                 :            : /* Check if all uses in DEF_INSN can be used in TARGET_INSN.  This
     870                 :            :    would require full computation of available expressions;
     871                 :            :    we check only restricted conditions, see use_killed_between.  */
     872                 :            : static bool
     873                 :   27413500 : all_uses_available_at (rtx_insn *def_insn, rtx_insn *target_insn)
     874                 :            : {
     875                 :   27413500 :   df_ref use;
     876                 :   27413500 :   struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn);
     877                 :   27413500 :   rtx def_set = single_set (def_insn);
     878                 :   27413500 :   rtx_insn *next;
     879                 :            : 
     880                 :   27413500 :   gcc_assert (def_set);
     881                 :            : 
     882                 :            :   /* If target_insn comes right after def_insn, which is very common
     883                 :            :      for addresses, we can use a quicker test.  Ignore debug insns
     884                 :            :      other than target insns for this.  */
     885                 :   27413500 :   next = NEXT_INSN (def_insn);
     886                 :   48511000 :   while (next && next != target_insn && DEBUG_INSN_P (next))
     887                 :   21097500 :     next = NEXT_INSN (next);
     888                 :   27413500 :   if (next == target_insn && REG_P (SET_DEST (def_set)))
     889                 :            :     {
     890                 :    9626480 :       rtx def_reg = SET_DEST (def_set);
     891                 :            : 
     892                 :            :       /* If the insn uses the reg that it defines, the substitution is
     893                 :            :          invalid.  */
     894                 :   20394000 :       FOR_EACH_INSN_INFO_USE (use, insn_info)
     895                 :   11862300 :         if (rtx_equal_p (DF_REF_REG (use), def_reg))
     896                 :            :           return false;
     897                 :    9033750 :       FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
     898                 :     501972 :         if (rtx_equal_p (DF_REF_REG (use), def_reg))
     899                 :            :           return false;
     900                 :            :     }
     901                 :            :   else
     902                 :            :     {
     903                 :   17787000 :       rtx def_reg = REG_P (SET_DEST (def_set)) ? SET_DEST (def_set) : NULL_RTX;
     904                 :            : 
     905                 :            :       /* Look at all the uses of DEF_INSN, and see if they are not
     906                 :            :          killed between DEF_INSN and TARGET_INSN.  */
     907                 :   32269800 :       FOR_EACH_INSN_INFO_USE (use, insn_info)
     908                 :            :         {
     909                 :   19542400 :           if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
     910                 :            :             return false;
     911                 :   18698400 :           if (use_killed_between (use, def_insn, target_insn))
     912                 :            :             return false;
     913                 :            :         }
     914                 :   13344800 :       FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
     915                 :            :         {
     916                 :     623552 :           if (def_reg && rtx_equal_p (DF_REF_REG (use), def_reg))
     917                 :            :             return false;
     918                 :     623552 :           if (use_killed_between (use, def_insn, target_insn))
     919                 :            :             return false;
     920                 :            :         }
     921                 :            :     }
     922                 :            : 
     923                 :            :   return true;
     924                 :            : }
     925                 :            : 
     926                 :            : 
     927                 :            : static df_ref *active_defs;
     928                 :            : static sparseset active_defs_check;
     929                 :            : 
     930                 :            : /* Fill the ACTIVE_DEFS array with the use->def link for the registers
     931                 :            :    mentioned in USE_REC.  Register the valid entries in ACTIVE_DEFS_CHECK
     932                 :            :    too, for checking purposes.  */
     933                 :            : 
     934                 :            : static void
     935                 :    8058490 : register_active_defs (df_ref use)
     936                 :            : {
     937                 :   14711100 :   for (; use; use = DF_REF_NEXT_LOC (use))
     938                 :            :     {
     939                 :    6652620 :       df_ref def = get_def_for_use (use);
     940                 :    6652620 :       int regno = DF_REF_REGNO (use);
     941                 :            : 
     942                 :    6652620 :       if (flag_checking)
     943                 :    6652600 :         sparseset_set_bit (active_defs_check, regno);
     944                 :    6652620 :       active_defs[regno] = def;
     945                 :            :     }
     946                 :    8058490 : }
     947                 :            : 
     948                 :            : 
     949                 :            : /* Build the use->def links that we use to update the dataflow info
     950                 :            :    for new uses.  Note that building the links is very cheap and if
     951                 :            :    it were done earlier, they could be used to rule out invalid
     952                 :            :    propagations (in addition to what is done in all_uses_available_at).
     953                 :            :    I'm not doing this yet, though.  */
     954                 :            : 
     955                 :            : static void
     956                 :    2686160 : update_df_init (rtx_insn *def_insn, rtx_insn *insn)
     957                 :            : {
     958                 :    2686160 :   if (flag_checking)
     959                 :    2686160 :     sparseset_clear (active_defs_check);
     960                 :    2686160 :   register_active_defs (DF_INSN_USES (def_insn));
     961                 :    2686160 :   register_active_defs (DF_INSN_USES (insn));
     962                 :    2686160 :   register_active_defs (DF_INSN_EQ_USES (insn));
     963                 :    2686160 : }
     964                 :            : 
     965                 :            : 
     966                 :            : /* Update the USE_DEF_REF array for the given use, using the active definitions
     967                 :            :    in the ACTIVE_DEFS array to match pseudos to their def. */
     968                 :            : 
     969                 :            : static inline void
     970                 :    4083160 : update_uses (df_ref use)
     971                 :            : {
     972                 :    9346420 :   for (; use; use = DF_REF_NEXT_LOC (use))
     973                 :            :     {
     974                 :    5263270 :       int regno = DF_REF_REGNO (use);
     975                 :            : 
     976                 :            :       /* Set up the use-def chain.  */
     977                 :   10526500 :       if (DF_REF_ID (use) >= (int) use_def_ref.length ())
     978                 :    1915040 :         use_def_ref.safe_grow_cleared (DF_REF_ID (use) + 1);
     979                 :            : 
     980                 :    5263270 :       if (flag_checking)
     981                 :    5263260 :         gcc_assert (sparseset_bit_p (active_defs_check, regno));
     982                 :    5263270 :       use_def_ref[DF_REF_ID (use)] = active_defs[regno];
     983                 :            :     }
     984                 :    4083160 : }
     985                 :            : 
     986                 :            : 
     987                 :            : /* Update the USE_DEF_REF array for the uses in INSN.  Only update note
     988                 :            :    uses if NOTES_ONLY is true.  */
     989                 :            : 
     990                 :            : static void
     991                 :    2153770 : update_df (rtx_insn *insn, rtx note)
     992                 :            : {
     993                 :    2153770 :   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
     994                 :            : 
     995                 :    2153770 :   if (note)
     996                 :            :     {
     997                 :     224392 :       df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
     998                 :     224392 :       df_notes_rescan (insn);
     999                 :            :     }
    1000                 :            :   else
    1001                 :            :     {
    1002                 :    1929380 :       df_uses_create (&PATTERN (insn), insn, 0);
    1003                 :    1929380 :       df_insn_rescan (insn);
    1004                 :    1929380 :       update_uses (DF_INSN_INFO_USES (insn_info));
    1005                 :            :     }
    1006                 :            : 
    1007                 :    2153770 :   update_uses (DF_INSN_INFO_EQ_USES (insn_info));
    1008                 :    2153770 : }
    1009                 :            : 
    1010                 :            : 
    1011                 :            : /* Try substituting NEW into LOC, which originated from forward propagation
    1012                 :            :    of USE's value from DEF_INSN.  SET_REG_EQUAL says whether we are
    1013                 :            :    substituting the whole SET_SRC, so we can set a REG_EQUAL note if the
    1014                 :            :    new insn is not recognized.  Return whether the substitution was
    1015                 :            :    performed.  */
    1016                 :            : 
    1017                 :            : static bool
    1018                 :    2627260 : try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx_insn *def_insn,
    1019                 :            :                   bool set_reg_equal)
    1020                 :            : {
    1021                 :    2627260 :   rtx_insn *insn = DF_REF_INSN (use);
    1022                 :    2627260 :   rtx set = single_set (insn);
    1023                 :    2627260 :   rtx note = NULL_RTX;
    1024                 :    2627260 :   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
    1025                 :    2627260 :   int old_cost = 0;
    1026                 :    2627260 :   bool ok;
    1027                 :            : 
    1028                 :    2627260 :   update_df_init (def_insn, insn);
    1029                 :            : 
    1030                 :            :   /* forward_propagate_subreg may be operating on an instruction with
    1031                 :            :      multiple sets.  If so, assume the cost of the new instruction is
    1032                 :            :      not greater than the old one.  */
    1033                 :    2627260 :   if (set)
    1034                 :    2366220 :     old_cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed);
    1035                 :    2627260 :   if (dump_file)
    1036                 :            :     {
    1037                 :         78 :       fprintf (dump_file, "\nIn insn %d, replacing\n ", INSN_UID (insn));
    1038                 :         78 :       print_inline_rtx (dump_file, *loc, 2);
    1039                 :         78 :       fprintf (dump_file, "\n with ");
    1040                 :         78 :       print_inline_rtx (dump_file, new_rtx, 2);
    1041                 :         78 :       fprintf (dump_file, "\n");
    1042                 :            :     }
    1043                 :            : 
    1044                 :    2627260 :   validate_unshare_change (insn, loc, new_rtx, true);
    1045                 :    2627260 :   if (!verify_changes (0))
    1046                 :            :     {
    1047                 :     387153 :       if (dump_file)
    1048                 :          2 :         fprintf (dump_file, "Changes to insn %d not recognized\n",
    1049                 :          2 :                  INSN_UID (insn));
    1050                 :            :       ok = false;
    1051                 :            :     }
    1052                 :            : 
    1053                 :    2240110 :   else if (DF_REF_TYPE (use) == DF_REF_REG_USE
    1054                 :    1414750 :            && set
    1055                 :    3395120 :            && (set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)), speed)
    1056                 :            :                > old_cost))
    1057                 :            :     {
    1058                 :     278585 :       if (dump_file)
    1059                 :          0 :         fprintf (dump_file, "Changes to insn %d not profitable\n",
    1060                 :          0 :                  INSN_UID (insn));
    1061                 :            :       ok = false;
    1062                 :            :     }
    1063                 :            : 
    1064                 :            :   else
    1065                 :            :     {
    1066                 :    1961520 :       if (dump_file)
    1067                 :         76 :         fprintf (dump_file, "Changed insn %d\n", INSN_UID (insn));
    1068                 :    1961520 :       ok = true;
    1069                 :            :     }
    1070                 :            : 
    1071                 :    1961520 :   if (ok)
    1072                 :            :     {
    1073                 :    1961520 :       confirm_change_group ();
    1074                 :    1961520 :       num_changes++;
    1075                 :            :     }
    1076                 :            :   else
    1077                 :            :     {
    1078                 :     665738 :       cancel_changes (0);
    1079                 :            : 
    1080                 :            :       /* Can also record a simplified value in a REG_EQUAL note,
    1081                 :            :          making a new one if one does not already exist.  */
    1082                 :     665738 :       if (set_reg_equal)
    1083                 :            :         {
    1084                 :            :           /* If there are any paradoxical SUBREGs, don't add REG_EQUAL note,
    1085                 :            :              because the bits in there can be anything and so might not
    1086                 :            :              match the REG_EQUAL note content.  See PR70574.  */
    1087                 :     534546 :           subrtx_var_iterator::array_type array;
    1088                 :    1472820 :           FOR_EACH_SUBRTX_VAR (iter, array, *loc, NONCONST)
    1089                 :            :             {
    1090                 :    1205550 :               rtx x = *iter;
    1091                 :    1205550 :               if (SUBREG_P (x) && paradoxical_subreg_p (x))
    1092                 :            :                 {
    1093                 :            :                   set_reg_equal = false;
    1094                 :            :                   break;
    1095                 :            :                 }
    1096                 :            :             }
    1097                 :            : 
    1098                 :     267273 :           if (set_reg_equal)
    1099                 :            :             {
    1100                 :     267273 :               if (dump_file)
    1101                 :          0 :                 fprintf (dump_file, " Setting REG_EQUAL note\n");
    1102                 :            : 
    1103                 :     267273 :               note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
    1104                 :            :             }
    1105                 :            :         }
    1106                 :            :     }
    1107                 :            : 
    1108                 :    2627260 :   if ((ok || note) && !CONSTANT_P (new_rtx))
    1109                 :    2152950 :     update_df (insn, note);
    1110                 :            : 
    1111                 :    2627260 :   return ok;
    1112                 :            : }
    1113                 :            : 
    1114                 :            : /* For the given single_set INSN, containing SRC known to be a
    1115                 :            :    ZERO_EXTEND or SIGN_EXTEND of a register, return true if INSN
    1116                 :            :    is redundant due to the register being set by a LOAD_EXTEND_OP
    1117                 :            :    load from memory.  */
    1118                 :            : 
    1119                 :            : static bool
    1120                 :      11541 : free_load_extend (rtx src, rtx_insn *insn)
    1121                 :            : {
    1122                 :      11541 :   rtx reg;
    1123                 :      11541 :   df_ref def, use;
    1124                 :            : 
    1125                 :      11541 :   reg = XEXP (src, 0);
    1126                 :      11541 :   if (load_extend_op (GET_MODE (reg)) != GET_CODE (src))
    1127                 :            :     return false;
    1128                 :            : 
    1129                 :          0 :   FOR_EACH_INSN_USE (use, insn)
    1130                 :          0 :     if (!DF_REF_IS_ARTIFICIAL (use)
    1131                 :          0 :         && DF_REF_TYPE (use) == DF_REF_REG_USE
    1132                 :          0 :         && DF_REF_REG (use) == reg)
    1133                 :            :       break;
    1134                 :          0 :   if (!use)
    1135                 :            :     return false;
    1136                 :            : 
    1137                 :          0 :   def = get_def_for_use (use);
    1138                 :          0 :   if (!def)
    1139                 :            :     return false;
    1140                 :            : 
    1141                 :          0 :   if (DF_REF_IS_ARTIFICIAL (def))
    1142                 :            :     return false;
    1143                 :            : 
    1144                 :          0 :   if (NONJUMP_INSN_P (DF_REF_INSN (def)))
    1145                 :            :     {
    1146                 :          0 :       rtx patt = PATTERN (DF_REF_INSN (def));
    1147                 :            : 
    1148                 :          0 :       if (GET_CODE (patt) == SET
    1149                 :          0 :           && GET_CODE (SET_SRC (patt)) == MEM
    1150                 :          0 :           && rtx_equal_p (SET_DEST (patt), reg))
    1151                 :          0 :         return true;
    1152                 :            :     }
    1153                 :            :   return false;
    1154                 :            : }
    1155                 :            : 
    1156                 :            : /* If USE is a subreg, see if it can be replaced by a pseudo.  */
    1157                 :            : 
    1158                 :            : static bool
    1159                 :   31411600 : forward_propagate_subreg (df_ref use, rtx_insn *def_insn, rtx def_set)
    1160                 :            : {
    1161                 :   31411600 :   rtx use_reg = DF_REF_REG (use);
    1162                 :   31411600 :   rtx_insn *use_insn;
    1163                 :   31411600 :   rtx src;
    1164                 :   31411600 :   scalar_int_mode int_use_mode, src_mode;
    1165                 :            : 
    1166                 :            :   /* Only consider subregs... */
    1167                 :   31411600 :   machine_mode use_mode = GET_MODE (use_reg);
    1168                 :   31411600 :   if (GET_CODE (use_reg) != SUBREG
    1169                 :    1079230 :       || !REG_P (SET_DEST (def_set)))
    1170                 :            :     return false;
    1171                 :            : 
    1172                 :    1068070 :   if (paradoxical_subreg_p (use_reg))
    1173                 :            :     {
    1174                 :            :       /* If this is a paradoxical SUBREG, we have no idea what value the
    1175                 :            :          extra bits would have.  However, if the operand is equivalent to
    1176                 :            :          a SUBREG whose operand is the same as our mode, and all the modes
    1177                 :            :          are within a word, we can just use the inner operand because
    1178                 :            :          these SUBREGs just say how to treat the register.  */
    1179                 :      13283 :       use_insn = DF_REF_INSN (use);
    1180                 :      13283 :       src = SET_SRC (def_set);
    1181                 :      13283 :       if (GET_CODE (src) == SUBREG
    1182                 :        200 :           && REG_P (SUBREG_REG (src))
    1183                 :        184 :           && REGNO (SUBREG_REG (src)) >= FIRST_PSEUDO_REGISTER
    1184                 :        184 :           && GET_MODE (SUBREG_REG (src)) == use_mode
    1185                 :         15 :           && subreg_lowpart_p (src)
    1186                 :      13298 :           && all_uses_available_at (def_insn, use_insn))
    1187                 :         15 :         return try_fwprop_subst (use, DF_REF_LOC (use), SUBREG_REG (src),
    1188                 :         15 :                                  def_insn, false);
    1189                 :            :     }
    1190                 :            : 
    1191                 :            :   /* If this is a SUBREG of a ZERO_EXTEND or SIGN_EXTEND, and the SUBREG
    1192                 :            :      is the low part of the reg being extended then just use the inner
    1193                 :            :      operand.  Don't do this if the ZERO_EXTEND or SIGN_EXTEND insn will
    1194                 :            :      be removed due to it matching a LOAD_EXTEND_OP load from memory,
    1195                 :            :      or due to the operation being a no-op when applied to registers.
    1196                 :            :      For example, if we have:
    1197                 :            : 
    1198                 :            :          A: (set (reg:DI X) (sign_extend:DI (reg:SI Y)))
    1199                 :            :          B: (... (subreg:SI (reg:DI X)) ...)
    1200                 :            : 
    1201                 :            :      and mode_rep_extended says that Y is already sign-extended,
    1202                 :            :      the backend will typically allow A to be combined with the
    1203                 :            :      definition of Y or, failing that, allow A to be deleted after
    1204                 :            :      reload through register tying.  Introducing more uses of Y
    1205                 :            :      prevents both optimisations.  */
    1206                 :    1054790 :   else if (is_a <scalar_int_mode> (use_mode, &int_use_mode)
    1207                 :     760663 :            && subreg_lowpart_p (use_reg))
    1208                 :            :     {
    1209                 :     666375 :       use_insn = DF_REF_INSN (use);
    1210                 :     666375 :       src = SET_SRC (def_set);
    1211                 :     666375 :       if ((GET_CODE (src) == ZERO_EXTEND
    1212                 :     666375 :            || GET_CODE (src) == SIGN_EXTEND)
    1213                 :      59726 :           && is_a <scalar_int_mode> (GET_MODE (src), &src_mode)
    1214                 :      59678 :           && REG_P (XEXP (src, 0))
    1215                 :      12984 :           && REGNO (XEXP (src, 0)) >= FIRST_PSEUDO_REGISTER
    1216                 :      12984 :           && GET_MODE (XEXP (src, 0)) == use_mode
    1217                 :      11541 :           && !free_load_extend (src, def_insn)
    1218                 :      11541 :           && (targetm.mode_rep_extended (int_use_mode, src_mode)
    1219                 :      11541 :               != (int) GET_CODE (src))
    1220                 :     677916 :           && all_uses_available_at (def_insn, use_insn))
    1221                 :      11352 :         return try_fwprop_subst (use, DF_REF_LOC (use), XEXP (src, 0),
    1222                 :      11352 :                                  def_insn, false);
    1223                 :            :     }
    1224                 :            : 
    1225                 :            :   return false;
    1226                 :            : }
    1227                 :            : 
    1228                 :            : /* Try to replace USE with SRC (defined in DEF_INSN) in __asm.  */
    1229                 :            : 
    1230                 :            : static bool
    1231                 :      59820 : forward_propagate_asm (df_ref use, rtx_insn *def_insn, rtx def_set, rtx reg)
    1232                 :            : {
    1233                 :      59820 :   rtx_insn *use_insn = DF_REF_INSN (use);
    1234                 :      59820 :   rtx src, use_pat, asm_operands, new_rtx, *loc;
    1235                 :      59820 :   int speed_p, i;
    1236                 :      59820 :   df_ref uses;
    1237                 :            : 
    1238                 :      59820 :   gcc_assert ((DF_REF_FLAGS (use) & DF_REF_IN_NOTE) == 0);
    1239                 :            : 
    1240                 :      59820 :   src = SET_SRC (def_set);
    1241                 :      59820 :   use_pat = PATTERN (use_insn);
    1242                 :            : 
    1243                 :            :   /* In __asm don't replace if src might need more registers than
    1244                 :            :      reg, as that could increase register pressure on the __asm.  */
    1245                 :      59820 :   uses = DF_INSN_USES (def_insn);
    1246                 :      59820 :   if (uses && DF_REF_NEXT_LOC (uses))
    1247                 :            :     return false;
    1248                 :            : 
    1249                 :      58901 :   update_df_init (def_insn, use_insn);
    1250                 :      58901 :   speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
    1251                 :      58901 :   asm_operands = NULL_RTX;
    1252                 :      58901 :   switch (GET_CODE (use_pat))
    1253                 :            :     {
    1254                 :            :     case ASM_OPERANDS:
    1255                 :            :       asm_operands = use_pat;
    1256                 :            :       break;
    1257                 :          1 :     case SET:
    1258                 :          1 :       if (MEM_P (SET_DEST (use_pat)))
    1259                 :            :         {
    1260                 :          0 :           loc = &SET_DEST (use_pat);
    1261                 :          0 :           new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
    1262                 :          0 :           if (new_rtx)
    1263                 :          0 :             validate_unshare_change (use_insn, loc, new_rtx, true);
    1264                 :            :         }
    1265                 :          1 :       asm_operands = SET_SRC (use_pat);
    1266                 :          1 :       break;
    1267                 :            :     case PARALLEL:
    1268                 :     322938 :       for (i = 0; i < XVECLEN (use_pat, 0); i++)
    1269                 :     264038 :         if (GET_CODE (XVECEXP (use_pat, 0, i)) == SET)
    1270                 :            :           {
    1271                 :     191571 :             if (MEM_P (SET_DEST (XVECEXP (use_pat, 0, i))))
    1272                 :            :               {
    1273                 :       2739 :                 loc = &SET_DEST (XVECEXP (use_pat, 0, i));
    1274                 :       2739 :                 new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg,
    1275                 :            :                                          src, speed_p);
    1276                 :       2739 :                 if (new_rtx)
    1277                 :         77 :                   validate_unshare_change (use_insn, loc, new_rtx, true);
    1278                 :            :               }
    1279                 :     191571 :             asm_operands = SET_SRC (XVECEXP (use_pat, 0, i));
    1280                 :            :           }
    1281                 :      72467 :         else if (GET_CODE (XVECEXP (use_pat, 0, i)) == ASM_OPERANDS)
    1282                 :       5257 :           asm_operands = XVECEXP (use_pat, 0, i);
    1283                 :            :       break;
    1284                 :          0 :     default:
    1285                 :          0 :       gcc_unreachable ();
    1286                 :            :     }
    1287                 :            : 
    1288                 :      58901 :   gcc_assert (asm_operands && GET_CODE (asm_operands) == ASM_OPERANDS);
    1289                 :     146559 :   for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (asm_operands); i++)
    1290                 :            :     {
    1291                 :      87658 :       loc = &ASM_OPERANDS_INPUT (asm_operands, i);
    1292                 :      87658 :       new_rtx = propagate_rtx (*loc, GET_MODE (*loc), reg, src, speed_p);
    1293                 :      87658 :       if (new_rtx)
    1294                 :      52378 :         validate_unshare_change (use_insn, loc, new_rtx, true);
    1295                 :            :     }
    1296                 :            : 
    1297                 :      58901 :   if (num_changes_pending () == 0 || !apply_change_group ())
    1298                 :      58081 :     return false;
    1299                 :            : 
    1300                 :        820 :   update_df (use_insn, NULL);
    1301                 :        820 :   num_changes++;
    1302                 :        820 :   return true;
    1303                 :            : }
    1304                 :            : 
    1305                 :            : /* Try to replace USE with SRC (defined in DEF_INSN) and simplify the
    1306                 :            :    result.  */
    1307                 :            : 
    1308                 :            : static bool
    1309                 :   33362600 : forward_propagate_and_simplify (df_ref use, rtx_insn *def_insn, rtx def_set)
    1310                 :            : {
    1311                 :   33362600 :   rtx_insn *use_insn = DF_REF_INSN (use);
    1312                 :   33362600 :   rtx use_set = single_set (use_insn);
    1313                 :   33362600 :   rtx src, reg, new_rtx, *loc;
    1314                 :   33362600 :   bool set_reg_equal;
    1315                 :   33362600 :   machine_mode mode;
    1316                 :   33362600 :   int asm_use = -1;
    1317                 :            : 
    1318                 :   33362600 :   if (INSN_CODE (use_insn) < 0)
    1319                 :    3663050 :     asm_use = asm_noperands (PATTERN (use_insn));
    1320                 :            : 
    1321                 :   33362600 :   if (!use_set && asm_use < 0 && !DEBUG_INSN_P (use_insn))
    1322                 :            :     return false;
    1323                 :            : 
    1324                 :            :   /* Do not propagate into PC, CC0, etc.  */
    1325                 :   32732100 :   if (use_set && GET_MODE (SET_DEST (use_set)) == VOIDmode)
    1326                 :            :     return false;
    1327                 :            : 
    1328                 :            :   /* If def and use are subreg, check if they match.  */
    1329                 :   29666700 :   reg = DF_REF_REG (use);
    1330                 :   29666700 :   if (GET_CODE (reg) == SUBREG && GET_CODE (SET_DEST (def_set)) == SUBREG)
    1331                 :            :     {
    1332                 :      11428 :       if (maybe_ne (SUBREG_BYTE (SET_DEST (def_set)), SUBREG_BYTE (reg)))
    1333                 :            :         return false;
    1334                 :            :     }
    1335                 :            :   /* Check if the def had a subreg, but the use has the whole reg.  */
    1336                 :   29655300 :   else if (REG_P (reg) && GET_CODE (SET_DEST (def_set)) == SUBREG)
    1337                 :            :     return false;
    1338                 :            :   /* Check if the use has a subreg, but the def had the whole reg.  Unlike the
    1339                 :            :      previous case, the optimization is possible and often useful indeed.  */
    1340                 :   29636000 :   else if (GET_CODE (reg) == SUBREG && REG_P (SET_DEST (def_set)))
    1341                 :    1100570 :     reg = SUBREG_REG (reg);
    1342                 :            : 
    1343                 :            :   /* Make sure that we can treat REG as having the same mode as the
    1344                 :            :      source of DEF_SET.  */
    1345                 :   29647400 :   if (GET_MODE (SET_DEST (def_set)) != GET_MODE (reg))
    1346                 :            :     return false;
    1347                 :            : 
    1348                 :            :   /* Check if the substitution is valid (last, because it's the most
    1349                 :            :      expensive check!).  */
    1350                 :   28740000 :   src = SET_SRC (def_set);
    1351                 :   28740000 :   if (!CONSTANT_P (src) && !all_uses_available_at (def_insn, use_insn))
    1352                 :            :     return false;
    1353                 :            : 
    1354                 :            :   /* Check if the def is loading something from the constant pool; in this
    1355                 :            :      case we would undo optimization such as compress_float_constant.
    1356                 :            :      Still, we can set a REG_EQUAL note.  */
    1357                 :   22579700 :   if (MEM_P (src) && MEM_READONLY_P (src))
    1358                 :            :     {
    1359                 :    1049960 :       rtx x = avoid_constant_pool_reference (src);
    1360                 :    1049960 :       if (x != src && use_set)
    1361                 :            :         {
    1362                 :     742258 :           rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
    1363                 :     742258 :           rtx old_rtx = note ? XEXP (note, 0) : SET_SRC (use_set);
    1364                 :     742258 :           rtx new_rtx = simplify_replace_rtx (old_rtx, src, x);
    1365                 :     742258 :           if (old_rtx != new_rtx)
    1366                 :         11 :             set_unique_reg_note (use_insn, REG_EQUAL, copy_rtx (new_rtx));
    1367                 :            :         }
    1368                 :    1049960 :       return false;
    1369                 :            :     }
    1370                 :            : 
    1371                 :   21529800 :   if (asm_use >= 0)
    1372                 :      59820 :     return forward_propagate_asm (use, def_insn, def_set, reg);
    1373                 :            : 
    1374                 :            :   /* Else try simplifying.  */
    1375                 :            : 
    1376                 :   21470000 :   if (DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE)
    1377                 :            :     {
    1378                 :    1146860 :       loc = &SET_DEST (use_set);
    1379                 :    1146860 :       set_reg_equal = false;
    1380                 :            :     }
    1381                 :   20323100 :   else if (!use_set)
    1382                 :            :     {
    1383                 :    2385480 :       loc = &INSN_VAR_LOCATION_LOC (use_insn);
    1384                 :    2385480 :       set_reg_equal = false;
    1385                 :            :     }
    1386                 :            :   else
    1387                 :            :     {
    1388                 :   17937600 :       rtx note = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
    1389                 :   17937600 :       if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
    1390                 :     344827 :         loc = &XEXP (note, 0);
    1391                 :            :       else
    1392                 :   17592800 :         loc = &SET_SRC (use_set);
    1393                 :            : 
    1394                 :            :       /* Do not replace an existing REG_EQUAL note if the insn is not
    1395                 :            :          recognized.  Either we're already replacing in the note, or we'll
    1396                 :            :          separately try plugging the definition in the note and simplifying.
    1397                 :            :          And only install a REQ_EQUAL note when the destination is a REG
    1398                 :            :          that isn't mentioned in USE_SET, as the note would be invalid
    1399                 :            :          otherwise.  We also don't want to install a note if we are merely
    1400                 :            :          propagating a pseudo since verifying that this pseudo isn't dead
    1401                 :            :          is a pain; moreover such a note won't help anything.
    1402                 :            :          If the use is a paradoxical subreg, make sure we don't add a
    1403                 :            :          REG_EQUAL note for it, because it is not equivalent, it is one
    1404                 :            :          possible value for it, but we can't rely on it holding that value.
    1405                 :            :          See PR70574.  */
    1406                 :   17937600 :       set_reg_equal = (note == NULL_RTX
    1407                 :   16019200 :                        && REG_P (SET_DEST (use_set))
    1408                 :   12714600 :                        && !REG_P (src)
    1409                 :   10017100 :                        && !(GET_CODE (src) == SUBREG
    1410                 :     331495 :                             && REG_P (SUBREG_REG (src)))
    1411                 :    9686290 :                        && !reg_mentioned_p (SET_DEST (use_set),
    1412                 :    9686290 :                                             SET_SRC (use_set))
    1413                 :   27440500 :                        && !paradoxical_subreg_p (DF_REF_REG (use)));
    1414                 :            :     }
    1415                 :            : 
    1416                 :   21470000 :   if (GET_MODE (*loc) == VOIDmode)
    1417                 :     127195 :     mode = GET_MODE (SET_DEST (use_set));
    1418                 :            :   else
    1419                 :   21342800 :     mode = GET_MODE (*loc);
    1420                 :            : 
    1421                 :   21470000 :   new_rtx = propagate_rtx (*loc, mode, reg, src,
    1422                 :   21470000 :                            optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn)));
    1423                 :            : 
    1424                 :   21470000 :   if (!new_rtx)
    1425                 :            :     return false;
    1426                 :            : 
    1427                 :    2615900 :   return try_fwprop_subst (use, loc, new_rtx, def_insn, set_reg_equal);
    1428                 :            : }
    1429                 :            : 
    1430                 :            : 
    1431                 :            : /* Given a use USE of an insn, if it has a single reaching
    1432                 :            :    definition, try to forward propagate it into that insn.
    1433                 :            :    Return true if cfg cleanup will be needed.
    1434                 :            :    REG_PROP_ONLY is true if we should only propagate register copies.  */
    1435                 :            : 
    1436                 :            : static bool
    1437                 :  172557000 : forward_propagate_into (df_ref use, bool reg_prop_only = false)
    1438                 :            : {
    1439                 :  172557000 :   df_ref def;
    1440                 :  172557000 :   rtx_insn *def_insn, *use_insn;
    1441                 :  172557000 :   rtx def_set;
    1442                 :  172557000 :   rtx parent;
    1443                 :            : 
    1444                 :  172557000 :   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
    1445                 :            :     return false;
    1446                 :  172157000 :   if (DF_REF_IS_ARTIFICIAL (use))
    1447                 :            :     return false;
    1448                 :            : 
    1449                 :            :   /* Only consider uses that have a single definition.  */
    1450                 :  112801000 :   def = get_def_for_use (use);
    1451                 :  112801000 :   if (!def)
    1452                 :            :     return false;
    1453                 :  103432000 :   if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
    1454                 :            :     return false;
    1455                 :   97704700 :   if (DF_REF_IS_ARTIFICIAL (def))
    1456                 :            :     return false;
    1457                 :            : 
    1458                 :            :   /* Check if the use is still present in the insn!  */
    1459                 :   75498700 :   use_insn = DF_REF_INSN (use);
    1460                 :   75498700 :   if (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
    1461                 :    1012380 :     parent = find_reg_note (use_insn, REG_EQUAL, NULL_RTX);
    1462                 :            :   else
    1463                 :   74486300 :     parent = PATTERN (use_insn);
    1464                 :            : 
    1465                 :   75498700 :   if (!reg_mentioned_p (DF_REF_REG (use), parent))
    1466                 :            :     return false;
    1467                 :            : 
    1468                 :   64845700 :   def_insn = DF_REF_INSN (def);
    1469                 :   64845700 :   if (multiple_sets (def_insn))
    1470                 :            :     return false;
    1471                 :   64297600 :   def_set = single_set (def_insn);
    1472                 :   64297600 :   if (!def_set)
    1473                 :            :     return false;
    1474                 :            : 
    1475                 :   63859800 :   if (reg_prop_only
    1476                 :   63859800 :       && (!reg_single_def_p (SET_SRC (def_set))
    1477                 :     439318 :           || !reg_single_def_p (SET_DEST (def_set))))
    1478                 :   29061900 :     return false;
    1479                 :            : 
    1480                 :            :   /* Allow propagations into a loop only for reg-to-reg copies, since
    1481                 :            :      replacing one register by another shouldn't increase the cost.  */
    1482                 :            : 
    1483                 :   34797800 :   if (DF_REF_BB (def)->loop_father != DF_REF_BB (use)->loop_father
    1484                 :   34797800 :       && (!reg_single_def_p (SET_SRC (def_set))
    1485                 :     113527 :           || !reg_single_def_p (SET_DEST (def_set))))
    1486                 :    1435260 :     return false;
    1487                 :            : 
    1488                 :            :   /* Only try one kind of propagation.  If two are possible, we'll
    1489                 :            :      do it on the following iterations.  */
    1490                 :   33362600 :   if (forward_propagate_and_simplify (use, def_insn, def_set)
    1491                 :   33362600 :       || forward_propagate_subreg (use, def_insn, def_set))
    1492                 :            :     {
    1493                 :    1962340 :       propagations_left--;
    1494                 :            : 
    1495                 :    1962340 :       if (cfun->can_throw_non_call_exceptions
    1496                 :     718971 :           && find_reg_note (use_insn, REG_EH_REGION, NULL_RTX)
    1497                 :    1973700 :           && purge_dead_edges (DF_REF_BB (use)))
    1498                 :          2 :         return true;
    1499                 :            :     }
    1500                 :            :   return false;
    1501                 :            : }
    1502                 :            : 
    1503                 :            : 
    1504                 :            : static void
    1505                 :    1377020 : fwprop_init (void)
    1506                 :            : {
    1507                 :    1377020 :   num_changes = 0;
    1508                 :    1377020 :   calculate_dominance_info (CDI_DOMINATORS);
    1509                 :            : 
    1510                 :            :   /* We do not always want to propagate into loops, so we have to find
    1511                 :            :      loops and be careful about them.  Avoid CFG modifications so that
    1512                 :            :      we don't have to update dominance information afterwards for
    1513                 :            :      build_single_def_use_links.  */
    1514                 :    1377020 :   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
    1515                 :            : 
    1516                 :    1377020 :   build_single_def_use_links ();
    1517                 :    1377020 :   df_set_flags (DF_DEFER_INSN_RESCAN);
    1518                 :            : 
    1519                 :    1377020 :   active_defs = XNEWVEC (df_ref, max_reg_num ());
    1520                 :    1377020 :   if (flag_checking)
    1521                 :    1377000 :     active_defs_check = sparseset_alloc (max_reg_num ());
    1522                 :            : 
    1523                 :    1377020 :   propagations_left = DF_USES_TABLE_SIZE ();
    1524                 :    1377020 : }
    1525                 :            : 
    1526                 :            : static void
    1527                 :    1377020 : fwprop_done (void)
    1528                 :            : {
    1529                 :    1377020 :   loop_optimizer_finalize ();
    1530                 :            : 
    1531                 :    1377020 :   use_def_ref.release ();
    1532                 :    1377020 :   free (active_defs);
    1533                 :    1377020 :   if (flag_checking)
    1534                 :    1377000 :     sparseset_free (active_defs_check);
    1535                 :            : 
    1536                 :    1377020 :   free_dominance_info (CDI_DOMINATORS);
    1537                 :    1377020 :   cleanup_cfg (0);
    1538                 :    1377020 :   delete_trivially_dead_insns (get_insns (), max_reg_num ());
    1539                 :            : 
    1540                 :    1377020 :   if (dump_file)
    1541                 :         62 :     fprintf (dump_file,
    1542                 :            :              "\nNumber of successful forward propagations: %d\n\n",
    1543                 :            :              num_changes);
    1544                 :    1377020 : }
    1545                 :            : 
    1546                 :            : 
    1547                 :            : /* Main entry point.  */
    1548                 :            : 
    1549                 :            : static bool
    1550                 :    1888200 : gate_fwprop (void)
    1551                 :            : {
    1552                 :    1377100 :   return optimize > 0 && flag_forward_propagate;
    1553                 :            : }
    1554                 :            : 
    1555                 :            : static unsigned int
    1556                 :    1377020 : fwprop (bool fwprop_addr_p)
    1557                 :            : {
    1558                 :    1377020 :   unsigned i;
    1559                 :            : 
    1560                 :    1377020 :   fwprop_init ();
    1561                 :            : 
    1562                 :            :   /* Go through all the uses.  df_uses_create will create new ones at the
    1563                 :            :      end, and we'll go through them as well.
    1564                 :            : 
    1565                 :            :      Do not forward propagate addresses into loops until after unrolling.
    1566                 :            :      CSE did so because it was able to fix its own mess, but we are not.  */
    1567                 :            : 
    1568                 :  176802000 :   for (i = 0; i < DF_USES_TABLE_SIZE (); i++)
    1569                 :            :     {
    1570                 :  175425000 :       if (!propagations_left)
    1571                 :            :         break;
    1572                 :            : 
    1573                 :  175425000 :       df_ref use = DF_USES_GET (i);
    1574                 :  175425000 :       if (use)
    1575                 :            :         {
    1576                 :  175425000 :           if (DF_REF_TYPE (use) == DF_REF_REG_USE
    1577                 :   24749700 :               || DF_REF_BB (use)->loop_father == NULL
    1578                 :            :               /* The outer most loop is not really a loop.  */
    1579                 :  206046000 :               || loop_outer (DF_REF_BB (use)->loop_father) == NULL)
    1580                 :  169554000 :             forward_propagate_into (use, fwprop_addr_p);
    1581                 :            : 
    1582                 :    5871390 :           else if (fwprop_addr_p)
    1583                 :    3003560 :             forward_propagate_into (use, false);
    1584                 :            :         }
    1585                 :            :     }
    1586                 :            : 
    1587                 :    1377020 :   fwprop_done ();
    1588                 :    1377020 :   return 0;
    1589                 :            : }
    1590                 :            : 
    1591                 :            : namespace {
    1592                 :            : 
    1593                 :            : const pass_data pass_data_rtl_fwprop =
    1594                 :            : {
    1595                 :            :   RTL_PASS, /* type */
    1596                 :            :   "fwprop1", /* name */
    1597                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    1598                 :            :   TV_FWPROP, /* tv_id */
    1599                 :            :   0, /* properties_required */
    1600                 :            :   0, /* properties_provided */
    1601                 :            :   0, /* properties_destroyed */
    1602                 :            :   0, /* todo_flags_start */
    1603                 :            :   TODO_df_finish, /* todo_flags_finish */
    1604                 :            : };
    1605                 :            : 
    1606                 :            : class pass_rtl_fwprop : public rtl_opt_pass
    1607                 :            : {
    1608                 :            : public:
    1609                 :     200773 :   pass_rtl_fwprop (gcc::context *ctxt)
    1610                 :     401546 :     : rtl_opt_pass (pass_data_rtl_fwprop, ctxt)
    1611                 :            :   {}
    1612                 :            : 
    1613                 :            :   /* opt_pass methods: */
    1614                 :     944101 :   virtual bool gate (function *) { return gate_fwprop (); }
    1615                 :     688510 :   virtual unsigned int execute (function *) { return fwprop (false); }
    1616                 :            : 
    1617                 :            : }; // class pass_rtl_fwprop
    1618                 :            : 
    1619                 :            : } // anon namespace
    1620                 :            : 
    1621                 :            : rtl_opt_pass *
    1622                 :     200773 : make_pass_rtl_fwprop (gcc::context *ctxt)
    1623                 :            : {
    1624                 :     200773 :   return new pass_rtl_fwprop (ctxt);
    1625                 :            : }
    1626                 :            : 
    1627                 :            : namespace {
    1628                 :            : 
    1629                 :            : const pass_data pass_data_rtl_fwprop_addr =
    1630                 :            : {
    1631                 :            :   RTL_PASS, /* type */
    1632                 :            :   "fwprop2", /* name */
    1633                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    1634                 :            :   TV_FWPROP, /* tv_id */
    1635                 :            :   0, /* properties_required */
    1636                 :            :   0, /* properties_provided */
    1637                 :            :   0, /* properties_destroyed */
    1638                 :            :   0, /* todo_flags_start */
    1639                 :            :   TODO_df_finish, /* todo_flags_finish */
    1640                 :            : };
    1641                 :            : 
    1642                 :            : class pass_rtl_fwprop_addr : public rtl_opt_pass
    1643                 :            : {
    1644                 :            : public:
    1645                 :     200773 :   pass_rtl_fwprop_addr (gcc::context *ctxt)
    1646                 :     401546 :     : rtl_opt_pass (pass_data_rtl_fwprop_addr, ctxt)
    1647                 :            :   {}
    1648                 :            : 
    1649                 :            :   /* opt_pass methods: */
    1650                 :     944101 :   virtual bool gate (function *) { return gate_fwprop (); }
    1651                 :     688510 :   virtual unsigned int execute (function *) { return fwprop (true); }
    1652                 :            : 
    1653                 :            : }; // class pass_rtl_fwprop_addr
    1654                 :            : 
    1655                 :            : } // anon namespace
    1656                 :            : 
    1657                 :            : rtl_opt_pass *
    1658                 :     200773 : make_pass_rtl_fwprop_addr (gcc::context *ctxt)
    1659                 :            : {
    1660                 :     200773 :   return new pass_rtl_fwprop_addr (ctxt);
    1661                 :            : }

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.