LCOV - code coverage report
Current view: top level - gcc - dce.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 495 537 92.2 %
Date: 2020-04-04 11:58:09 Functions: 34 34 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* RTL dead code elimination.
       2                 :            :    Copyright (C) 2005-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify it under
       7                 :            : the terms of the GNU General Public License as published by the Free
       8                 :            : Software Foundation; either version 3, or (at your option) any later
       9                 :            : version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "backend.h"
      24                 :            : #include "rtl.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "predict.h"
      27                 :            : #include "df.h"
      28                 :            : #include "memmodel.h"
      29                 :            : #include "tm_p.h"
      30                 :            : #include "emit-rtl.h"  /* FIXME: Can go away once crtl is moved to rtl.h.  */
      31                 :            : #include "cfgrtl.h"
      32                 :            : #include "cfgbuild.h"
      33                 :            : #include "cfgcleanup.h"
      34                 :            : #include "dce.h"
      35                 :            : #include "valtrack.h"
      36                 :            : #include "tree-pass.h"
      37                 :            : #include "dbgcnt.h"
      38                 :            : #include "rtl-iter.h"
      39                 :            : 
      40                 :            : 
      41                 :            : /* -------------------------------------------------------------------------
      42                 :            :    Core mark/delete routines
      43                 :            :    ------------------------------------------------------------------------- */
      44                 :            : 
      45                 :            : /* True if we are invoked while the df engine is running; in this case,
      46                 :            :    we don't want to reenter it.  */
      47                 :            : static bool df_in_progress = false;
      48                 :            : 
      49                 :            : /* True if we are allowed to alter the CFG in this pass.  */
      50                 :            : static bool can_alter_cfg = false;
      51                 :            : 
      52                 :            : /* Instructions that have been marked but whose dependencies have not
      53                 :            :    yet been processed.  */
      54                 :            : static vec<rtx_insn *> worklist;
      55                 :            : 
      56                 :            : /* Bitmap of instructions marked as needed indexed by INSN_UID.  */
      57                 :            : static sbitmap marked;
      58                 :            : 
      59                 :            : /* Bitmap obstacks used for block processing by the fast algorithm.  */
      60                 :            : static bitmap_obstack dce_blocks_bitmap_obstack;
      61                 :            : static bitmap_obstack dce_tmp_bitmap_obstack;
      62                 :            : 
      63                 :            : static bool find_call_stack_args (rtx_call_insn *, bool, bool, bitmap);
      64                 :            : 
      65                 :            : /* A subroutine for which BODY is part of the instruction being tested;
      66                 :            :    either the top-level pattern, or an element of a PARALLEL.  The
      67                 :            :    instruction is known not to be a bare USE or CLOBBER.  */
      68                 :            : 
      69                 :            : static bool
      70                 :  469159000 : deletable_insn_p_1 (rtx body)
      71                 :            : {
      72                 :  469159000 :   switch (GET_CODE (body))
      73                 :            :     {
      74                 :            :     case PREFETCH:
      75                 :            :     case TRAP_IF:
      76                 :            :       /* The UNSPEC case was added here because the ia-64 claims that
      77                 :            :          USEs do not work after reload and generates UNSPECS rather
      78                 :            :          than USEs.  Since dce is run after reload we need to avoid
      79                 :            :          deleting these even if they are dead.  If it turns out that
      80                 :            :          USEs really do work after reload, the ia-64 should be
      81                 :            :          changed, and the UNSPEC case can be removed.  */
      82                 :            :     case UNSPEC:
      83                 :            :       return false;
      84                 :            : 
      85                 :  469019000 :     default:
      86                 :  469019000 :       return !volatile_refs_p (body);
      87                 :            :     }
      88                 :            : }
      89                 :            : 
      90                 :            : /* Don't delete calls that may throw if we cannot do so.  */
      91                 :            : 
      92                 :            : static bool
      93                 :     948715 : can_delete_call (rtx_insn *insn)
      94                 :            : {
      95                 :     948715 :   if (cfun->can_delete_dead_exceptions && can_alter_cfg)
      96                 :            :     return true;
      97                 :     948700 :   if (!insn_nothrow_p (insn))
      98                 :            :     return false;
      99                 :     941568 :   if (can_alter_cfg)
     100                 :            :     return true;
     101                 :            :   /* If we can't alter cfg, even when the call can't throw exceptions, it
     102                 :            :      might have EDGE_ABNORMAL_CALL edges and so we shouldn't delete such
     103                 :            :      calls.  */
     104                 :     630706 :   gcc_assert (CALL_P (insn));
     105                 :     630706 :   if (BLOCK_FOR_INSN (insn) && BB_END (BLOCK_FOR_INSN (insn)) == insn)
     106                 :            :     {
     107                 :        406 :       edge e;
     108                 :        406 :       edge_iterator ei;
     109                 :            : 
     110                 :        574 :       FOR_EACH_EDGE (e, ei, BLOCK_FOR_INSN (insn)->succs)
     111                 :        406 :         if ((e->flags & EDGE_ABNORMAL_CALL) != 0)
     112                 :        238 :           return false;
     113                 :            :     }
     114                 :            :   return true;
     115                 :            : }
     116                 :            : 
     117                 :            : /* Return true if INSN is a normal instruction that can be deleted by
     118                 :            :    the DCE pass.  */
     119                 :            : 
     120                 :            : static bool
     121                 :  500611000 : deletable_insn_p (rtx_insn *insn, bool fast, bitmap arg_stores)
     122                 :            : {
     123                 :  500611000 :   rtx body, x;
     124                 :  500611000 :   int i;
     125                 :  500611000 :   df_ref def;
     126                 :            : 
     127                 :  500611000 :   if (CALL_P (insn)
     128                 :            :       /* We cannot delete calls inside of the recursive dce because
     129                 :            :          this may cause basic blocks to be deleted and this messes up
     130                 :            :          the rest of the stack of optimization passes.  */
     131                 :   38779000 :       && (!df_in_progress)
     132                 :            :       /* We cannot delete pure or const sibling calls because it is
     133                 :            :          hard to see the result.  */
     134                 :    9148230 :       && (!SIBLING_CALL_P (insn))
     135                 :            :       /* We can delete dead const or pure calls as long as they do not
     136                 :            :          infinite loop.  */
     137                 :    8946350 :       && (RTL_CONST_OR_PURE_CALL_P (insn)
     138                 :     553900 :           && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
     139                 :            :       /* Don't delete calls that may throw if we cannot do so.  */
     140                 :  501086000 :       && can_delete_call (insn))
     141                 :     471645 :     return find_call_stack_args (as_a <rtx_call_insn *> (insn), false,
     142                 :     471645 :                                  fast, arg_stores);
     143                 :            : 
     144                 :            :   /* Don't delete jumps, notes and the like.  */
     145                 :  500139000 :   if (!NONJUMP_INSN_P (insn))
     146                 :            :     return false;
     147                 :            : 
     148                 :            :   /* Don't delete insns that may throw if we cannot do so.  */
     149                 :      15038 :   if (!(cfun->can_delete_dead_exceptions && can_alter_cfg)
     150                 :  413773000 :       && !insn_nothrow_p (insn))
     151                 :            :     return false;
     152                 :            : 
     153                 :            :   /* If INSN sets a global_reg, leave it untouched.  */
     154                 :  802642000 :   FOR_EACH_INSN_DEF (def, insn)
     155                 :  404795000 :     if (HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
     156                 :  272922000 :         && global_regs[DF_REF_REGNO (def)])
     157                 :            :       return false;
     158                 :            :     /* Initialization of pseudo PIC register should never be removed.  */
     159                 :  404795000 :     else if (DF_REF_REG (def) == pic_offset_table_rtx
     160                 :  404795000 :              && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
     161                 :            :       return false;
     162                 :            : 
     163                 :            :   /* Callee-save restores are needed.  */
     164                 :  397847000 :   if (RTX_FRAME_RELATED_P (insn)
     165                 :    7367200 :       && crtl->shrink_wrapped_separate
     166                 :  397847000 :       && find_reg_note (insn, REG_CFA_RESTORE, NULL))
     167                 :            :     return false;
     168                 :            : 
     169                 :  397847000 :   body = PATTERN (insn);
     170                 :  397847000 :   switch (GET_CODE (body))
     171                 :            :     {
     172                 :            :     case USE:
     173                 :            :     case VAR_LOCATION:
     174                 :            :       return false;
     175                 :            : 
     176                 :     657339 :     case CLOBBER:
     177                 :     657339 :       if (fast)
     178                 :            :         {
     179                 :            :           /* A CLOBBER of a dead pseudo register serves no purpose.
     180                 :            :              That is not necessarily true for hard registers until
     181                 :            :              after reload.  */
     182                 :     546401 :           x = XEXP (body, 0);
     183                 :     546401 :           return REG_P (x) && (!HARD_REGISTER_P (x) || reload_completed);
     184                 :            :         }
     185                 :            :       else
     186                 :            :         /* Because of the way that use-def chains are built, it is not
     187                 :            :            possible to tell if the clobber is dead because it can
     188                 :            :            never be the target of a use-def chain.  */
     189                 :            :         return false;
     190                 :            : 
     191                 :   69469200 :     case PARALLEL:
     192                 :  212739000 :       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
     193                 :  144367000 :         if (!deletable_insn_p_1 (XVECEXP (body, 0, i)))
     194                 :            :           return false;
     195                 :            :       return true;
     196                 :            : 
     197                 :  324792000 :     default:
     198                 :  324792000 :       return deletable_insn_p_1 (body);
     199                 :            :     }
     200                 :            : }
     201                 :            : 
     202                 :            : 
     203                 :            : /* Return true if INSN has been marked as needed.  */
     204                 :            : 
     205                 :            : static inline int
     206                 : 1497710000 : marked_insn_p (rtx_insn *insn)
     207                 :            : {
     208                 :            :   /* Artificial defs are always needed and they do not have an insn.
     209                 :            :      We should never see them here.  */
     210                 : 1497710000 :   gcc_assert (insn);
     211                 : 1497710000 :   return bitmap_bit_p (marked, INSN_UID (insn));
     212                 :            : }
     213                 :            : 
     214                 :            : 
     215                 :            : /* If INSN has not yet been marked as needed, mark it now, and add it to
     216                 :            :    the worklist.  */
     217                 :            : 
     218                 :            : static void
     219                 :  526563000 : mark_insn (rtx_insn *insn, bool fast)
     220                 :            : {
     221                 :  526563000 :   if (!marked_insn_p (insn))
     222                 :            :     {
     223                 :  498190000 :       if (!fast)
     224                 :   35404500 :         worklist.safe_push (insn);
     225                 :  498190000 :       bitmap_set_bit (marked, INSN_UID (insn));
     226                 :  498190000 :       if (dump_file)
     227                 :       8935 :         fprintf (dump_file, "  Adding insn %d to worklist\n", INSN_UID (insn));
     228                 :  498190000 :       if (CALL_P (insn)
     229                 :   38777100 :           && !df_in_progress
     230                 :    9146280 :           && !SIBLING_CALL_P (insn)
     231                 :    8944400 :           && (RTL_CONST_OR_PURE_CALL_P (insn)
     232                 :     551955 :               && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn))
     233                 :  498664000 :           && can_delete_call (insn))
     234                 :     469700 :         find_call_stack_args (as_a <rtx_call_insn *> (insn), true, fast, NULL);
     235                 :            :     }
     236                 :  526563000 : }
     237                 :            : 
     238                 :            : 
     239                 :            : /* A note_stores callback used by mark_nonreg_stores.  DATA is the
     240                 :            :    instruction containing DEST.  */
     241                 :            : 
     242                 :            : static void
     243                 :  425508000 : mark_nonreg_stores_1 (rtx dest, const_rtx pattern, void *data)
     244                 :            : {
     245                 :  425508000 :   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
     246                 :   83371500 :     mark_insn ((rtx_insn *) data, true);
     247                 :  425508000 : }
     248                 :            : 
     249                 :            : 
     250                 :            : /* A note_stores callback used by mark_nonreg_stores.  DATA is the
     251                 :            :    instruction containing DEST.  */
     252                 :            : 
     253                 :            : static void
     254                 :   32984700 : mark_nonreg_stores_2 (rtx dest, const_rtx pattern, void *data)
     255                 :            : {
     256                 :   32984700 :   if (GET_CODE (pattern) != CLOBBER && !REG_P (dest))
     257                 :    5648110 :     mark_insn ((rtx_insn *) data, false);
     258                 :   32984700 : }
     259                 :            : 
     260                 :            : 
     261                 :            : /* Mark INSN if it stores to a non-register destination.  */
     262                 :            : 
     263                 :            : static void
     264                 :  386899000 : mark_nonreg_stores (rtx_insn *insn, bool fast)
     265                 :            : {
     266                 :  386899000 :   if (fast)
     267                 :  359189000 :     note_stores (insn, mark_nonreg_stores_1, insn);
     268                 :            :   else
     269                 :   27709900 :     note_stores (insn, mark_nonreg_stores_2, insn);
     270                 :  386899000 : }
     271                 :            : 
     272                 :            : 
     273                 :            : /* Return true if a store to SIZE bytes, starting OFF bytes from stack pointer,
     274                 :            :    is a call argument store, and clear corresponding bits from SP_BYTES
     275                 :            :    bitmap if it is.  */
     276                 :            : 
     277                 :            : static bool
     278                 :        336 : check_argument_store (HOST_WIDE_INT size, HOST_WIDE_INT off,
     279                 :            :                       HOST_WIDE_INT min_sp_off, HOST_WIDE_INT max_sp_off,
     280                 :            :                       bitmap sp_bytes)
     281                 :            : {
     282                 :        336 :   HOST_WIDE_INT byte;
     283                 :       2464 :   for (byte = off; byte < off + size; byte++)
     284                 :            :     {
     285                 :       2128 :       if (byte < min_sp_off
     286                 :       2128 :           || byte >= max_sp_off
     287                 :       2128 :           || !bitmap_clear_bit (sp_bytes, byte - min_sp_off))
     288                 :          0 :         return false;
     289                 :            :     }
     290                 :            :   return true;
     291                 :            : }
     292                 :            : 
     293                 :            : /* If MEM has sp address, return 0, if it has sp + const address,
     294                 :            :    return that const, if it has reg address where reg is set to sp + const
     295                 :            :    and FAST is false, return const, otherwise return
     296                 :            :    INTTYPE_MINUMUM (HOST_WIDE_INT).  */
     297                 :            : 
     298                 :            : static HOST_WIDE_INT
     299                 :        960 : sp_based_mem_offset (rtx_call_insn *call_insn, const_rtx mem, bool fast)
     300                 :            : {
     301                 :        960 :   HOST_WIDE_INT off = 0;
     302                 :        960 :   rtx addr = XEXP (mem, 0);
     303                 :        960 :   if (GET_CODE (addr) == PLUS
     304                 :        768 :       && REG_P (XEXP (addr, 0))
     305                 :        768 :       && CONST_INT_P (XEXP (addr, 1)))
     306                 :            :     {
     307                 :        768 :       off = INTVAL (XEXP (addr, 1));
     308                 :        768 :       addr = XEXP (addr, 0);
     309                 :            :     }
     310                 :        960 :   if (addr == stack_pointer_rtx)
     311                 :            :     return off;
     312                 :            : 
     313                 :         24 :   if (!REG_P (addr) || fast)
     314                 :            :     return INTTYPE_MINIMUM (HOST_WIDE_INT);
     315                 :            : 
     316                 :            :   /* If not fast, use chains to see if addr wasn't set to sp + offset.  */
     317                 :         24 :   df_ref use;
     318                 :         96 :   FOR_EACH_INSN_USE (use, call_insn)
     319                 :         72 :   if (rtx_equal_p (addr, DF_REF_REG (use)))
     320                 :            :     break;
     321                 :            : 
     322                 :         24 :   if (use == NULL)
     323                 :            :     return INTTYPE_MINIMUM (HOST_WIDE_INT);
     324                 :            : 
     325                 :          0 :   struct df_link *defs;
     326                 :          0 :   for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
     327                 :          0 :     if (! DF_REF_IS_ARTIFICIAL (defs->ref))
     328                 :            :       break;
     329                 :            : 
     330                 :          0 :   if (defs == NULL)
     331                 :            :     return INTTYPE_MINIMUM (HOST_WIDE_INT);
     332                 :            : 
     333                 :          0 :   rtx set = single_set (DF_REF_INSN (defs->ref));
     334                 :          0 :   if (!set)
     335                 :            :     return INTTYPE_MINIMUM (HOST_WIDE_INT);
     336                 :            : 
     337                 :          0 :   if (GET_CODE (SET_SRC (set)) != PLUS
     338                 :          0 :       || XEXP (SET_SRC (set), 0) != stack_pointer_rtx
     339                 :          0 :       || !CONST_INT_P (XEXP (SET_SRC (set), 1)))
     340                 :            :     return INTTYPE_MINIMUM (HOST_WIDE_INT);
     341                 :            : 
     342                 :          0 :   off += INTVAL (XEXP (SET_SRC (set), 1));
     343                 :          0 :   return off;
     344                 :            : }
     345                 :            : 
     346                 :            : /* Data for check_argument_load called via note_uses.  */
     347                 :            : struct check_argument_load_data {
     348                 :            :   bitmap sp_bytes;
     349                 :            :   HOST_WIDE_INT min_sp_off, max_sp_off;
     350                 :            :   rtx_call_insn *call_insn;
     351                 :            :   bool fast;
     352                 :            :   bool load_found;
     353                 :            : };
     354                 :            : 
     355                 :            : /* Helper function for find_call_stack_args.  Check if there are
     356                 :            :    any loads from the argument slots in between the const/pure call
     357                 :            :    and store to the argument slot, set LOAD_FOUND if any is found.  */
     358                 :            : 
     359                 :            : static void
     360                 :       1004 : check_argument_load (rtx *loc, void *data)
     361                 :            : {
     362                 :       1004 :   struct check_argument_load_data *d
     363                 :            :     = (struct check_argument_load_data *) data;
     364                 :       2008 :   subrtx_iterator::array_type array;
     365                 :       2700 :   FOR_EACH_SUBRTX (iter, array, *loc, NONCONST)
     366                 :            :     {
     367                 :       1696 :       const_rtx mem = *iter;
     368                 :       1696 :       HOST_WIDE_INT size;
     369                 :       1696 :       if (MEM_P (mem)
     370                 :         48 :           && MEM_SIZE_KNOWN_P (mem)
     371                 :       1744 :           && MEM_SIZE (mem).is_constant (&size))
     372                 :            :         {
     373                 :         48 :           HOST_WIDE_INT off = sp_based_mem_offset (d->call_insn, mem, d->fast);
     374                 :         48 :           if (off != INTTYPE_MINIMUM (HOST_WIDE_INT)
     375                 :         24 :               && off < d->max_sp_off
     376                 :          0 :               && off + size > d->min_sp_off)
     377                 :          0 :             for (HOST_WIDE_INT byte = MAX (off, d->min_sp_off);
     378                 :          0 :                  byte < MIN (off + size, d->max_sp_off); byte++)
     379                 :          0 :               if (bitmap_bit_p (d->sp_bytes, byte - d->min_sp_off))
     380                 :            :                 {
     381                 :          0 :                   d->load_found = true;
     382                 :          0 :                   return;
     383                 :            :                 }
     384                 :            :         }
     385                 :            :     }
     386                 :            : }
     387                 :            : 
     388                 :            : /* Try to find all stack stores of CALL_INSN arguments if
     389                 :            :    ACCUMULATE_OUTGOING_ARGS.  If all stack stores have been found
     390                 :            :    and it is therefore safe to eliminate the call, return true,
     391                 :            :    otherwise return false.  This function should be first called
     392                 :            :    with DO_MARK false, and only when the CALL_INSN is actually
     393                 :            :    going to be marked called again with DO_MARK true.  */
     394                 :            : 
     395                 :            : static bool
     396                 :     941345 : find_call_stack_args (rtx_call_insn *call_insn, bool do_mark, bool fast,
     397                 :            :                       bitmap arg_stores)
     398                 :            : {
     399                 :     941345 :   rtx p;
     400                 :     941345 :   rtx_insn *insn, *prev_insn;
     401                 :     941345 :   bool ret;
     402                 :     941345 :   HOST_WIDE_INT min_sp_off, max_sp_off;
     403                 :     941345 :   bitmap sp_bytes;
     404                 :            : 
     405                 :     941345 :   gcc_assert (CALL_P (call_insn));
     406                 :     941345 :   if (!ACCUMULATE_OUTGOING_ARGS)
     407                 :     940975 :     return true;
     408                 :            : 
     409                 :        370 :   if (!do_mark)
     410                 :            :     {
     411                 :        185 :       gcc_assert (arg_stores);
     412                 :        185 :       bitmap_clear (arg_stores);
     413                 :            :     }
     414                 :            : 
     415                 :        370 :   min_sp_off = INTTYPE_MAXIMUM (HOST_WIDE_INT);
     416                 :        370 :   max_sp_off = 0;
     417                 :            : 
     418                 :            :   /* First determine the minimum and maximum offset from sp for
     419                 :            :      stored arguments.  */
     420                 :       1364 :   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
     421                 :        994 :     if (GET_CODE (XEXP (p, 0)) == USE
     422                 :        958 :         && MEM_P (XEXP (XEXP (p, 0), 0)))
     423                 :            :       {
     424                 :        288 :         rtx mem = XEXP (XEXP (p, 0), 0);
     425                 :        288 :         HOST_WIDE_INT size;
     426                 :        288 :         if (!MEM_SIZE_KNOWN_P (mem) || !MEM_SIZE (mem).is_constant (&size))
     427                 :     941345 :           return false;
     428                 :        288 :         HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast);
     429                 :        288 :         if (off == INTTYPE_MINIMUM (HOST_WIDE_INT))
     430                 :            :           return false;
     431                 :        288 :         min_sp_off = MIN (min_sp_off, off);
     432                 :        288 :         max_sp_off = MAX (max_sp_off, off + size);
     433                 :            :       }
     434                 :            : 
     435                 :        370 :   if (min_sp_off >= max_sp_off)
     436                 :            :     return true;
     437                 :         64 :   sp_bytes = BITMAP_ALLOC (NULL);
     438                 :            : 
     439                 :            :   /* Set bits in SP_BYTES bitmap for bytes relative to sp + min_sp_off
     440                 :            :      which contain arguments.  Checking has been done in the previous
     441                 :            :      loop.  */
     442                 :        656 :   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
     443                 :        592 :     if (GET_CODE (XEXP (p, 0)) == USE
     444                 :        592 :         && MEM_P (XEXP (XEXP (p, 0), 0)))
     445                 :            :       {
     446                 :        288 :         rtx mem = XEXP (XEXP (p, 0), 0);
     447                 :            :         /* Checked in the previous iteration.  */
     448                 :        288 :         HOST_WIDE_INT size = MEM_SIZE (mem).to_constant ();
     449                 :        288 :         HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast);
     450                 :        288 :         gcc_checking_assert (off != INTTYPE_MINIMUM (HOST_WIDE_INT));
     451                 :       2416 :         for (HOST_WIDE_INT byte = off; byte < off + size; byte++)
     452                 :       2128 :           if (!bitmap_set_bit (sp_bytes, byte - min_sp_off))
     453                 :          0 :             gcc_unreachable ();
     454                 :            :       }
     455                 :            : 
     456                 :            :   /* Walk backwards, looking for argument stores.  The search stops
     457                 :            :      when seeing another call, sp adjustment, memory store other than
     458                 :            :      argument store or a read from an argument stack slot.  */
     459                 :         64 :   struct check_argument_load_data data
     460                 :         64 :     = { sp_bytes, min_sp_off, max_sp_off, call_insn, fast, false };
     461                 :         64 :   ret = false;
     462                 :        692 :   for (insn = PREV_INSN (call_insn); insn; insn = prev_insn)
     463                 :            :     {
     464                 :        692 :       if (insn == BB_HEAD (BLOCK_FOR_INSN (call_insn)))
     465                 :            :         prev_insn = NULL;
     466                 :            :       else
     467                 :        692 :         prev_insn = PREV_INSN (insn);
     468                 :            : 
     469                 :        692 :       if (CALL_P (insn))
     470                 :            :         break;
     471                 :            : 
     472                 :        692 :       if (!NONDEBUG_INSN_P (insn))
     473                 :         24 :         continue;
     474                 :            : 
     475                 :        668 :       rtx set = single_set (insn);
     476                 :        668 :       if (!set || SET_DEST (set) == stack_pointer_rtx)
     477                 :            :         break;
     478                 :            : 
     479                 :        668 :       note_uses (&PATTERN (insn), check_argument_load, &data);
     480                 :        668 :       if (data.load_found)
     481                 :            :         break;
     482                 :            : 
     483                 :        668 :       if (!MEM_P (SET_DEST (set)))
     484                 :        332 :         continue;
     485                 :            : 
     486                 :        336 :       rtx mem = SET_DEST (set);
     487                 :        336 :       HOST_WIDE_INT off = sp_based_mem_offset (call_insn, mem, fast);
     488                 :        336 :       if (off == INTTYPE_MINIMUM (HOST_WIDE_INT))
     489                 :            :         break;
     490                 :            : 
     491                 :        336 :       HOST_WIDE_INT size;
     492                 :        336 :       if (!MEM_SIZE_KNOWN_P (mem)
     493                 :        336 :           || !MEM_SIZE (mem).is_constant (&size)
     494                 :        336 :           || !check_argument_store (size, off, min_sp_off,
     495                 :            :                                     max_sp_off, sp_bytes))
     496                 :            :         break;
     497                 :            : 
     498                 :        336 :       if (!deletable_insn_p (insn, fast, NULL))
     499                 :            :         break;
     500                 :            : 
     501                 :        336 :       if (do_mark)
     502                 :        168 :         mark_insn (insn, fast);
     503                 :            :       else
     504                 :        168 :         bitmap_set_bit (arg_stores, INSN_UID (insn));
     505                 :            : 
     506                 :        336 :       if (bitmap_empty_p (sp_bytes))
     507                 :            :         {
     508                 :            :           ret = true;
     509                 :            :           break;
     510                 :            :         }
     511                 :            :     }
     512                 :            : 
     513                 :         64 :   BITMAP_FREE (sp_bytes);
     514                 :         64 :   if (!ret && arg_stores)
     515                 :          0 :     bitmap_clear (arg_stores);
     516                 :            : 
     517                 :            :   return ret;
     518                 :            : }
     519                 :            : 
     520                 :            : 
     521                 :            : /* Remove all REG_EQUAL and REG_EQUIV notes referring to the registers INSN
     522                 :            :    writes to.  */
     523                 :            : 
     524                 :            : static void
     525                 :    2423270 : remove_reg_equal_equiv_notes_for_defs (rtx_insn *insn)
     526                 :            : {
     527                 :    2423270 :   df_ref def;
     528                 :            : 
     529                 :    5088810 :   FOR_EACH_INSN_DEF (def, insn)
     530                 :    2665540 :     remove_reg_equal_equiv_notes_for_regno (DF_REF_REGNO (def));
     531                 :    2423270 : }
     532                 :            : 
     533                 :            : /* Scan all BBs for debug insns and reset those that reference values
     534                 :            :    defined in unmarked insns.  */
     535                 :            : 
     536                 :            : static void
     537                 :     335137 : reset_unmarked_insns_debug_uses (void)
     538                 :            : {
     539                 :     335137 :   basic_block bb;
     540                 :     335137 :   rtx_insn *insn, *next;
     541                 :            : 
     542                 :    4742340 :   FOR_EACH_BB_REVERSE_FN (bb, cfun)
     543                 :  128547000 :     FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
     544                 :   59866200 :       if (DEBUG_INSN_P (insn))
     545                 :            :         {
     546                 :   27980800 :           df_ref use;
     547                 :            : 
     548                 :   33418100 :           FOR_EACH_INSN_USE (use, insn)
     549                 :            :             {
     550                 :    5437350 :               struct df_link *defs;
     551                 :   12340500 :               for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
     552                 :            :                 {
     553                 :    6903180 :                   rtx_insn *ref_insn;
     554                 :    6903180 :                   if (DF_REF_IS_ARTIFICIAL (defs->ref))
     555                 :    1478850 :                     continue;
     556                 :    5424330 :                   ref_insn = DF_REF_INSN (defs->ref);
     557                 :    5424330 :                   if (!marked_insn_p (ref_insn))
     558                 :            :                     break;
     559                 :            :                 }
     560                 :    5437350 :               if (!defs)
     561                 :    5437300 :                 continue;
     562                 :            :               /* ??? FIXME could we propagate the values assigned to
     563                 :            :                  each of the DEFs?  */
     564                 :         56 :               INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
     565                 :         56 :               df_insn_rescan_debug_internal (insn);
     566                 :         56 :               break;
     567                 :            :             }
     568                 :            :         }
     569                 :     335137 : }
     570                 :            : 
     571                 :            : /* Delete every instruction that hasn't been marked.  */
     572                 :            : 
     573                 :            : static void
     574                 :    5338520 : delete_unmarked_insns (void)
     575                 :            : {
     576                 :    5338520 :   basic_block bb;
     577                 :    5338520 :   rtx_insn *insn, *next;
     578                 :    5338520 :   bool must_clean = false;
     579                 :            : 
     580                 :   95683400 :   FOR_EACH_BB_REVERSE_FN (bb, cfun)
     581                 : 2283720000 :     FOR_BB_INSNS_REVERSE_SAFE (bb, insn, next)
     582                 : 1051520000 :       if (NONDEBUG_INSN_P (insn))
     583                 :            :         {
     584                 :  500611000 :           rtx turn_into_use = NULL_RTX;
     585                 :            : 
     586                 :            :           /* Always delete no-op moves.  */
     587                 :  500611000 :           if (noop_move_p (insn)
     588                 :            :               /* Unless the no-op move can throw and we are not allowed
     589                 :            :                  to alter cfg.  */
     590                 :  500611000 :               && (!cfun->can_throw_non_call_exceptions
     591                 :       1009 :                   || (cfun->can_delete_dead_exceptions && can_alter_cfg)
     592                 :       1009 :                   || insn_nothrow_p (insn)))
     593                 :            :             {
     594                 :       2665 :               if (RTX_FRAME_RELATED_P (insn))
     595                 :          0 :                 turn_into_use
     596                 :          0 :                   = find_reg_note (insn, REG_CFA_RESTORE, NULL);
     597                 :          0 :               if (turn_into_use && REG_P (XEXP (turn_into_use, 0)))
     598                 :          0 :                 turn_into_use = XEXP (turn_into_use, 0);
     599                 :            :               else
     600                 :            :                 turn_into_use = NULL_RTX;
     601                 :            :             }
     602                 :            : 
     603                 :            :           /* Otherwise rely only on the DCE algorithm.  */
     604                 :  500608000 :           else if (marked_insn_p (insn))
     605                 :  498188000 :             continue;
     606                 :            : 
     607                 :            :           /* Beware that reaching a dbg counter limit here can result
     608                 :            :              in miscompiled file.  This occurs when a group of insns
     609                 :            :              must be deleted together, typically because the kept insn
     610                 :            :              depends on the output from the deleted insn.  Deleting
     611                 :            :              this insns in reverse order (both at the bb level and
     612                 :            :              when looking at the blocks) minimizes this, but does not
     613                 :            :              eliminate it, since it is possible for the using insn to
     614                 :            :              be top of a block and the producer to be at the bottom of
     615                 :            :              the block.  However, in most cases this will only result
     616                 :            :              in an uninitialized use of an insn that is dead anyway.
     617                 :            : 
     618                 :            :              However, there is one rare case that will cause a
     619                 :            :              miscompile: deletion of non-looping pure and constant
     620                 :            :              calls on a machine where ACCUMULATE_OUTGOING_ARGS is true.
     621                 :            :              In this case it is possible to remove the call, but leave
     622                 :            :              the argument pushes to the stack.  Because of the changes
     623                 :            :              to the stack pointer, this will almost always lead to a
     624                 :            :              miscompile.  */
     625                 :    2423270 :           if (!dbg_cnt (dce))
     626                 :          0 :             continue;
     627                 :            : 
     628                 :    2423270 :           if (dump_file)
     629                 :         65 :             fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
     630                 :            : 
     631                 :            :           /* Before we delete the insn we have to remove the REG_EQUAL notes
     632                 :            :              for the destination regs in order to avoid dangling notes.  */
     633                 :    2423270 :           remove_reg_equal_equiv_notes_for_defs (insn);
     634                 :            : 
     635                 :    2423270 :           if (turn_into_use)
     636                 :            :             {
     637                 :            :               /* Don't remove frame related noop moves if they cary
     638                 :            :                  REG_CFA_RESTORE note, while we don't need to emit any code,
     639                 :            :                  we need it to emit the CFI restore note.  */
     640                 :          0 :               PATTERN (insn)
     641                 :          0 :                 = gen_rtx_USE (GET_MODE (turn_into_use), turn_into_use);
     642                 :          0 :               INSN_CODE (insn) = -1;
     643                 :          0 :               df_insn_rescan (insn);
     644                 :            :             }
     645                 :            :           else
     646                 :            :             /* Now delete the insn.  */
     647                 :    2423270 :             must_clean |= delete_insn_and_edges (insn);
     648                 :            :         }
     649                 :            : 
     650                 :            :   /* Deleted a pure or const call.  */
     651                 :    5338520 :   if (must_clean)
     652                 :            :     {
     653                 :          7 :       gcc_assert (can_alter_cfg);
     654                 :          7 :       delete_unreachable_blocks ();
     655                 :          7 :       free_dominance_info (CDI_DOMINATORS);
     656                 :            :     }
     657                 :    5338520 : }
     658                 :            : 
     659                 :            : 
     660                 :            : /* Go through the instructions and mark those whose necessity is not
     661                 :            :    dependent on inter-instruction information.  Make sure all other
     662                 :            :    instructions are not marked.  */
     663                 :            : 
     664                 :            : static void
     665                 :    5338520 : prescan_insns_for_dce (bool fast)
     666                 :            : {
     667                 :    5338520 :   basic_block bb;
     668                 :    5338520 :   rtx_insn *insn, *prev;
     669                 :    5338520 :   bitmap arg_stores = NULL;
     670                 :            : 
     671                 :    5338520 :   if (dump_file)
     672                 :        267 :     fprintf (dump_file, "Finding needed instructions:\n");
     673                 :            : 
     674                 :    5338520 :   if (!df_in_progress && ACCUMULATE_OUTGOING_ARGS)
     675                 :      87717 :     arg_stores = BITMAP_ALLOC (NULL);
     676                 :            : 
     677                 :   95683400 :   FOR_EACH_BB_FN (bb, cfun)
     678                 :            :     {
     679                 : 2283360000 :       FOR_BB_INSNS_REVERSE_SAFE (bb, insn, prev)
     680                 : 1051340000 :         if (NONDEBUG_INSN_P (insn))
     681                 :            :           {
     682                 :            :             /* Don't mark argument stores now.  They will be marked
     683                 :            :                if needed when the associated CALL is marked.  */
     684                 :  500611000 :             if (arg_stores && bitmap_bit_p (arg_stores, INSN_UID (insn)))
     685                 :        168 :               continue;
     686                 :  500611000 :             if (deletable_insn_p (insn, fast, arg_stores))
     687                 :  386899000 :               mark_nonreg_stores (insn, fast);
     688                 :            :             else
     689                 :  113712000 :               mark_insn (insn, fast);
     690                 :            :           }
     691                 :            :       /* find_call_stack_args only looks at argument stores in the
     692                 :            :          same bb.  */
     693                 :   90344900 :       if (arg_stores)
     694                 :     119883 :         bitmap_clear (arg_stores);
     695                 :            :     }
     696                 :            : 
     697                 :    5338520 :   if (arg_stores)
     698                 :      87717 :     BITMAP_FREE (arg_stores);
     699                 :            : 
     700                 :    5338520 :   if (dump_file)
     701                 :        267 :     fprintf (dump_file, "Finished finding needed instructions:\n");
     702                 :    5338520 : }
     703                 :            : 
     704                 :            : 
     705                 :            : /* UD-based DSE routines. */
     706                 :            : 
     707                 :            : /* Mark instructions that define artificially-used registers, such as
     708                 :            :    the frame pointer and the stack pointer.  */
     709                 :            : 
     710                 :            : static void
     711                 :     645344 : mark_artificial_uses (void)
     712                 :            : {
     713                 :     645344 :   basic_block bb;
     714                 :     645344 :   struct df_link *defs;
     715                 :     645344 :   df_ref use;
     716                 :            : 
     717                 :    8235380 :   FOR_ALL_BB_FN (bb, cfun)
     718                 :   42692400 :     FOR_EACH_ARTIFICIAL_USE (use, bb->index)
     719                 :   57076300 :       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
     720                 :   29564000 :         if (!DF_REF_IS_ARTIFICIAL (defs->ref))
     721                 :    4094670 :           mark_insn (DF_REF_INSN (defs->ref), false);
     722                 :     645344 : }
     723                 :            : 
     724                 :            : 
     725                 :            : /* Mark every instruction that defines a register value that INSN uses.  */
     726                 :            : 
     727                 :            : static void
     728                 :   35404500 : mark_reg_dependencies (rtx_insn *insn)
     729                 :            : {
     730                 :   35404500 :   struct df_link *defs;
     731                 :   35404500 :   df_ref use;
     732                 :            : 
     733                 :   35404500 :   if (DEBUG_INSN_P (insn))
     734                 :            :     return;
     735                 :            : 
     736                 :   80778400 :   FOR_EACH_INSN_USE (use, insn)
     737                 :            :     {
     738                 :   45373900 :       if (dump_file)
     739                 :            :         {
     740                 :       1270 :           fprintf (dump_file, "Processing use of ");
     741                 :       1270 :           print_simple_rtl (dump_file, DF_REF_REG (use));
     742                 :       1270 :           fprintf (dump_file, " in insn %d:\n", INSN_UID (insn));
     743                 :            :         }
     744                 :   97024300 :       for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
     745                 :   51650400 :         if (! DF_REF_IS_ARTIFICIAL (defs->ref))
     746                 :   43487300 :           mark_insn (DF_REF_INSN (defs->ref), false);
     747                 :            :     }
     748                 :            : }
     749                 :            : 
     750                 :            : 
     751                 :            : /* Initialize global variables for a new DCE pass.  */
     752                 :            : 
     753                 :            : static void
     754                 :    5338480 : init_dce (bool fast)
     755                 :            : {
     756                 :    5338480 :   if (!df_in_progress)
     757                 :            :     {
     758                 :    1556960 :       if (!fast)
     759                 :            :         {
     760                 :     645344 :           df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
     761                 :     645344 :           df_chain_add_problem (DF_UD_CHAIN);
     762                 :            :         }
     763                 :    1556960 :       df_analyze ();
     764                 :            :     }
     765                 :            : 
     766                 :    5338480 :   if (dump_file)
     767                 :        267 :     df_dump (dump_file);
     768                 :            : 
     769                 :    5338480 :   if (fast)
     770                 :            :     {
     771                 :    4693130 :       bitmap_obstack_initialize (&dce_blocks_bitmap_obstack);
     772                 :    4693130 :       bitmap_obstack_initialize (&dce_tmp_bitmap_obstack);
     773                 :    4693130 :       can_alter_cfg = false;
     774                 :            :     }
     775                 :            :   else
     776                 :     645344 :     can_alter_cfg = true;
     777                 :            : 
     778                 :    5338480 :   marked = sbitmap_alloc (get_max_uid () + 1);
     779                 :    5338480 :   bitmap_clear (marked);
     780                 :    5338480 : }
     781                 :            : 
     782                 :            : 
     783                 :            : /* Free the data allocated by init_dce.  */
     784                 :            : 
     785                 :            : static void
     786                 :    5338480 : fini_dce (bool fast)
     787                 :            : {
     788                 :    5338480 :   sbitmap_free (marked);
     789                 :            : 
     790                 :    5338480 :   if (fast)
     791                 :            :     {
     792                 :    4693130 :       bitmap_obstack_release (&dce_blocks_bitmap_obstack);
     793                 :    4693130 :       bitmap_obstack_release (&dce_tmp_bitmap_obstack);
     794                 :            :     }
     795                 :    5338480 : }
     796                 :            : 
     797                 :            : 
     798                 :            : /* UD-chain based DCE.  */
     799                 :            : 
     800                 :            : static unsigned int
     801                 :     645344 : rest_of_handle_ud_dce (void)
     802                 :            : {
     803                 :     645344 :   rtx_insn *insn;
     804                 :            : 
     805                 :     645344 :   init_dce (false);
     806                 :            : 
     807                 :     645344 :   prescan_insns_for_dce (false);
     808                 :     645344 :   mark_artificial_uses ();
     809                 :   36049900 :   while (worklist.length () > 0)
     810                 :            :     {
     811                 :   35404500 :       insn = worklist.pop ();
     812                 :   35404500 :       mark_reg_dependencies (insn);
     813                 :            :     }
     814                 :     645344 :   worklist.release ();
     815                 :            : 
     816                 :     645344 :   if (MAY_HAVE_DEBUG_BIND_INSNS)
     817                 :     335137 :     reset_unmarked_insns_debug_uses ();
     818                 :            : 
     819                 :            :   /* Before any insns are deleted, we must remove the chains since
     820                 :            :      they are not bidirectional.  */
     821                 :     645344 :   df_remove_problem (df_chain);
     822                 :     645344 :   delete_unmarked_insns ();
     823                 :            : 
     824                 :     645344 :   fini_dce (false);
     825                 :     645344 :   return 0;
     826                 :            : }
     827                 :            : 
     828                 :            : 
     829                 :            : namespace {
     830                 :            : 
     831                 :            : const pass_data pass_data_ud_rtl_dce =
     832                 :            : {
     833                 :            :   RTL_PASS, /* type */
     834                 :            :   "ud_dce", /* name */
     835                 :            :   OPTGROUP_NONE, /* optinfo_flags */
     836                 :            :   TV_DCE, /* tv_id */
     837                 :            :   0, /* properties_required */
     838                 :            :   0, /* properties_provided */
     839                 :            :   0, /* properties_destroyed */
     840                 :            :   0, /* todo_flags_start */
     841                 :            :   TODO_df_finish, /* todo_flags_finish */
     842                 :            : };
     843                 :            : 
     844                 :            : class pass_ud_rtl_dce : public rtl_opt_pass
     845                 :            : {
     846                 :            : public:
     847                 :     200773 :   pass_ud_rtl_dce (gcc::context *ctxt)
     848                 :     401546 :     : rtl_opt_pass (pass_data_ud_rtl_dce, ctxt)
     849                 :            :   {}
     850                 :            : 
     851                 :            :   /* opt_pass methods: */
     852                 :     944101 :   virtual bool gate (function *)
     853                 :            :     {
     854                 :     944101 :       return optimize > 1 && flag_dce && dbg_cnt (dce_ud);
     855                 :            :     }
     856                 :            : 
     857                 :     645344 :   virtual unsigned int execute (function *)
     858                 :            :     {
     859                 :     645344 :       return rest_of_handle_ud_dce ();
     860                 :            :     }
     861                 :            : 
     862                 :            : }; // class pass_ud_rtl_dce
     863                 :            : 
     864                 :            : } // anon namespace
     865                 :            : 
     866                 :            : rtl_opt_pass *
     867                 :     200773 : make_pass_ud_rtl_dce (gcc::context *ctxt)
     868                 :            : {
     869                 :     200773 :   return new pass_ud_rtl_dce (ctxt);
     870                 :            : }
     871                 :            : 
     872                 :            : 
     873                 :            : /* -------------------------------------------------------------------------
     874                 :            :    Fast DCE functions
     875                 :            :    ------------------------------------------------------------------------- */
     876                 :            : 
     877                 :            : /* Process basic block BB.  Return true if the live_in set has
     878                 :            :    changed. REDO_OUT is true if the info at the bottom of the block
     879                 :            :    needs to be recalculated before starting.  AU is the proper set of
     880                 :            :    artificial uses.  Track global substitution of uses of dead pseudos
     881                 :            :    in debug insns using GLOBAL_DEBUG.  */
     882                 :            : 
     883                 :            : static bool
     884                 :    2147940 : word_dce_process_block (basic_block bb, bool redo_out,
     885                 :            :                         struct dead_debug_global *global_debug)
     886                 :            : {
     887                 :    2147940 :   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
     888                 :    2147940 :   rtx_insn *insn;
     889                 :    2147940 :   bool block_changed;
     890                 :    2147940 :   struct dead_debug_local debug;
     891                 :            : 
     892                 :    2147940 :   if (redo_out)
     893                 :            :     {
     894                 :            :       /* Need to redo the live_out set of this block if when one of
     895                 :            :          the succs of this block has had a change in it live in
     896                 :            :          set.  */
     897                 :          0 :       edge e;
     898                 :          0 :       edge_iterator ei;
     899                 :          0 :       df_confluence_function_n con_fun_n = df_word_lr->problem->con_fun_n;
     900                 :          0 :       bitmap_clear (DF_WORD_LR_OUT (bb));
     901                 :          0 :       FOR_EACH_EDGE (e, ei, bb->succs)
     902                 :          0 :         (*con_fun_n) (e);
     903                 :            :     }
     904                 :            : 
     905                 :    2147940 :   if (dump_file)
     906                 :            :     {
     907                 :          0 :       fprintf (dump_file, "processing block %d live out = ", bb->index);
     908                 :          0 :       df_print_word_regset (dump_file, DF_WORD_LR_OUT (bb));
     909                 :            :     }
     910                 :            : 
     911                 :    4295880 :   bitmap_copy (local_live, DF_WORD_LR_OUT (bb));
     912                 :    2147940 :   dead_debug_local_init (&debug, NULL, global_debug);
     913                 :            : 
     914                 :   48725900 :   FOR_BB_INSNS_REVERSE (bb, insn)
     915                 :   23289000 :     if (DEBUG_INSN_P (insn))
     916                 :            :       {
     917                 :    6025980 :         df_ref use;
     918                 :    7508950 :         FOR_EACH_INSN_USE (use, insn)
     919                 :    1482980 :           if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
     920                 :    2733320 :               && known_eq (GET_MODE_SIZE (GET_MODE (DF_REF_REAL_REG (use))),
     921                 :            :                            2 * UNITS_PER_WORD)
     922                 :      81811 :               && !bitmap_bit_p (local_live, 2 * DF_REF_REGNO (use))
     923                 :    1484710 :               && !bitmap_bit_p (local_live, 2 * DF_REF_REGNO (use) + 1))
     924                 :        257 :             dead_debug_add (&debug, use, DF_REF_REGNO (use));
     925                 :            :       }
     926                 :   17263000 :     else if (INSN_P (insn))
     927                 :            :       {
     928                 :   13327700 :         bool any_changed;
     929                 :            : 
     930                 :            :         /* No matter if the instruction is needed or not, we remove
     931                 :            :            any regno in the defs from the live set.  */
     932                 :   13327700 :         any_changed = df_word_lr_simulate_defs (insn, local_live);
     933                 :   13327700 :         if (any_changed)
     934                 :    9757200 :           mark_insn (insn, true);
     935                 :            : 
     936                 :            :         /* On the other hand, we do not allow the dead uses to set
     937                 :            :            anything in local_live.  */
     938                 :   13327700 :         if (marked_insn_p (insn))
     939                 :   13320400 :           df_word_lr_simulate_uses (insn, local_live);
     940                 :            : 
     941                 :            :         /* Insert debug temps for dead REGs used in subsequent debug
     942                 :            :            insns.  We may have to emit a debug temp even if the insn
     943                 :            :            was marked, in case the debug use was after the point of
     944                 :            :            death.  */
     945                 :   13327700 :         if (debug.used && !bitmap_empty_p (debug.used))
     946                 :            :           {
     947                 :      25448 :             df_ref def;
     948                 :            : 
     949                 :      56083 :             FOR_EACH_INSN_DEF (def, insn)
     950                 :      61140 :               dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn,
     951                 :      30635 :                                       marked_insn_p (insn)
     952                 :      30505 :                                       && !control_flow_insn_p (insn)
     953                 :            :                                       ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
     954                 :            :                                       : DEBUG_TEMP_BEFORE_WITH_VALUE);
     955                 :            :           }
     956                 :            : 
     957                 :   13327700 :         if (dump_file)
     958                 :            :           {
     959                 :          0 :             fprintf (dump_file, "finished processing insn %d live out = ",
     960                 :          0 :                      INSN_UID (insn));
     961                 :          0 :             df_print_word_regset (dump_file, local_live);
     962                 :            :           }
     963                 :            :       }
     964                 :            : 
     965                 :    4295880 :   block_changed = !bitmap_equal_p (local_live, DF_WORD_LR_IN (bb));
     966                 :    2147940 :   if (block_changed)
     967                 :          0 :     bitmap_copy (DF_WORD_LR_IN (bb), local_live);
     968                 :            : 
     969                 :    2147940 :   dead_debug_local_finish (&debug, NULL);
     970                 :    2147940 :   BITMAP_FREE (local_live);
     971                 :    2147940 :   return block_changed;
     972                 :            : }
     973                 :            : 
     974                 :            : 
     975                 :            : /* Process basic block BB.  Return true if the live_in set has
     976                 :            :    changed. REDO_OUT is true if the info at the bottom of the block
     977                 :            :    needs to be recalculated before starting.  AU is the proper set of
     978                 :            :    artificial uses.  Track global substitution of uses of dead pseudos
     979                 :            :    in debug insns using GLOBAL_DEBUG.  */
     980                 :            : 
     981                 :            : static bool
     982                 :   81897600 : dce_process_block (basic_block bb, bool redo_out, bitmap au,
     983                 :            :                    struct dead_debug_global *global_debug)
     984                 :            : {
     985                 :   81897600 :   bitmap local_live = BITMAP_ALLOC (&dce_tmp_bitmap_obstack);
     986                 :   81897600 :   rtx_insn *insn;
     987                 :   81897600 :   bool block_changed;
     988                 :   81897600 :   df_ref def;
     989                 :   81897600 :   struct dead_debug_local debug;
     990                 :            : 
     991                 :   81897600 :   if (redo_out)
     992                 :            :     {
     993                 :            :       /* Need to redo the live_out set of this block if when one of
     994                 :            :          the succs of this block has had a change in it live in
     995                 :            :          set.  */
     996                 :      38135 :       edge e;
     997                 :      38135 :       edge_iterator ei;
     998                 :      38135 :       df_confluence_function_n con_fun_n = df_lr->problem->con_fun_n;
     999                 :      76270 :       bitmap_clear (DF_LR_OUT (bb));
    1000                 :     108926 :       FOR_EACH_EDGE (e, ei, bb->succs)
    1001                 :      70791 :         (*con_fun_n) (e);
    1002                 :            :     }
    1003                 :            : 
    1004                 :   81897600 :   if (dump_file)
    1005                 :            :     {
    1006                 :       1709 :       fprintf (dump_file, "processing block %d lr out = ", bb->index);
    1007                 :       3418 :       df_print_regset (dump_file, DF_LR_OUT (bb));
    1008                 :            :     }
    1009                 :            : 
    1010                 :  163795000 :   bitmap_copy (local_live, DF_LR_OUT (bb));
    1011                 :            : 
    1012                 :   81897600 :   df_simulate_initialize_backwards (bb, local_live);
    1013                 :   81897600 :   dead_debug_local_init (&debug, NULL, global_debug);
    1014                 :            : 
    1015                 : 1991320000 :   FOR_BB_INSNS_REVERSE (bb, insn)
    1016                 :  954709000 :     if (DEBUG_INSN_P (insn))
    1017                 :            :       {
    1018                 :  356689000 :         df_ref use;
    1019                 :  428083000 :         FOR_EACH_INSN_USE (use, insn)
    1020                 :   71393600 :           if (!bitmap_bit_p (local_live, DF_REF_REGNO (use))
    1021                 :   71393600 :               && !bitmap_bit_p (au, DF_REF_REGNO (use)))
    1022                 :     188915 :             dead_debug_add (&debug, use, DF_REF_REGNO (use));
    1023                 :            :       }
    1024                 :  598020000 :     else if (INSN_P (insn))
    1025                 :            :       {
    1026                 :  451754000 :         bool needed = marked_insn_p (insn);
    1027                 :            : 
    1028                 :            :         /* The insn is needed if there is someone who uses the output.  */
    1029                 :  451754000 :         if (!needed)
    1030                 :  323736000 :           FOR_EACH_INSN_DEF (def, insn)
    1031                 :  321447000 :             if (bitmap_bit_p (local_live, DF_REF_REGNO (def))
    1032                 :  321447000 :                 || bitmap_bit_p (au, DF_REF_REGNO (def)))
    1033                 :            :               {
    1034                 :  266493000 :                 needed = true;
    1035                 :  266493000 :                 mark_insn (insn, true);
    1036                 :  266493000 :                 break;
    1037                 :            :               }
    1038                 :            : 
    1039                 :            :         /* No matter if the instruction is needed or not, we remove
    1040                 :            :            any regno in the defs from the live set.  */
    1041                 :  451754000 :         df_simulate_defs (insn, local_live);
    1042                 :            : 
    1043                 :            :         /* On the other hand, we do not allow the dead uses to set
    1044                 :            :            anything in local_live.  */
    1045                 :  451754000 :         if (needed)
    1046                 :  449465000 :           df_simulate_uses (insn, local_live);
    1047                 :            : 
    1048                 :            :         /* Insert debug temps for dead REGs used in subsequent debug
    1049                 :            :            insns.  We may have to emit a debug temp even if the insn
    1050                 :            :            was marked, in case the debug use was after the point of
    1051                 :            :            death.  */
    1052                 :  451754000 :         if (debug.used && !bitmap_empty_p (debug.used))
    1053                 :   43341400 :           FOR_EACH_INSN_DEF (def, insn)
    1054                 :   70767100 :             dead_debug_insert_temp (&debug, DF_REF_REGNO (def), insn,
    1055                 :   35344600 :                                     needed && !control_flow_insn_p (insn)
    1056                 :            :                                     ? DEBUG_TEMP_AFTER_WITH_REG_FORCE
    1057                 :            :                                     : DEBUG_TEMP_BEFORE_WITH_VALUE);
    1058                 :            :       }
    1059                 :            : 
    1060                 :   81897600 :   dead_debug_local_finish (&debug, NULL);
    1061                 :   81897600 :   df_simulate_finalize_backwards (bb, local_live);
    1062                 :            : 
    1063                 :  163795000 :   block_changed = !bitmap_equal_p (local_live, DF_LR_IN (bb));
    1064                 :   81897600 :   if (block_changed)
    1065                 :      89116 :     bitmap_copy (DF_LR_IN (bb), local_live);
    1066                 :            : 
    1067                 :   81897600 :   BITMAP_FREE (local_live);
    1068                 :   81897600 :   return block_changed;
    1069                 :            : }
    1070                 :            : 
    1071                 :            : 
    1072                 :            : /* Perform fast DCE once initialization is done.  If WORD_LEVEL is
    1073                 :            :    true, use the word level dce, otherwise do it at the pseudo
    1074                 :            :    level.  */
    1075                 :            : 
    1076                 :            : static void
    1077                 :    4693130 : fast_dce (bool word_level)
    1078                 :            : {
    1079                 :    4693130 :   int *postorder = df_get_postorder (DF_BACKWARD);
    1080                 :    4693130 :   int n_blocks = df_get_n_blocks (DF_BACKWARD);
    1081                 :            :   /* The set of blocks that have been seen on this iteration.  */
    1082                 :    4693130 :   bitmap processed = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
    1083                 :            :   /* The set of blocks that need to have the out vectors reset because
    1084                 :            :      the in of one of their successors has changed.  */
    1085                 :    4693130 :   bitmap redo_out = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
    1086                 :    4693130 :   bitmap all_blocks = BITMAP_ALLOC (&dce_blocks_bitmap_obstack);
    1087                 :    4693130 :   bool global_changed = true;
    1088                 :            : 
    1089                 :            :   /* These regs are considered always live so if they end up dying
    1090                 :            :      because of some def, we need to bring the back again.  Calling
    1091                 :            :      df_simulate_fixup_sets has the disadvantage of calling
    1092                 :            :      bb_has_eh_pred once per insn, so we cache the information
    1093                 :            :      here.  */
    1094                 :    4693130 :   bitmap au = &df->regular_block_artificial_uses;
    1095                 :    4693130 :   bitmap au_eh = &df->eh_block_artificial_uses;
    1096                 :    4693130 :   int i;
    1097                 :    4693130 :   struct dead_debug_global global_debug;
    1098                 :            : 
    1099                 :    4693130 :   prescan_insns_for_dce (true);
    1100                 :            : 
    1101                 :   98118700 :   for (i = 0; i < n_blocks; i++)
    1102                 :   93425500 :     bitmap_set_bit (all_blocks, postorder[i]);
    1103                 :            : 
    1104                 :    4693130 :   dead_debug_global_init (&global_debug, NULL);
    1105                 :            : 
    1106                 :    9386300 :   while (global_changed)
    1107                 :            :     {
    1108                 :            :       global_changed = false;
    1109                 :            : 
    1110                 :   98125100 :       for (i = 0; i < n_blocks; i++)
    1111                 :            :         {
    1112                 :   93431900 :           int index = postorder[i];
    1113                 :   93431900 :           basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
    1114                 :   93431900 :           bool local_changed;
    1115                 :            : 
    1116                 :   93431900 :           if (index < NUM_FIXED_BLOCKS)
    1117                 :            :             {
    1118                 :    9386350 :               bitmap_set_bit (processed, index);
    1119                 :    9386350 :               continue;
    1120                 :            :             }
    1121                 :            : 
    1122                 :   84045600 :           if (word_level)
    1123                 :    2147940 :             local_changed
    1124                 :    2147940 :               = word_dce_process_block (bb, bitmap_bit_p (redo_out, index),
    1125                 :            :                                         &global_debug);
    1126                 :            :           else
    1127                 :   81897600 :             local_changed
    1128                 :  162034000 :               = dce_process_block (bb, bitmap_bit_p (redo_out, index),
    1129                 :   81897600 :                                    bb_has_eh_pred (bb) ? au_eh : au,
    1130                 :            :                                    &global_debug);
    1131                 :   84045600 :           bitmap_set_bit (processed, index);
    1132                 :            : 
    1133                 :   84045600 :           if (local_changed)
    1134                 :            :             {
    1135                 :      44558 :               edge e;
    1136                 :      44558 :               edge_iterator ei;
    1137                 :      96059 :               FOR_EACH_EDGE (e, ei, bb->preds)
    1138                 :      51501 :                 if (bitmap_bit_p (processed, e->src->index))
    1139                 :            :                   /* Be tricky about when we need to iterate the
    1140                 :            :                      analysis.  We only have redo the analysis if the
    1141                 :            :                      bitmaps change at the top of a block that is the
    1142                 :            :                      entry to a loop.  */
    1143                 :            :                   global_changed = true;
    1144                 :            :                 else
    1145                 :      51451 :                   bitmap_set_bit (redo_out, e->src->index);
    1146                 :            :             }
    1147                 :            :         }
    1148                 :            : 
    1149                 :    4693170 :       if (global_changed)
    1150                 :            :         {
    1151                 :            :           /* Turn off the RUN_DCE flag to prevent recursive calls to
    1152                 :            :              dce.  */
    1153                 :         43 :           int old_flag = df_clear_flags (DF_LR_RUN_DCE);
    1154                 :            : 
    1155                 :            :           /* So something was deleted that requires a redo.  Do it on
    1156                 :            :              the cheap.  */
    1157                 :         43 :           delete_unmarked_insns ();
    1158                 :         43 :           bitmap_clear (marked);
    1159                 :         43 :           bitmap_clear (processed);
    1160                 :         43 :           bitmap_clear (redo_out);
    1161                 :            : 
    1162                 :            :           /* We do not need to rescan any instructions.  We only need
    1163                 :            :              to redo the dataflow equations for the blocks that had a
    1164                 :            :              change at the top of the block.  Then we need to redo the
    1165                 :            :              iteration.  */
    1166                 :         43 :           if (word_level)
    1167                 :          0 :             df_analyze_problem (df_word_lr, all_blocks, postorder, n_blocks);
    1168                 :            :           else
    1169                 :         43 :             df_analyze_problem (df_lr, all_blocks, postorder, n_blocks);
    1170                 :            : 
    1171                 :         43 :           if (old_flag & DF_LR_RUN_DCE)
    1172                 :         35 :             df_set_flags (DF_LR_RUN_DCE);
    1173                 :            : 
    1174                 :         43 :           prescan_insns_for_dce (true);
    1175                 :            :         }
    1176                 :            :     }
    1177                 :            : 
    1178                 :    4693130 :   dead_debug_global_finish (&global_debug, NULL);
    1179                 :            : 
    1180                 :    4693130 :   delete_unmarked_insns ();
    1181                 :            : 
    1182                 :    4693130 :   BITMAP_FREE (processed);
    1183                 :    4693130 :   BITMAP_FREE (redo_out);
    1184                 :    4693130 :   BITMAP_FREE (all_blocks);
    1185                 :    4693130 : }
    1186                 :            : 
    1187                 :            : 
    1188                 :            : /* Fast register level DCE.  */
    1189                 :            : 
    1190                 :            : static unsigned int
    1191                 :    4605360 : rest_of_handle_fast_dce (void)
    1192                 :            : {
    1193                 :    4605360 :   init_dce (true);
    1194                 :    4605360 :   fast_dce (false);
    1195                 :    4605360 :   fini_dce (true);
    1196                 :    4605360 :   return 0;
    1197                 :            : }
    1198                 :            : 
    1199                 :            : 
    1200                 :            : /* Fast byte level DCE.  */
    1201                 :            : 
    1202                 :            : void
    1203                 :      87775 : run_word_dce (void)
    1204                 :            : {
    1205                 :      87775 :   int old_flags;
    1206                 :            : 
    1207                 :      87775 :   if (!flag_dce)
    1208                 :            :     return;
    1209                 :            : 
    1210                 :      87769 :   timevar_push (TV_DCE);
    1211                 :      87769 :   old_flags = df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
    1212                 :      87769 :   df_word_lr_add_problem ();
    1213                 :      87769 :   init_dce (true);
    1214                 :      87769 :   fast_dce (true);
    1215                 :      87769 :   fini_dce (true);
    1216                 :      87769 :   df_set_flags (old_flags);
    1217                 :      87769 :   timevar_pop (TV_DCE);
    1218                 :            : }
    1219                 :            : 
    1220                 :            : 
    1221                 :            : /* This is an internal call that is used by the df live register
    1222                 :            :    problem to run fast dce as a side effect of creating the live
    1223                 :            :    information.  The stack is organized so that the lr problem is run,
    1224                 :            :    this pass is run, which updates the live info and the df scanning
    1225                 :            :    info, and then returns to allow the rest of the problems to be run.
    1226                 :            : 
    1227                 :            :    This can be called by elsewhere but it will not update the bit
    1228                 :            :    vectors for any other problems than LR.  */
    1229                 :            : 
    1230                 :            : void
    1231                 :    3781710 : run_fast_df_dce (void)
    1232                 :            : {
    1233                 :    3781710 :   if (flag_dce)
    1234                 :            :     {
    1235                 :            :       /* If dce is able to delete something, it has to happen
    1236                 :            :          immediately.  Otherwise there will be problems handling the
    1237                 :            :          eq_notes.  */
    1238                 :    3781510 :       int old_flags =
    1239                 :    3781510 :         df_clear_flags (DF_DEFER_INSN_RESCAN + DF_NO_INSN_RESCAN);
    1240                 :            : 
    1241                 :    3781510 :       df_in_progress = true;
    1242                 :    3781510 :       rest_of_handle_fast_dce ();
    1243                 :    3781510 :       df_in_progress = false;
    1244                 :            : 
    1245                 :    3781510 :       df_set_flags (old_flags);
    1246                 :            :     }
    1247                 :    3781710 : }
    1248                 :            : 
    1249                 :            : 
    1250                 :            : /* Run a fast DCE pass.  */
    1251                 :            : 
    1252                 :            : void
    1253                 :     135345 : run_fast_dce (void)
    1254                 :            : {
    1255                 :     135345 :   if (flag_dce)
    1256                 :     135336 :     rest_of_handle_fast_dce ();
    1257                 :     135345 : }
    1258                 :            : 
    1259                 :            : 
    1260                 :            : namespace {
    1261                 :            : 
    1262                 :            : const pass_data pass_data_fast_rtl_dce =
    1263                 :            : {
    1264                 :            :   RTL_PASS, /* type */
    1265                 :            :   "rtl_dce", /* name */
    1266                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    1267                 :            :   TV_DCE, /* tv_id */
    1268                 :            :   0, /* properties_required */
    1269                 :            :   0, /* properties_provided */
    1270                 :            :   0, /* properties_destroyed */
    1271                 :            :   0, /* todo_flags_start */
    1272                 :            :   TODO_df_finish, /* todo_flags_finish */
    1273                 :            : };
    1274                 :            : 
    1275                 :            : class pass_fast_rtl_dce : public rtl_opt_pass
    1276                 :            : {
    1277                 :            : public:
    1278                 :     200773 :   pass_fast_rtl_dce (gcc::context *ctxt)
    1279                 :     401546 :     : rtl_opt_pass (pass_data_fast_rtl_dce, ctxt)
    1280                 :            :   {}
    1281                 :            : 
    1282                 :            :   /* opt_pass methods: */
    1283                 :     944101 :   virtual bool gate (function *)
    1284                 :            :     {
    1285                 :     944101 :       return optimize > 0 && flag_dce && dbg_cnt (dce_fast);
    1286                 :            :     }
    1287                 :            : 
    1288                 :     688513 :   virtual unsigned int execute (function *)
    1289                 :            :     {
    1290                 :     688513 :       return rest_of_handle_fast_dce ();
    1291                 :            :     }
    1292                 :            : 
    1293                 :            : }; // class pass_fast_rtl_dce
    1294                 :            : 
    1295                 :            : } // anon namespace
    1296                 :            : 
    1297                 :            : rtl_opt_pass *
    1298                 :     200773 : make_pass_fast_rtl_dce (gcc::context *ctxt)
    1299                 :            : {
    1300                 :     200773 :   return new pass_fast_rtl_dce (ctxt);
    1301                 :            : }

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.