LCOV - code coverage report
Current view: top level - gcc - tree-ssa-dce.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 728 749 97.2 %
Date: 2020-03-28 11:57:23 Functions: 31 33 93.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Dead code elimination pass for the GNU compiler.
       2                 :            :    Copyright (C) 2002-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Ben Elliston <bje@redhat.com>
       4                 :            :    and Andrew MacLeod <amacleod@redhat.com>
       5                 :            :    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
       6                 :            : 
       7                 :            : This file is part of GCC.
       8                 :            : 
       9                 :            : GCC is free software; you can redistribute it and/or modify it
      10                 :            : under the terms of the GNU General Public License as published by the
      11                 :            : Free Software Foundation; either version 3, or (at your option) any
      12                 :            : later version.
      13                 :            : 
      14                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT
      15                 :            : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      16                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      17                 :            : for more details.
      18                 :            : 
      19                 :            : You should have received a copy of the GNU General Public License
      20                 :            : along with GCC; see the file COPYING3.  If not see
      21                 :            : <http://www.gnu.org/licenses/>.  */
      22                 :            : 
      23                 :            : /* Dead code elimination.
      24                 :            : 
      25                 :            :    References:
      26                 :            : 
      27                 :            :      Building an Optimizing Compiler,
      28                 :            :      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
      29                 :            : 
      30                 :            :      Advanced Compiler Design and Implementation,
      31                 :            :      Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10.
      32                 :            : 
      33                 :            :    Dead-code elimination is the removal of statements which have no
      34                 :            :    impact on the program's output.  "Dead statements" have no impact
      35                 :            :    on the program's output, while "necessary statements" may have
      36                 :            :    impact on the output.
      37                 :            : 
      38                 :            :    The algorithm consists of three phases:
      39                 :            :    1. Marking as necessary all statements known to be necessary,
      40                 :            :       e.g. most function calls, writing a value to memory, etc;
      41                 :            :    2. Propagating necessary statements, e.g., the statements
      42                 :            :       giving values to operands in necessary statements; and
      43                 :            :    3. Removing dead statements.  */
      44                 :            : 
      45                 :            : #include "config.h"
      46                 :            : #include "system.h"
      47                 :            : #include "coretypes.h"
      48                 :            : #include "backend.h"
      49                 :            : #include "rtl.h"
      50                 :            : #include "tree.h"
      51                 :            : #include "gimple.h"
      52                 :            : #include "cfghooks.h"
      53                 :            : #include "tree-pass.h"
      54                 :            : #include "ssa.h"
      55                 :            : #include "gimple-pretty-print.h"
      56                 :            : #include "fold-const.h"
      57                 :            : #include "calls.h"
      58                 :            : #include "cfganal.h"
      59                 :            : #include "tree-eh.h"
      60                 :            : #include "gimplify.h"
      61                 :            : #include "gimple-iterator.h"
      62                 :            : #include "tree-cfg.h"
      63                 :            : #include "tree-ssa-loop-niter.h"
      64                 :            : #include "tree-into-ssa.h"
      65                 :            : #include "tree-dfa.h"
      66                 :            : #include "cfgloop.h"
      67                 :            : #include "tree-scalar-evolution.h"
      68                 :            : #include "tree-ssa-propagate.h"
      69                 :            : #include "gimple-fold.h"
      70                 :            : 
      71                 :            : static struct stmt_stats
      72                 :            : {
      73                 :            :   int total;
      74                 :            :   int total_phis;
      75                 :            :   int removed;
      76                 :            :   int removed_phis;
      77                 :            : } stats;
      78                 :            : 
      79                 :            : #define STMT_NECESSARY GF_PLF_1
      80                 :            : 
      81                 :            : static vec<gimple *> worklist;
      82                 :            : 
      83                 :            : /* Vector indicating an SSA name has already been processed and marked
      84                 :            :    as necessary.  */
      85                 :            : static sbitmap processed;
      86                 :            : 
      87                 :            : /* Vector indicating that the last statement of a basic block has already
      88                 :            :    been marked as necessary.  */
      89                 :            : static sbitmap last_stmt_necessary;
      90                 :            : 
      91                 :            : /* Vector indicating that BB contains statements that are live.  */
      92                 :            : static sbitmap bb_contains_live_stmts;
      93                 :            : 
      94                 :            : /* Before we can determine whether a control branch is dead, we need to
      95                 :            :    compute which blocks are control dependent on which edges.
      96                 :            : 
      97                 :            :    We expect each block to be control dependent on very few edges so we
      98                 :            :    use a bitmap for each block recording its edges.  An array holds the
      99                 :            :    bitmap.  The Ith bit in the bitmap is set if that block is dependent
     100                 :            :    on the Ith edge.  */
     101                 :            : static control_dependences *cd;
     102                 :            : 
     103                 :            : /* Vector indicating that a basic block has already had all the edges
     104                 :            :    processed that it is control dependent on.  */
     105                 :            : static sbitmap visited_control_parents;
     106                 :            : 
     107                 :            : /* TRUE if this pass alters the CFG (by removing control statements).
     108                 :            :    FALSE otherwise.
     109                 :            : 
     110                 :            :    If this pass alters the CFG, then it will arrange for the dominators
     111                 :            :    to be recomputed.  */
     112                 :            : static bool cfg_altered;
     113                 :            : 
     114                 :            : /* When non-NULL holds map from basic block index into the postorder.  */
     115                 :            : static int *bb_postorder;
     116                 :            : 
     117                 :            : 
     118                 :            : /* True if we should treat any stmt with a vdef as necessary.  */
     119                 :            : 
     120                 :            : static inline bool
     121                 :  159136000 : keep_all_vdefs_p ()
     122                 :            : {
     123                 :  159136000 :   return optimize_debug;
     124                 :            : }
     125                 :            : 
     126                 :            : /* If STMT is not already marked necessary, mark it, and add it to the
     127                 :            :    worklist if ADD_TO_WORKLIST is true.  */
     128                 :            : 
     129                 :            : static inline void
     130                 :  262741000 : mark_stmt_necessary (gimple *stmt, bool add_to_worklist)
     131                 :            : {
     132                 :  262741000 :   gcc_assert (stmt);
     133                 :            : 
     134                 :  262741000 :   if (gimple_plf (stmt, STMT_NECESSARY))
     135                 :            :     return;
     136                 :            : 
     137                 :  262741000 :   if (dump_file && (dump_flags & TDF_DETAILS))
     138                 :            :     {
     139                 :        198 :       fprintf (dump_file, "Marking useful stmt: ");
     140                 :        198 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
     141                 :        198 :       fprintf (dump_file, "\n");
     142                 :            :     }
     143                 :            : 
     144                 :  262741000 :   gimple_set_plf (stmt, STMT_NECESSARY, true);
     145                 :  262741000 :   if (add_to_worklist)
     146                 :   60941800 :     worklist.safe_push (stmt);
     147                 :  262741000 :   if (add_to_worklist && bb_contains_live_stmts && !is_gimple_debug (stmt))
     148                 :   22442800 :     bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
     149                 :            : }
     150                 :            : 
     151                 :            : 
     152                 :            : /* Mark the statement defining operand OP as necessary.  */
     153                 :            : 
     154                 :            : static inline void
     155                 :  200153000 : mark_operand_necessary (tree op)
     156                 :            : {
     157                 :  200153000 :   gimple *stmt;
     158                 :  200153000 :   int ver;
     159                 :            : 
     160                 :  200153000 :   gcc_assert (op);
     161                 :            : 
     162                 :  200153000 :   ver = SSA_NAME_VERSION (op);
     163                 :  200153000 :   if (bitmap_bit_p (processed, ver))
     164                 :            :     {
     165                 :   70894600 :       stmt = SSA_NAME_DEF_STMT (op);
     166                 :   70894600 :       gcc_assert (gimple_nop_p (stmt)
     167                 :            :                   || gimple_plf (stmt, STMT_NECESSARY));
     168                 :  110762000 :       return;
     169                 :            :     }
     170                 :  129258000 :   bitmap_set_bit (processed, ver);
     171                 :            : 
     172                 :  129258000 :   stmt = SSA_NAME_DEF_STMT (op);
     173                 :  129258000 :   gcc_assert (stmt);
     174                 :            : 
     175                 :  129258000 :   if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
     176                 :            :     return;
     177                 :            : 
     178                 :   89391000 :   if (dump_file && (dump_flags & TDF_DETAILS))
     179                 :            :     {
     180                 :         64 :       fprintf (dump_file, "marking necessary through ");
     181                 :         64 :       print_generic_expr (dump_file, op);
     182                 :         64 :       fprintf (dump_file, " stmt ");
     183                 :         64 :       print_gimple_stmt (dump_file, stmt, 0);
     184                 :            :     }
     185                 :            : 
     186                 :   89391000 :   gimple_set_plf (stmt, STMT_NECESSARY, true);
     187                 :   89391000 :   if (bb_contains_live_stmts)
     188                 :   33106800 :     bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
     189                 :   89391000 :   worklist.safe_push (stmt);
     190                 :            : }
     191                 :            : 
     192                 :            : 
     193                 :            : /* Mark STMT as necessary if it obviously is.  Add it to the worklist if
     194                 :            :    it can make other statements necessary.
     195                 :            : 
     196                 :            :    If AGGRESSIVE is false, control statements are conservatively marked as
     197                 :            :    necessary.  */
     198                 :            : 
     199                 :            : static void
     200                 :  352183000 : mark_stmt_if_obviously_necessary (gimple *stmt, bool aggressive)
     201                 :            : {
     202                 :            :   /* With non-call exceptions, we have to assume that all statements could
     203                 :            :      throw.  If a statement could throw, it can be deemed necessary.  */
     204                 :  352183000 :   if (cfun->can_throw_non_call_exceptions
     205                 :  352183000 :       && !cfun->can_delete_dead_exceptions
     206                 :  352183000 :       && stmt_could_throw_p (cfun, stmt))
     207                 :            :     {
     208                 :   12355400 :       mark_stmt_necessary (stmt, true);
     209                 :   12355400 :       return;
     210                 :            :     }
     211                 :            : 
     212                 :            :   /* Statements that are implicitly live.  Most function calls, asm
     213                 :            :      and return statements are required.  Labels and GIMPLE_BIND nodes
     214                 :            :      are kept because they are control flow, and we have no way of
     215                 :            :      knowing whether they can be removed.  DCE can eliminate all the
     216                 :            :      other statements in a block, and CFG can then remove the block
     217                 :            :      and labels.  */
     218                 :  339827000 :   switch (gimple_code (stmt))
     219                 :            :     {
     220                 :    3772560 :     case GIMPLE_PREDICT:
     221                 :    3772560 :     case GIMPLE_LABEL:
     222                 :    3772560 :       mark_stmt_necessary (stmt, false);
     223                 :    3772560 :       return;
     224                 :            : 
     225                 :    6288790 :     case GIMPLE_ASM:
     226                 :    6288790 :     case GIMPLE_RESX:
     227                 :    6288790 :     case GIMPLE_RETURN:
     228                 :    6288790 :       mark_stmt_necessary (stmt, true);
     229                 :    6288790 :       return;
     230                 :            : 
     231                 :   15759300 :     case GIMPLE_CALL:
     232                 :   15759300 :       {
     233                 :   15759300 :         tree callee = gimple_call_fndecl (stmt);
     234                 :   15759300 :         if (callee != NULL_TREE
     235                 :   15759300 :             && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
     236                 :    4696590 :           switch (DECL_FUNCTION_CODE (callee))
     237                 :            :             {
     238                 :            :             case BUILT_IN_MALLOC:
     239                 :            :             case BUILT_IN_ALIGNED_ALLOC:
     240                 :            :             case BUILT_IN_CALLOC:
     241                 :            :             CASE_BUILT_IN_ALLOCA:
     242                 :            :             case BUILT_IN_STRDUP:
     243                 :            :             case BUILT_IN_STRNDUP:
     244                 :            :               return;
     245                 :            : 
     246                 :            :             default:;
     247                 :            :             }
     248                 :            : 
     249                 :   15514800 :         if (callee != NULL_TREE
     250                 :   14411200 :             && flag_allocation_dce
     251                 :   29924700 :             && DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee))
     252                 :            :           return;
     253                 :            : 
     254                 :            :         /* Most, but not all function calls are required.  Function calls that
     255                 :            :            produce no result and have no side effects (i.e. const pure
     256                 :            :            functions) are unnecessary.  */
     257                 :   15381100 :         if (gimple_has_side_effects (stmt))
     258                 :            :           {
     259                 :   13309700 :             mark_stmt_necessary (stmt, true);
     260                 :   13309700 :             return;
     261                 :            :           }
     262                 :            :         /* IFN_GOACC_LOOP calls are necessary in that they are used to
     263                 :            :            represent parameter (i.e. step, bound) of a lowered OpenACC
     264                 :            :            partitioned loop.  But this kind of partitioned loop might not
     265                 :            :            survive from aggressive loop removal for it has loop exit and
     266                 :            :            is assumed to be finite.  Therefore, we need to explicitly mark
     267                 :            :            these calls. (An example is libgomp.oacc-c-c++-common/pr84955.c) */
     268                 :    2071420 :         if (gimple_call_internal_p (stmt, IFN_GOACC_LOOP))
     269                 :            :           {
     270                 :      22229 :             mark_stmt_necessary (stmt, true);
     271                 :      22229 :             return;
     272                 :            :           }
     273                 :    2049190 :         if (!gimple_call_lhs (stmt))
     274                 :            :           return;
     275                 :            :         break;
     276                 :            :       }
     277                 :            : 
     278                 :  198174000 :     case GIMPLE_DEBUG:
     279                 :            :       /* Debug temps without a value are not useful.  ??? If we could
     280                 :            :          easily locate the debug temp bind stmt for a use thereof,
     281                 :            :          would could refrain from marking all debug temps here, and
     282                 :            :          mark them only if they're used.  */
     283                 :  346677000 :       if (gimple_debug_nonbind_marker_p (stmt)
     284                 :  148503000 :           || !gimple_debug_bind_p (stmt)
     285                 :  148204000 :           || gimple_debug_bind_has_value_p (stmt)
     286                 :  267218000 :           || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
     287                 :  198026000 :         mark_stmt_necessary (stmt, false);
     288                 :            :       return;
     289                 :            : 
     290                 :       1726 :     case GIMPLE_GOTO:
     291                 :       1726 :       gcc_assert (!simple_goto_p (stmt));
     292                 :       1726 :       mark_stmt_necessary (stmt, true);
     293                 :       1726 :       return;
     294                 :            : 
     295                 :   17858900 :     case GIMPLE_COND:
     296                 :   17858900 :       gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
     297                 :            :       /* Fall through.  */
     298                 :            : 
     299                 :   17943900 :     case GIMPLE_SWITCH:
     300                 :   17943900 :       if (! aggressive)
     301                 :   11409200 :         mark_stmt_necessary (stmt, true);
     302                 :            :       break;
     303                 :            : 
     304                 :   97846500 :     case GIMPLE_ASSIGN:
     305                 :   97846500 :       if (gimple_clobber_p (stmt))
     306                 :            :         return;
     307                 :            :       break;
     308                 :            : 
     309                 :            :     default:
     310                 :            :       break;
     311                 :            :     }
     312                 :            : 
     313                 :            :   /* If the statement has volatile operands, it needs to be preserved.
     314                 :            :      Same for statements that can alter control flow in unpredictable
     315                 :            :      ways.  */
     316                 :  203625000 :   if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
     317                 :            :     {
     318                 :    3053100 :       mark_stmt_necessary (stmt, true);
     319                 :    3053100 :       return;
     320                 :            :     }
     321                 :            : 
     322                 :  107731000 :   if (stmt_may_clobber_global_p (stmt))
     323                 :            :     {
     324                 :    7990610 :       mark_stmt_necessary (stmt, true);
     325                 :    7990610 :       return;
     326                 :            :     }
     327                 :            : 
     328                 :  181529000 :   if (gimple_vdef (stmt) && keep_all_vdefs_p ())
     329                 :            :     {
     330                 :       2859 :       mark_stmt_necessary (stmt, true);
     331                 :       2859 :       return;
     332                 :            :     }
     333                 :            : 
     334                 :            :   return;
     335                 :            : }
     336                 :            : 
     337                 :            : 
     338                 :            : /* Mark the last statement of BB as necessary.  */
     339                 :            : 
     340                 :            : static void
     341                 :    8603660 : mark_last_stmt_necessary (basic_block bb)
     342                 :            : {
     343                 :    8603660 :   gimple *stmt = last_stmt (bb);
     344                 :            : 
     345                 :    8603660 :   bitmap_set_bit (last_stmt_necessary, bb->index);
     346                 :    8603660 :   bitmap_set_bit (bb_contains_live_stmts, bb->index);
     347                 :            : 
     348                 :            :   /* We actually mark the statement only if it is a control statement.  */
     349                 :    8603660 :   if (stmt && is_ctrl_stmt (stmt))
     350                 :    6508190 :     mark_stmt_necessary (stmt, true);
     351                 :    8603660 : }
     352                 :            : 
     353                 :            : 
     354                 :            : /* Mark control dependent edges of BB as necessary.  We have to do this only
     355                 :            :    once for each basic block so we set the appropriate bit after we're done.
     356                 :            : 
     357                 :            :    When IGNORE_SELF is true, ignore BB in the list of control dependences.  */
     358                 :            : 
     359                 :            : static void
     360                 :   17755700 : mark_control_dependent_edges_necessary (basic_block bb, bool ignore_self)
     361                 :            : {
     362                 :   17755700 :   bitmap_iterator bi;
     363                 :   17755700 :   unsigned edge_number;
     364                 :   17755700 :   bool skipped = false;
     365                 :            : 
     366                 :   17755700 :   gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
     367                 :            : 
     368                 :   17755700 :   if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     369                 :          0 :     return;
     370                 :            : 
     371                 :   39839600 :   EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
     372                 :            :                             0, edge_number, bi)
     373                 :            :     {
     374                 :   22083900 :       basic_block cd_bb = cd->get_edge_src (edge_number);
     375                 :            : 
     376                 :   22083900 :       if (ignore_self && cd_bb == bb)
     377                 :            :         {
     378                 :      32674 :           skipped = true;
     379                 :      32674 :           continue;
     380                 :            :         }
     381                 :            : 
     382                 :   22051200 :       if (!bitmap_bit_p (last_stmt_necessary, cd_bb->index))
     383                 :    8601620 :         mark_last_stmt_necessary (cd_bb);
     384                 :            :     }
     385                 :            : 
     386                 :   17755700 :   if (!skipped)
     387                 :   35478800 :     bitmap_set_bit (visited_control_parents, bb->index);
     388                 :            : }
     389                 :            : 
     390                 :            : 
     391                 :            : /* Find obviously necessary statements.  These are things like most function
     392                 :            :    calls, and stores to file level variables.
     393                 :            : 
     394                 :            :    If EL is NULL, control statements are conservatively marked as
     395                 :            :    necessary.  Otherwise it contains the list of edges used by control
     396                 :            :    dependence analysis.  */
     397                 :            : 
     398                 :            : static void
     399                 :    5204660 : find_obviously_necessary_stmts (bool aggressive)
     400                 :            : {
     401                 :    5204660 :   basic_block bb;
     402                 :    5204660 :   gimple_stmt_iterator gsi;
     403                 :    5204660 :   edge e;
     404                 :    5204660 :   gimple *phi, *stmt;
     405                 :    5204660 :   int flags;
     406                 :            : 
     407                 :   53776800 :   FOR_EACH_BB_FN (bb, cfun)
     408                 :            :     {
     409                 :            :       /* PHI nodes are never inherently necessary.  */
     410                 :   67555200 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     411                 :            :         {
     412                 :   18983100 :           phi = gsi_stmt (gsi);
     413                 :   18983100 :           gimple_set_plf (phi, STMT_NECESSARY, false);
     414                 :            :         }
     415                 :            : 
     416                 :            :       /* Check all statements in the block.  */
     417                 :  449327000 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     418                 :            :         {
     419                 :  352183000 :           stmt = gsi_stmt (gsi);
     420                 :  352183000 :           gimple_set_plf (stmt, STMT_NECESSARY, false);
     421                 :  352183000 :           mark_stmt_if_obviously_necessary (stmt, aggressive);
     422                 :            :         }
     423                 :            :     }
     424                 :            : 
     425                 :            :   /* Pure and const functions are finite and thus have no infinite loops in
     426                 :            :      them.  */
     427                 :    5204660 :   flags = flags_from_decl_or_type (current_function_decl);
     428                 :    5204660 :   if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
     429                 :     607313 :     return;
     430                 :            : 
     431                 :            :   /* Prevent the empty possibly infinite loops from being removed.  */
     432                 :    4597350 :   if (aggressive)
     433                 :            :     {
     434                 :    2197510 :       class loop *loop;
     435                 :    2197510 :       if (mark_irreducible_loops ())
     436                 :      79488 :         FOR_EACH_BB_FN (bb, cfun)
     437                 :            :           {
     438                 :      76860 :             edge_iterator ei;
     439                 :     193748 :             FOR_EACH_EDGE (e, ei, bb->succs)
     440                 :     116888 :               if ((e->flags & EDGE_DFS_BACK)
     441                 :     116888 :                   && (e->flags & EDGE_IRREDUCIBLE_LOOP))
     442                 :            :                 {
     443                 :       5804 :                   if (dump_file)
     444                 :          0 :                     fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
     445                 :          0 :                              e->src->index, e->dest->index);
     446                 :       5804 :                   mark_control_dependent_edges_necessary (e->dest, false);
     447                 :            :                 }
     448                 :            :           }
     449                 :            : 
     450                 :    5425620 :       FOR_EACH_LOOP (loop, 0)
     451                 :    1030600 :         if (!finite_loop_p (loop))
     452                 :            :           {
     453                 :      12159 :             if (dump_file)
     454                 :          4 :               fprintf (dump_file, "cannot prove finiteness of loop %i\n", loop->num);
     455                 :      12159 :             mark_control_dependent_edges_necessary (loop->latch, false);
     456                 :            :           }
     457                 :            :     }
     458                 :            : }
     459                 :            : 
     460                 :            : 
     461                 :            : /* Return true if REF is based on an aliased base, otherwise false.  */
     462                 :            : 
     463                 :            : static bool
     464                 :   63240800 : ref_may_be_aliased (tree ref)
     465                 :            : {
     466                 :   63240800 :   gcc_assert (TREE_CODE (ref) != WITH_SIZE_EXPR);
     467                 :  116416000 :   while (handled_component_p (ref))
     468                 :   53175400 :     ref = TREE_OPERAND (ref, 0);
     469                 :   63240800 :   if (TREE_CODE (ref) == MEM_REF
     470                 :   63240800 :       && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR)
     471                 :    8944300 :     ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
     472                 :  107139000 :   return !(DECL_P (ref)
     473                 :   43898500 :            && !may_be_aliased (ref));
     474                 :            : }
     475                 :            : 
     476                 :            : static bitmap visited = NULL;
     477                 :            : static unsigned int longest_chain = 0;
     478                 :            : static unsigned int total_chain = 0;
     479                 :            : static unsigned int nr_walks = 0;
     480                 :            : static bool chain_ovfl = false;
     481                 :            : 
     482                 :            : /* Worker for the walker that marks reaching definitions of REF,
     483                 :            :    which is based on a non-aliased decl, necessary.  It returns
     484                 :            :    true whenever the defining statement of the current VDEF is
     485                 :            :    a kill for REF, as no dominating may-defs are necessary for REF
     486                 :            :    anymore.  DATA points to the basic-block that contains the
     487                 :            :    stmt that refers to REF.  */
     488                 :            : 
     489                 :            : static bool
     490                 :   26453700 : mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
     491                 :            : {
     492                 :   26453700 :   gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
     493                 :            : 
     494                 :            :   /* All stmts we visit are necessary.  */
     495                 :   26453700 :   if (! gimple_clobber_p (def_stmt))
     496                 :   26325300 :     mark_operand_necessary (vdef);
     497                 :            : 
     498                 :            :   /* If the stmt lhs kills ref, then we can stop walking.  */
     499                 :   26453700 :   if (gimple_has_lhs (def_stmt)
     500                 :   20073400 :       && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME
     501                 :            :       /* The assignment is not necessarily carried out if it can throw
     502                 :            :          and we can catch it in the current function where we could inspect
     503                 :            :          the previous value.
     504                 :            :          ???  We only need to care about the RHS throwing.  For aggregate
     505                 :            :          assignments or similar calls and non-call exceptions the LHS
     506                 :            :          might throw as well.  */
     507                 :   25636400 :       && !stmt_can_throw_internal (cfun, def_stmt))
     508                 :            :     {
     509                 :   17818100 :       tree base, lhs = gimple_get_lhs (def_stmt);
     510                 :   17818100 :       poly_int64 size, offset, max_size;
     511                 :   17818100 :       bool reverse;
     512                 :   17818100 :       ao_ref_base (ref);
     513                 :   17818100 :       base
     514                 :   17818100 :         = get_ref_base_and_extent (lhs, &offset, &size, &max_size, &reverse);
     515                 :            :       /* We can get MEM[symbol: sZ, index: D.8862_1] here,
     516                 :            :          so base == refd->base does not always hold.  */
     517                 :   17818100 :       if (base == ref->base)
     518                 :            :         {
     519                 :            :           /* For a must-alias check we need to be able to constrain
     520                 :            :              the accesses properly.  */
     521                 :   16033400 :           if (known_eq (size, max_size)
     522                 :   16033400 :               && known_subrange_p (ref->offset, ref->max_size, offset, size))
     523                 :    6335230 :             return true;
     524                 :            :           /* Or they need to be exactly the same.  */
     525                 :    9698870 :           else if (ref->ref
     526                 :            :                    /* Make sure there is no induction variable involved
     527                 :            :                       in the references (gcc.c-torture/execute/pr42142.c).
     528                 :            :                       The simplest way is to check if the kill dominates
     529                 :            :                       the use.  */
     530                 :            :                    /* But when both are in the same block we cannot
     531                 :            :                       easily tell whether we came from a backedge
     532                 :            :                       unless we decide to compute stmt UIDs
     533                 :            :                       (see PR58246).  */
     534                 :    9698870 :                    && (basic_block) data != gimple_bb (def_stmt)
     535                 :    4312730 :                    && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
     536                 :    4312730 :                                       gimple_bb (def_stmt))
     537                 :   11707700 :                    && operand_equal_p (ref->ref, lhs, 0))
     538                 :            :             return true;
     539                 :            :         }
     540                 :            :     }
     541                 :            : 
     542                 :            :   /* Otherwise keep walking.  */
     543                 :            :   return false;
     544                 :            : }
     545                 :            : 
     546                 :            : static void
     547                 :    9398510 : mark_aliased_reaching_defs_necessary (gimple *stmt, tree ref)
     548                 :            : {
     549                 :            :   /* Should have been caught before calling this function.  */
     550                 :    9398510 :   gcc_checking_assert (!keep_all_vdefs_p ());
     551                 :            : 
     552                 :    9398510 :   unsigned int chain;
     553                 :    9398510 :   ao_ref refd;
     554                 :    9398510 :   gcc_assert (!chain_ovfl);
     555                 :    9398510 :   ao_ref_init (&refd, ref);
     556                 :    9398510 :   chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
     557                 :            :                               mark_aliased_reaching_defs_necessary_1,
     558                 :    9398510 :                               gimple_bb (stmt), NULL);
     559                 :    9398510 :   if (chain > longest_chain)
     560                 :    1359360 :     longest_chain = chain;
     561                 :    9398510 :   total_chain += chain;
     562                 :    9398510 :   nr_walks++;
     563                 :    9398510 : }
     564                 :            : 
     565                 :            : /* Worker for the walker that marks reaching definitions of REF, which
     566                 :            :    is not based on a non-aliased decl.  For simplicity we need to end
     567                 :            :    up marking all may-defs necessary that are not based on a non-aliased
     568                 :            :    decl.  The only job of this walker is to skip may-defs based on
     569                 :            :    a non-aliased decl.  */
     570                 :            : 
     571                 :            : static bool
     572                 :   50362900 : mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
     573                 :            :                                     tree vdef, void *data ATTRIBUTE_UNUSED)
     574                 :            : {
     575                 :   50362900 :   gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
     576                 :            : 
     577                 :            :   /* We have to skip already visited (and thus necessary) statements
     578                 :            :      to make the chaining work after we dropped back to simple mode.  */
     579                 :   50362900 :   if (chain_ovfl
     580                 :   50362900 :       && bitmap_bit_p (processed, SSA_NAME_VERSION (vdef)))
     581                 :            :     {
     582                 :    1520600 :       gcc_assert (gimple_nop_p (def_stmt)
     583                 :            :                   || gimple_plf (def_stmt, STMT_NECESSARY));
     584                 :            :       return false;
     585                 :            :     }
     586                 :            : 
     587                 :            :   /* We want to skip stores to non-aliased variables.  */
     588                 :   48842300 :   if (!chain_ovfl
     589                 :   48842300 :       && gimple_assign_single_p (def_stmt))
     590                 :            :     {
     591                 :   33046400 :       tree lhs = gimple_assign_lhs (def_stmt);
     592                 :   33046400 :       if (!ref_may_be_aliased (lhs))
     593                 :            :         return false;
     594                 :            :     }
     595                 :            : 
     596                 :            :   /* We want to skip statments that do not constitute stores but have
     597                 :            :      a virtual definition.  */
     598                 :   39785500 :   if (is_gimple_call (def_stmt))
     599                 :            :     {
     600                 :   15263200 :       tree callee = gimple_call_fndecl (def_stmt);
     601                 :   15263200 :       if (callee != NULL_TREE
     602                 :   15263200 :           && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
     603                 :    2528830 :         switch (DECL_FUNCTION_CODE (callee))
     604                 :            :           {
     605                 :            :           case BUILT_IN_MALLOC:
     606                 :            :           case BUILT_IN_ALIGNED_ALLOC:
     607                 :            :           case BUILT_IN_CALLOC:
     608                 :            :           CASE_BUILT_IN_ALLOCA:
     609                 :            :           case BUILT_IN_FREE:
     610                 :            :             return false;
     611                 :            : 
     612                 :            :           default:;
     613                 :            :           }
     614                 :            : 
     615                 :   14901500 :       if (callee != NULL_TREE
     616                 :   29026700 :           && (DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee)
     617                 :   14007000 :               || DECL_IS_OPERATOR_DELETE_P (callee)))
     618                 :            :         return false;
     619                 :            :     }
     620                 :            : 
     621                 :   38977500 :   if (! gimple_clobber_p (def_stmt))
     622                 :   35534500 :     mark_operand_necessary (vdef);
     623                 :            : 
     624                 :            :   return false;
     625                 :            : }
     626                 :            : 
     627                 :            : static void
     628                 :   43095500 : mark_all_reaching_defs_necessary (gimple *stmt)
     629                 :            : {
     630                 :            :   /* Should have been caught before calling this function.  */
     631                 :   43095500 :   gcc_checking_assert (!keep_all_vdefs_p ());
     632                 :   86190900 :   walk_aliased_vdefs (NULL, gimple_vuse (stmt),
     633                 :            :                       mark_all_reaching_defs_necessary_1, NULL, &visited);
     634                 :   43095500 : }
     635                 :            : 
     636                 :            : /* Return true for PHI nodes with one or identical arguments
     637                 :            :    can be removed.  */
     638                 :            : static bool
     639                 :   12991500 : degenerate_phi_p (gimple *phi)
     640                 :            : {
     641                 :   12991500 :   unsigned int i;
     642                 :   12991500 :   tree op = gimple_phi_arg_def (phi, 0);
     643                 :   13470800 :   for (i = 1; i < gimple_phi_num_args (phi); i++)
     644                 :   12545500 :     if (gimple_phi_arg_def (phi, i) != op)
     645                 :            :       return false;
     646                 :            :   return true;
     647                 :            : }
     648                 :            : 
     649                 :            : /* Propagate necessity using the operands of necessary statements.
     650                 :            :    Process the uses on each statement in the worklist, and add all
     651                 :            :    feeding statements which contribute to the calculation of this
     652                 :            :    value to the worklist.
     653                 :            : 
     654                 :            :    In conservative mode, EL is NULL.  */
     655                 :            : 
     656                 :            : static void
     657                 :    5204660 : propagate_necessity (bool aggressive)
     658                 :            : {
     659                 :    5204660 :   gimple *stmt;
     660                 :            : 
     661                 :    5204660 :   if (dump_file && (dump_flags & TDF_DETAILS))
     662                 :         99 :     fprintf (dump_file, "\nProcessing worklist:\n");
     663                 :            : 
     664                 :  155537000 :   while (worklist.length () > 0)
     665                 :            :     {
     666                 :            :       /* Take STMT from worklist.  */
     667                 :  150333000 :       stmt = worklist.pop ();
     668                 :            : 
     669                 :  150333000 :       if (dump_file && (dump_flags & TDF_DETAILS))
     670                 :            :         {
     671                 :        261 :           fprintf (dump_file, "processing: ");
     672                 :        261 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
     673                 :        261 :           fprintf (dump_file, "\n");
     674                 :            :         }
     675                 :            : 
     676                 :  150333000 :       if (aggressive)
     677                 :            :         {
     678                 :            :           /* Mark the last statement of the basic blocks on which the block
     679                 :            :              containing STMT is control dependent, but only if we haven't
     680                 :            :              already done so.  */
     681                 :   55549600 :           basic_block bb = gimple_bb (stmt);
     682                 :   55549600 :           if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     683                 :   55549600 :               && !bitmap_bit_p (visited_control_parents, bb->index))
     684                 :   13892200 :             mark_control_dependent_edges_necessary (bb, false);
     685                 :            :         }
     686                 :            : 
     687                 :  150333000 :       if (gimple_code (stmt) == GIMPLE_PHI
     688                 :            :           /* We do not process virtual PHI nodes nor do we track their
     689                 :            :              necessity.  */
     690                 :  191030000 :           && !virtual_operand_p (gimple_phi_result (stmt)))
     691                 :            :         {
     692                 :            :           /* PHI nodes are somewhat special in that each PHI alternative has
     693                 :            :              data and control dependencies.  All the statements feeding the
     694                 :            :              PHI node's arguments are always necessary.  In aggressive mode,
     695                 :            :              we also consider the control dependent edges leading to the
     696                 :            :              predecessor block associated with each PHI alternative as
     697                 :            :              necessary.  */
     698                 :   31071700 :           gphi *phi = as_a <gphi *> (stmt);
     699                 :            :           size_t k;
     700                 :            : 
     701                 :   31071700 :           for (k = 0; k < gimple_phi_num_args (stmt); k++)
     702                 :            :             {
     703                 :   21446700 :               tree arg = PHI_ARG_DEF (stmt, k);
     704                 :   21446700 :               if (TREE_CODE (arg) == SSA_NAME)
     705                 :   15923100 :                 mark_operand_necessary (arg);
     706                 :            :             }
     707                 :            : 
     708                 :            :           /* For PHI operands it matters from where the control flow arrives
     709                 :            :              to the BB.  Consider the following example:
     710                 :            : 
     711                 :            :              a=exp1;
     712                 :            :              b=exp2;
     713                 :            :              if (test)
     714                 :            :                 ;
     715                 :            :              else
     716                 :            :                 ;
     717                 :            :              c=PHI(a,b)
     718                 :            : 
     719                 :            :              We need to mark control dependence of the empty basic blocks, since they
     720                 :            :              contains computation of PHI operands.
     721                 :            : 
     722                 :            :              Doing so is too restrictive in the case the predecestor block is in
     723                 :            :              the loop. Consider:
     724                 :            : 
     725                 :            :               if (b)
     726                 :            :                 {
     727                 :            :                   int i;
     728                 :            :                   for (i = 0; i<1000; ++i)
     729                 :            :                     ;
     730                 :            :                   j = 0;
     731                 :            :                 }
     732                 :            :               return j;
     733                 :            : 
     734                 :            :              There is PHI for J in the BB containing return statement.
     735                 :            :              In this case the control dependence of predecestor block (that is
     736                 :            :              within the empty loop) also contains the block determining number
     737                 :            :              of iterations of the block that would prevent removing of empty
     738                 :            :              loop in this case.
     739                 :            : 
     740                 :            :              This scenario can be avoided by splitting critical edges.
     741                 :            :              To save the critical edge splitting pass we identify how the control
     742                 :            :              dependence would look like if the edge was split.
     743                 :            : 
     744                 :            :              Consider the modified CFG created from current CFG by splitting
     745                 :            :              edge B->C.  In the postdominance tree of modified CFG, C' is
     746                 :            :              always child of C.  There are two cases how chlids of C' can look
     747                 :            :              like:
     748                 :            : 
     749                 :            :                 1) C' is leaf
     750                 :            : 
     751                 :            :                    In this case the only basic block C' is control dependent on is B.
     752                 :            : 
     753                 :            :                 2) C' has single child that is B
     754                 :            : 
     755                 :            :                    In this case control dependence of C' is same as control
     756                 :            :                    dependence of B in original CFG except for block B itself.
     757                 :            :                    (since C' postdominate B in modified CFG)
     758                 :            : 
     759                 :            :              Now how to decide what case happens?  There are two basic options:
     760                 :            : 
     761                 :            :                 a) C postdominate B.  Then C immediately postdominate B and
     762                 :            :                    case 2 happens iff there is no other way from B to C except
     763                 :            :                    the edge B->C.
     764                 :            : 
     765                 :            :                    There is other way from B to C iff there is succesor of B that
     766                 :            :                    is not postdominated by B.  Testing this condition is somewhat
     767                 :            :                    expensive, because we need to iterate all succesors of B.
     768                 :            :                    We are safe to assume that this does not happen: we will mark B
     769                 :            :                    as needed when processing the other path from B to C that is
     770                 :            :                    conrol dependent on B and marking control dependencies of B
     771                 :            :                    itself is harmless because they will be processed anyway after
     772                 :            :                    processing control statement in B.
     773                 :            : 
     774                 :            :                 b) C does not postdominate B.  Always case 1 happens since there is
     775                 :            :                    path from C to exit that does not go through B and thus also C'.  */
     776                 :            : 
     777                 :    9625040 :           if (aggressive && !degenerate_phi_p (stmt))
     778                 :            :             {
     779                 :   11380200 :               for (k = 0; k < gimple_phi_num_args (stmt); k++)
     780                 :            :                 {
     781                 :    7978490 :                   basic_block arg_bb = gimple_phi_arg_edge (phi, k)->src;
     782                 :            : 
     783                 :    7978490 :                   if (gimple_bb (stmt)
     784                 :    7978490 :                       != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
     785                 :            :                     {
     786                 :     875863 :                       if (!bitmap_bit_p (last_stmt_necessary, arg_bb->index))
     787                 :       2041 :                         mark_last_stmt_necessary (arg_bb);
     788                 :            :                     }
     789                 :    7102620 :                   else if (arg_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     790                 :    7102620 :                            && !bitmap_bit_p (visited_control_parents,
     791                 :            :                                          arg_bb->index))
     792                 :    3845520 :                     mark_control_dependent_edges_necessary (arg_bb, true);
     793                 :            :                 }
     794                 :            :             }
     795                 :            :         }
     796                 :            :       else
     797                 :            :         {
     798                 :            :           /* Propagate through the operands.  Examine all the USE, VUSE and
     799                 :            :              VDEF operands in this statement.  Mark all the statements
     800                 :            :              which feed this statement's uses as necessary.  */
     801                 :  140708000 :           ssa_op_iter iter;
     802                 :  140708000 :           tree use;
     803                 :            : 
     804                 :            :           /* If this is a call to free which is directly fed by an
     805                 :            :              allocation function do not mark that necessary through
     806                 :            :              processing the argument.  */
     807                 :  140708000 :           bool is_delete_operator
     808                 :  140708000 :             = (is_gimple_call (stmt)
     809                 :  140708000 :                && gimple_call_operator_delete_p (as_a <gcall *> (stmt)));
     810                 :  140218000 :           if (is_delete_operator
     811                 :  140218000 :               || gimple_call_builtin_p (stmt, BUILT_IN_FREE))
     812                 :            :             {
     813                 :     670487 :               tree ptr = gimple_call_arg (stmt, 0);
     814                 :     670487 :               gimple *def_stmt;
     815                 :     670487 :               tree def_callee;
     816                 :            :               /* If the pointer we free is defined by an allocation
     817                 :            :                  function do not add the call to the worklist.  */
     818                 :     670487 :               if (TREE_CODE (ptr) == SSA_NAME
     819                 :     670142 :                   && is_gimple_call (def_stmt = SSA_NAME_DEF_STMT (ptr))
     820                 :     118437 :                   && (def_callee = gimple_call_fndecl (def_stmt))
     821                 :     788821 :                   && ((DECL_BUILT_IN_CLASS (def_callee) == BUILT_IN_NORMAL
     822                 :      76946 :                        && (DECL_FUNCTION_CODE (def_callee) == BUILT_IN_ALIGNED_ALLOC
     823                 :      76940 :                            || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_MALLOC
     824                 :       4159 :                            || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_CALLOC))
     825                 :      44801 :                       || DECL_IS_REPLACEABLE_OPERATOR_NEW_P (def_callee)))
     826                 :            :                 {
     827                 :            :                   /* Delete operators can have alignment and (or) size as next
     828                 :            :                      arguments.  When being a SSA_NAME, they must be marked
     829                 :            :                      as necessary.  */
     830                 :     102822 :                   if (is_delete_operator && gimple_call_num_args (stmt) >= 2)
     831                 :      48055 :                     for (unsigned i = 1; i < gimple_call_num_args (stmt); i++)
     832                 :            :                       {
     833                 :      24040 :                         tree arg = gimple_call_arg (stmt, i);
     834                 :      24040 :                         if (TREE_CODE (arg) == SSA_NAME)
     835                 :       1826 :                           mark_operand_necessary (arg);
     836                 :            :                       }
     837                 :            : 
     838                 :   59488300 :                   continue;
     839                 :            :                 }
     840                 :            :             }
     841                 :            : 
     842                 :  262973000 :           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
     843                 :  122368000 :             mark_operand_necessary (use);
     844                 :            : 
     845                 :  140605000 :           use = gimple_vuse (stmt);
     846                 :  121725000 :           if (!use)
     847                 :   55977900 :             continue;
     848                 :            : 
     849                 :            :           /* No need to search for vdefs if we intrinsicly keep them all.  */
     850                 :   84627000 :           if (keep_all_vdefs_p ())
     851                 :      43872 :             continue;
     852                 :            : 
     853                 :            :           /* If we dropped to simple mode make all immediately
     854                 :            :              reachable definitions necessary.  */
     855                 :   84583200 :           if (chain_ovfl)
     856                 :            :             {
     857                 :    2270510 :               mark_all_reaching_defs_necessary (stmt);
     858                 :    2270510 :               continue;
     859                 :            :             }
     860                 :            : 
     861                 :            :           /* For statements that may load from memory (have a VUSE) we
     862                 :            :              have to mark all reaching (may-)definitions as necessary.
     863                 :            :              We partition this task into two cases:
     864                 :            :               1) explicit loads based on decls that are not aliased
     865                 :            :               2) implicit loads (like calls) and explicit loads not
     866                 :            :                  based on decls that are not aliased (like indirect
     867                 :            :                  references or loads from globals)
     868                 :            :              For 1) we mark all reaching may-defs as necessary, stopping
     869                 :            :              at dominating kills.  For 2) we want to mark all dominating
     870                 :            :              references necessary, but non-aliased ones which we handle
     871                 :            :              in 1).  By keeping a global visited bitmap for references
     872                 :            :              we walk for 2) we avoid quadratic behavior for those.  */
     873                 :            : 
     874                 :   82312700 :           if (is_gimple_call (stmt))
     875                 :            :             {
     876                 :   21296500 :               tree callee = gimple_call_fndecl (stmt);
     877                 :   21296500 :               unsigned i;
     878                 :            : 
     879                 :            :               /* Calls to functions that are merely acting as barriers
     880                 :            :                  or that only store to memory do not make any previous
     881                 :            :                  stores necessary.  */
     882                 :   21796000 :               if (callee != NULL_TREE
     883                 :   20291500 :                   && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
     884                 :   25504900 :                   && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET
     885                 :    4095300 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET_CHK
     886                 :    4092850 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC
     887                 :    3904800 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALIGNED_ALLOC
     888                 :    3904660 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC
     889                 :    3902110 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE
     890                 :    3794940 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_VA_END
     891                 :    3780900 :                       || ALLOCA_FUNCTION_CODE_P (DECL_FUNCTION_CODE (callee))
     892                 :    3731490 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE
     893                 :    3720260 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE
     894                 :    3708940 :                       || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED))
     895                 :     499438 :                 continue;
     896                 :            : 
     897                 :   21390800 :               if (callee != NULL_TREE
     898                 :   40589100 :                   && (DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee)
     899                 :   19658400 :                       || DECL_IS_OPERATOR_DELETE_P (callee)))
     900                 :     593720 :                 continue;
     901                 :            : 
     902                 :            :               /* Calls implicitly load from memory, their arguments
     903                 :            :                  in addition may explicitly perform memory loads.  */
     904                 :   20203400 :               mark_all_reaching_defs_necessary (stmt);
     905                 :   58798700 :               for (i = 0; i < gimple_call_num_args (stmt); ++i)
     906                 :            :                 {
     907                 :   38595300 :                   tree arg = gimple_call_arg (stmt, i);
     908                 :   74392400 :                   if (TREE_CODE (arg) == SSA_NAME
     909                 :   38595300 :                       || is_gimple_min_invariant (arg))
     910                 :   35797100 :                     continue;
     911                 :    2798220 :                   if (TREE_CODE (arg) == WITH_SIZE_EXPR)
     912                 :        683 :                     arg = TREE_OPERAND (arg, 0);
     913                 :    2798220 :                   if (!ref_may_be_aliased (arg))
     914                 :    2521870 :                     mark_aliased_reaching_defs_necessary (stmt, arg);
     915                 :            :                 }
     916                 :            :             }
     917                 :   61016100 :           else if (gimple_assign_single_p (stmt))
     918                 :            :             {
     919                 :   55818400 :               tree rhs;
     920                 :            :               /* If this is a load mark things necessary.  */
     921                 :   55818400 :               rhs = gimple_assign_rhs1 (stmt);
     922                 :   55818400 :               if (TREE_CODE (rhs) != SSA_NAME
     923                 :   43801800 :                   && !is_gimple_min_invariant (rhs)
     924                 :   83206000 :                   && TREE_CODE (rhs) != CONSTRUCTOR)
     925                 :            :                 {
     926                 :   26962800 :                   if (!ref_may_be_aliased (rhs))
     927                 :    6459080 :                     mark_aliased_reaching_defs_necessary (stmt, rhs);
     928                 :            :                   else
     929                 :   20503700 :                     mark_all_reaching_defs_necessary (stmt);
     930                 :            :                 }
     931                 :            :             }
     932                 :    5197770 :           else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
     933                 :            :             {
     934                 :    5087350 :               tree rhs = gimple_return_retval (return_stmt);
     935                 :            :               /* A return statement may perform a load.  */
     936                 :    5087350 :               if (rhs
     937                 :    2745340 :                   && TREE_CODE (rhs) != SSA_NAME
     938                 :     967485 :                   && !is_gimple_min_invariant (rhs)
     939                 :    5508080 :                   && TREE_CODE (rhs) != CONSTRUCTOR)
     940                 :            :                 {
     941                 :     420731 :                   if (!ref_may_be_aliased (rhs))
     942                 :     413300 :                     mark_aliased_reaching_defs_necessary (stmt, rhs);
     943                 :            :                   else
     944                 :       7431 :                     mark_all_reaching_defs_necessary (stmt);
     945                 :            :                 }
     946                 :            :             }
     947                 :     110420 :           else if (gasm *asm_stmt = dyn_cast <gasm *> (stmt))
     948                 :            :             {
     949                 :     109122 :               unsigned i;
     950                 :     109122 :               mark_all_reaching_defs_necessary (stmt);
     951                 :            :               /* Inputs may perform loads.  */
     952                 :     189092 :               for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
     953                 :            :                 {
     954                 :      79970 :                   tree op = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
     955                 :      79970 :                   if (TREE_CODE (op) != SSA_NAME
     956                 :      45588 :                       && !is_gimple_min_invariant (op)
     957                 :      12637 :                       && TREE_CODE (op) != CONSTRUCTOR
     958                 :      92607 :                       && !ref_may_be_aliased (op))
     959                 :       4266 :                     mark_aliased_reaching_defs_necessary (stmt, op);
     960                 :            :                 }
     961                 :            :             }
     962                 :       1298 :           else if (gimple_code (stmt) == GIMPLE_TRANSACTION)
     963                 :            :             {
     964                 :            :               /* The beginning of a transaction is a memory barrier.  */
     965                 :            :               /* ??? If we were really cool, we'd only be a barrier
     966                 :            :                  for the memories touched within the transaction.  */
     967                 :       1298 :               mark_all_reaching_defs_necessary (stmt);
     968                 :            :             }
     969                 :            :           else
     970                 :          0 :             gcc_unreachable ();
     971                 :            : 
     972                 :            :           /* If we over-used our alias oracle budget drop to simple
     973                 :            :              mode.  The cost metric allows quadratic behavior
     974                 :            :              (number of uses times number of may-defs queries) up to
     975                 :            :              a constant maximal number of queries and after that falls back to
     976                 :            :              super-linear complexity.  */
     977                 :   81219500 :           if (/* Constant but quadratic for small functions.  */
     978                 :   81219500 :               total_chain > 128 * 128
     979                 :            :               /* Linear in the number of may-defs.  */
     980                 :     667974 :               && total_chain > 32 * longest_chain
     981                 :            :               /* Linear in the number of uses.  */
     982                 :       2546 :               && total_chain > nr_walks * 32)
     983                 :            :             {
     984                 :       2546 :               chain_ovfl = true;
     985                 :       2546 :               if (visited)
     986                 :       2546 :                 bitmap_clear (visited);
     987                 :            :             }
     988                 :            :         }
     989                 :            :     }
     990                 :    5204660 : }
     991                 :            : 
     992                 :            : /* Remove dead PHI nodes from block BB.  */
     993                 :            : 
     994                 :            : static bool
     995                 :   48572100 : remove_dead_phis (basic_block bb)
     996                 :            : {
     997                 :   48572100 :   bool something_changed = false;
     998                 :   48572100 :   gphi *phi;
     999                 :   48572100 :   gphi_iterator gsi;
    1000                 :            : 
    1001                 :   67555200 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
    1002                 :            :     {
    1003                 :   18983100 :       stats.total_phis++;
    1004                 :   18983100 :       phi = gsi.phi ();
    1005                 :            : 
    1006                 :            :       /* We do not track necessity of virtual PHI nodes.  Instead do
    1007                 :            :          very simple dead PHI removal here.  */
    1008                 :   37966200 :       if (virtual_operand_p (gimple_phi_result (phi)))
    1009                 :            :         {
    1010                 :            :           /* Virtual PHI nodes with one or identical arguments
    1011                 :            :              can be removed.  */
    1012                 :    9081360 :           if (degenerate_phi_p (phi))
    1013                 :            :             {
    1014                 :     416874 :               tree vdef = gimple_phi_result (phi);
    1015                 :     416874 :               tree vuse = gimple_phi_arg_def (phi, 0);
    1016                 :            : 
    1017                 :     416874 :               use_operand_p use_p;
    1018                 :     416874 :               imm_use_iterator iter;
    1019                 :     416874 :               gimple *use_stmt;
    1020                 :    1096320 :               FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
    1021                 :    2069630 :                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    1022                 :     695092 :                   SET_USE (use_p, vuse);
    1023                 :     416874 :               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
    1024                 :     416874 :                   && TREE_CODE (vuse) == SSA_NAME)
    1025                 :        155 :                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
    1026                 :            :             }
    1027                 :            :           else
    1028                 :    8664480 :             gimple_set_plf (phi, STMT_NECESSARY, true);
    1029                 :            :         }
    1030                 :            : 
    1031                 :   18983100 :       if (!gimple_plf (phi, STMT_NECESSARY))
    1032                 :            :         {
    1033                 :     693603 :           something_changed = true;
    1034                 :     693603 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1035                 :            :             {
    1036                 :          5 :               fprintf (dump_file, "Deleting : ");
    1037                 :          5 :               print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
    1038                 :          5 :               fprintf (dump_file, "\n");
    1039                 :            :             }
    1040                 :            : 
    1041                 :     693603 :           remove_phi_node (&gsi, true);
    1042                 :     693603 :           stats.removed_phis++;
    1043                 :     693603 :           continue;
    1044                 :            :         }
    1045                 :            : 
    1046                 :   18289500 :       gsi_next (&gsi);
    1047                 :            :     }
    1048                 :   48572100 :   return something_changed;
    1049                 :            : }
    1050                 :            : 
    1051                 :            : 
    1052                 :            : /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
    1053                 :            :    containing I so that we don't have to look it up.  */
    1054                 :            : 
    1055                 :            : static void
    1056                 :    4421600 : remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb,
    1057                 :            :                   vec<edge> &to_remove_edges)
    1058                 :            : {
    1059                 :    4421600 :   gimple *stmt = gsi_stmt (*i);
    1060                 :            : 
    1061                 :    4421600 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1062                 :            :     {
    1063                 :         96 :       fprintf (dump_file, "Deleting : ");
    1064                 :         96 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1065                 :         96 :       fprintf (dump_file, "\n");
    1066                 :            :     }
    1067                 :            : 
    1068                 :    4421600 :   stats.removed++;
    1069                 :            : 
    1070                 :            :   /* If we have determined that a conditional branch statement contributes
    1071                 :            :      nothing to the program, then we not only remove it, but we need to update
    1072                 :            :      the CFG.  We can chose any of edges out of BB as long as we are sure to not
    1073                 :            :      close infinite loops.  This is done by always choosing the edge closer to
    1074                 :            :      exit in inverted_post_order_compute order.  */
    1075                 :    4421600 :   if (is_ctrl_stmt (stmt))
    1076                 :            :     {
    1077                 :      26571 :       edge_iterator ei;
    1078                 :      26571 :       edge e = NULL, e2;
    1079                 :            : 
    1080                 :            :       /* See if there is only one non-abnormal edge.  */
    1081                 :      26571 :       if (single_succ_p (bb))
    1082                 :          0 :         e = single_succ_edge (bb);
    1083                 :            :       /* Otherwise chose one that is closer to bb with live statement in it.
    1084                 :            :          To be able to chose one, we compute inverted post order starting from
    1085                 :            :          all BBs with live statements.  */
    1086                 :          0 :       if (!e)
    1087                 :            :         {
    1088                 :      26571 :           if (!bb_postorder)
    1089                 :            :             {
    1090                 :      30794 :               auto_vec<int, 20> postorder;
    1091                 :      15397 :                  inverted_post_order_compute (&postorder,
    1092                 :            :                                               &bb_contains_live_stmts);
    1093                 :      15397 :               bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
    1094                 :    1067890 :               for (unsigned int i = 0; i < postorder.length (); ++i)
    1095                 :     518550 :                  bb_postorder[postorder[i]] = i;
    1096                 :            :             }
    1097                 :      79729 :           FOR_EACH_EDGE (e2, ei, bb->succs)
    1098                 :      53158 :             if (!e || e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
    1099                 :      26587 :                 || bb_postorder [e->dest->index]
    1100                 :      26587 :                    < bb_postorder [e2->dest->index])
    1101                 :      39088 :               e = e2;
    1102                 :            :         }
    1103                 :      26571 :       gcc_assert (e);
    1104                 :      26571 :       e->probability = profile_probability::always ();
    1105                 :            : 
    1106                 :            :       /* The edge is no longer associated with a conditional, so it does
    1107                 :            :          not have TRUE/FALSE flags.
    1108                 :            :          We are also safe to drop EH/ABNORMAL flags and turn them into
    1109                 :            :          normal control flow, because we know that all the destinations (including
    1110                 :            :          those odd edges) are equivalent for program execution.  */
    1111                 :      26571 :       e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_EH | EDGE_ABNORMAL);
    1112                 :            : 
    1113                 :            :       /* The lone outgoing edge from BB will be a fallthru edge.  */
    1114                 :      26571 :       e->flags |= EDGE_FALLTHRU;
    1115                 :            : 
    1116                 :            :       /* Remove the remaining outgoing edges.  */
    1117                 :      79729 :       FOR_EACH_EDGE (e2, ei, bb->succs)
    1118                 :      53158 :         if (e != e2)
    1119                 :            :           {
    1120                 :            :             /* If we made a BB unconditionally exit a loop or removed
    1121                 :            :                an entry into an irreducible region, then this transform
    1122                 :            :                alters the set of BBs in the loop.  Schedule a fixup.  */
    1123                 :      26587 :             if (loop_exit_edge_p (bb->loop_father, e)
    1124                 :      26587 :                 || (e2->dest->flags & BB_IRREDUCIBLE_LOOP))
    1125                 :      12588 :               loops_state_set (LOOPS_NEED_FIXUP);
    1126                 :      26587 :             to_remove_edges.safe_push (e2);
    1127                 :            :           }
    1128                 :            :     }
    1129                 :            : 
    1130                 :            :   /* If this is a store into a variable that is being optimized away,
    1131                 :            :      add a debug bind stmt if possible.  */
    1132                 :    4421600 :   if (MAY_HAVE_DEBUG_BIND_STMTS
    1133                 :     809421 :       && gimple_assign_single_p (stmt)
    1134                 :    5231020 :       && is_gimple_val (gimple_assign_rhs1 (stmt)))
    1135                 :            :     {
    1136                 :     342093 :       tree lhs = gimple_assign_lhs (stmt);
    1137                 :     256763 :       if ((VAR_P (lhs) || TREE_CODE (lhs) == PARM_DECL)
    1138                 :      85649 :           && !DECL_IGNORED_P (lhs)
    1139                 :      55976 :           && is_gimple_reg_type (TREE_TYPE (lhs))
    1140                 :        241 :           && !is_global_var (lhs)
    1141                 :     342334 :           && !DECL_HAS_VALUE_EXPR_P (lhs))
    1142                 :            :         {
    1143                 :        241 :           tree rhs = gimple_assign_rhs1 (stmt);
    1144                 :        241 :           gdebug *note
    1145                 :        241 :             = gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt);
    1146                 :        241 :           gsi_insert_after (i, note, GSI_SAME_STMT);
    1147                 :            :         }
    1148                 :            :     }
    1149                 :            : 
    1150                 :    4421600 :   unlink_stmt_vdef (stmt);
    1151                 :    4421600 :   gsi_remove (i, true);
    1152                 :    4421600 :   release_defs (stmt);
    1153                 :    4421600 : }
    1154                 :            : 
    1155                 :            : /* Helper for maybe_optimize_arith_overflow.  Find in *TP if there are any
    1156                 :            :    uses of data (SSA_NAME) other than REALPART_EXPR referencing it.  */
    1157                 :            : 
    1158                 :            : static tree
    1159                 :          4 : find_non_realpart_uses (tree *tp, int *walk_subtrees, void *data)
    1160                 :            : {
    1161                 :          4 :   if (TYPE_P (*tp) || TREE_CODE (*tp) == REALPART_EXPR)
    1162                 :          0 :     *walk_subtrees = 0;
    1163                 :          4 :   if (*tp == (tree) data)
    1164                 :          2 :     return *tp;
    1165                 :            :   return NULL_TREE;
    1166                 :            : }
    1167                 :            : 
    1168                 :            : /* If the IMAGPART_EXPR of the {ADD,SUB,MUL}_OVERFLOW result is never used,
    1169                 :            :    but REALPART_EXPR is, optimize the {ADD,SUB,MUL}_OVERFLOW internal calls
    1170                 :            :    into plain unsigned {PLUS,MINUS,MULT}_EXPR, and if needed reset debug
    1171                 :            :    uses.  */
    1172                 :            : 
    1173                 :            : static void
    1174                 :     260752 : maybe_optimize_arith_overflow (gimple_stmt_iterator *gsi,
    1175                 :            :                                enum tree_code subcode)
    1176                 :            : {
    1177                 :     260752 :   gimple *stmt = gsi_stmt (*gsi);
    1178                 :     260752 :   tree lhs = gimple_call_lhs (stmt);
    1179                 :            : 
    1180                 :     260752 :   if (lhs == NULL || TREE_CODE (lhs) != SSA_NAME)
    1181                 :     260724 :     return;
    1182                 :            : 
    1183                 :     260752 :   imm_use_iterator imm_iter;
    1184                 :     260752 :   use_operand_p use_p;
    1185                 :     260752 :   bool has_debug_uses = false;
    1186                 :     260752 :   bool has_realpart_uses = false;
    1187                 :     260752 :   bool has_other_uses = false;
    1188                 :     261178 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
    1189                 :            :     {
    1190                 :     261150 :       gimple *use_stmt = USE_STMT (use_p);
    1191                 :     261150 :       if (is_gimple_debug (use_stmt))
    1192                 :            :         has_debug_uses = true;
    1193                 :     261050 :       else if (is_gimple_assign (use_stmt)
    1194                 :     261050 :                && gimple_assign_rhs_code (use_stmt) == REALPART_EXPR
    1195                 :     261376 :                && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == lhs)
    1196                 :            :         has_realpart_uses = true;
    1197                 :            :       else
    1198                 :            :         {
    1199                 :            :           has_other_uses = true;
    1200                 :            :           break;
    1201                 :            :         }
    1202                 :            :     }
    1203                 :            : 
    1204                 :     260752 :   if (!has_realpart_uses || has_other_uses)
    1205                 :            :     return;
    1206                 :            : 
    1207                 :         28 :   tree arg0 = gimple_call_arg (stmt, 0);
    1208                 :         28 :   tree arg1 = gimple_call_arg (stmt, 1);
    1209                 :         28 :   location_t loc = gimple_location (stmt);
    1210                 :         28 :   tree type = TREE_TYPE (TREE_TYPE (lhs));
    1211                 :         28 :   tree utype = type;
    1212                 :         28 :   if (!TYPE_UNSIGNED (type))
    1213                 :          4 :     utype = build_nonstandard_integer_type (TYPE_PRECISION (type), 1);
    1214                 :         28 :   tree result = fold_build2_loc (loc, subcode, utype,
    1215                 :            :                                  fold_convert_loc (loc, utype, arg0),
    1216                 :            :                                  fold_convert_loc (loc, utype, arg1));
    1217                 :         28 :   result = fold_convert_loc (loc, type, result);
    1218                 :            : 
    1219                 :         28 :   if (has_debug_uses)
    1220                 :            :     {
    1221                 :          2 :       gimple *use_stmt;
    1222                 :          6 :       FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
    1223                 :            :         {
    1224                 :          4 :           if (!gimple_debug_bind_p (use_stmt))
    1225                 :          2 :             continue;
    1226                 :          2 :           tree v = gimple_debug_bind_get_value (use_stmt);
    1227                 :          2 :           if (walk_tree (&v, find_non_realpart_uses, lhs, NULL))
    1228                 :            :             {
    1229                 :          2 :               gimple_debug_bind_reset_value (use_stmt);
    1230                 :          4 :               update_stmt (use_stmt);
    1231                 :            :             }
    1232                 :            :         }
    1233                 :            :     }
    1234                 :            : 
    1235                 :         28 :   if (TREE_CODE (result) == INTEGER_CST && TREE_OVERFLOW (result))
    1236                 :          0 :     result = drop_tree_overflow (result);
    1237                 :         28 :   tree overflow = build_zero_cst (type);
    1238                 :         28 :   tree ctype = build_complex_type (type);
    1239                 :         28 :   if (TREE_CODE (result) == INTEGER_CST)
    1240                 :          0 :     result = build_complex (ctype, result, overflow);
    1241                 :            :   else
    1242                 :         28 :     result = build2_loc (gimple_location (stmt), COMPLEX_EXPR,
    1243                 :            :                          ctype, result, overflow);
    1244                 :            : 
    1245                 :         28 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1246                 :            :     {
    1247                 :          0 :       fprintf (dump_file, "Transforming call: ");
    1248                 :          0 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1249                 :          0 :       fprintf (dump_file, "because the overflow result is never used into: ");
    1250                 :          0 :       print_generic_stmt (dump_file, result, TDF_SLIM);
    1251                 :          0 :       fprintf (dump_file, "\n");
    1252                 :            :     }
    1253                 :            : 
    1254                 :         28 :   if (!update_call_from_tree (gsi, result))
    1255                 :         28 :     gimplify_and_update_call_from_tree (gsi, result);
    1256                 :            : }
    1257                 :            : 
    1258                 :            : /* Eliminate unnecessary statements. Any instruction not marked as necessary
    1259                 :            :    contributes nothing to the program, and can be deleted.  */
    1260                 :            : 
    1261                 :            : static bool
    1262                 :    5204660 : eliminate_unnecessary_stmts (void)
    1263                 :            : {
    1264                 :    5204660 :   bool something_changed = false;
    1265                 :    5204660 :   basic_block bb;
    1266                 :    5204660 :   gimple_stmt_iterator gsi, psi;
    1267                 :    5204660 :   gimple *stmt;
    1268                 :    5204660 :   tree call;
    1269                 :    5204660 :   vec<basic_block> h;
    1270                 :    5204660 :   auto_vec<edge> to_remove_edges;
    1271                 :            : 
    1272                 :    5204660 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1273                 :         99 :     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
    1274                 :            : 
    1275                 :    5204660 :   clear_special_calls ();
    1276                 :            : 
    1277                 :            :   /* Walking basic blocks and statements in reverse order avoids
    1278                 :            :      releasing SSA names before any other DEFs that refer to them are
    1279                 :            :      released.  This helps avoid loss of debug information, as we get
    1280                 :            :      a chance to propagate all RHSs of removed SSAs into debug uses,
    1281                 :            :      rather than only the latest ones.  E.g., consider:
    1282                 :            : 
    1283                 :            :      x_3 = y_1 + z_2;
    1284                 :            :      a_5 = x_3 - b_4;
    1285                 :            :      # DEBUG a => a_5
    1286                 :            : 
    1287                 :            :      If we were to release x_3 before a_5, when we reached a_5 and
    1288                 :            :      tried to substitute it into the debug stmt, we'd see x_3 there,
    1289                 :            :      but x_3's DEF, type, etc would have already been disconnected.
    1290                 :            :      By going backwards, the debug stmt first changes to:
    1291                 :            : 
    1292                 :            :      # DEBUG a => x_3 - b_4
    1293                 :            : 
    1294                 :            :      and then to:
    1295                 :            : 
    1296                 :            :      # DEBUG a => y_1 + z_2 - b_4
    1297                 :            : 
    1298                 :            :      as desired.  */
    1299                 :    5204660 :   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
    1300                 :    5204660 :   h = get_all_dominated_blocks (CDI_DOMINATORS,
    1301                 :    5204660 :                                 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
    1302                 :            : 
    1303                 :   53776800 :   while (h.length ())
    1304                 :            :     {
    1305                 :   48572100 :       bb = h.pop ();
    1306                 :            : 
    1307                 :            :       /* Remove dead statements.  */
    1308                 :   97144200 :       auto_bitmap debug_seen;
    1309                 :  449327000 :       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
    1310                 :            :         {
    1311                 :  352183000 :           stmt = gsi_stmt (gsi);
    1312                 :            : 
    1313                 :  352183000 :           psi = gsi;
    1314                 :  352183000 :           gsi_prev (&psi);
    1315                 :            : 
    1316                 :  352183000 :           stats.total++;
    1317                 :            : 
    1318                 :            :           /* We can mark a call to free as not necessary if the
    1319                 :            :              defining statement of its argument is not necessary
    1320                 :            :              (and thus is getting removed).  */
    1321                 :  352183000 :           if (gimple_plf (stmt, STMT_NECESSARY)
    1322                 :  352183000 :               && (gimple_call_builtin_p (stmt, BUILT_IN_FREE)
    1323                 :  342326000 :                   || (is_gimple_call (stmt)
    1324                 :   23007100 :                       && gimple_call_operator_delete_p (as_a <gcall *> (stmt)))))
    1325                 :            :             {
    1326                 :     670487 :               tree ptr = gimple_call_arg (stmt, 0);
    1327                 :     670487 :               if (TREE_CODE (ptr) == SSA_NAME)
    1328                 :            :                 {
    1329                 :     670142 :                   gimple *def_stmt = SSA_NAME_DEF_STMT (ptr);
    1330                 :     670142 :                   if (!gimple_nop_p (def_stmt)
    1331                 :     670142 :                       && !gimple_plf (def_stmt, STMT_NECESSARY))
    1332                 :       1539 :                     gimple_set_plf (stmt, STMT_NECESSARY, false);
    1333                 :            :                 }
    1334                 :            :             }
    1335                 :            : 
    1336                 :            :           /* If GSI is not necessary then remove it.  */
    1337                 :  352183000 :           if (!gimple_plf (stmt, STMT_NECESSARY))
    1338                 :            :             {
    1339                 :            :               /* Keep clobbers that we can keep live live.  */
    1340                 :    9677730 :               if (gimple_clobber_p (stmt))
    1341                 :            :                 {
    1342                 :    7087590 :                   ssa_op_iter iter;
    1343                 :    7087590 :                   use_operand_p use_p;
    1344                 :    7087590 :                   bool dead = false;
    1345                 :    7848100 :                   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
    1346                 :            :                     {
    1347                 :     761872 :                       tree name = USE_FROM_PTR (use_p);
    1348                 :     761872 :                       if (!SSA_NAME_IS_DEFAULT_DEF (name)
    1349                 :     761872 :                           && !bitmap_bit_p (processed, SSA_NAME_VERSION (name)))
    1350                 :            :                         {
    1351                 :            :                           dead = true;
    1352                 :            :                           break;
    1353                 :            :                         }
    1354                 :            :                     }
    1355                 :    7087590 :                   if (!dead)
    1356                 :            :                     {
    1357                 :    7086220 :                       bitmap_clear (debug_seen);
    1358                 :    7086220 :                       continue;
    1359                 :            :                     }
    1360                 :            :                 }
    1361                 :    2591510 :               if (!is_gimple_debug (stmt))
    1362                 :    2443870 :                 something_changed = true;
    1363                 :    2591510 :               remove_dead_stmt (&gsi, bb, to_remove_edges);
    1364                 :    2591510 :               continue;
    1365                 :            :             }
    1366                 :  342505000 :           else if (is_gimple_call (stmt))
    1367                 :            :             {
    1368                 :   23186400 :               tree name = gimple_call_lhs (stmt);
    1369                 :            : 
    1370                 :   23186400 :               notice_special_calls (as_a <gcall *> (stmt));
    1371                 :            : 
    1372                 :            :               /* When LHS of var = call (); is dead, simplify it into
    1373                 :            :                  call (); saving one operand.  */
    1374                 :   23186400 :               if (name
    1375                 :    9205060 :                   && TREE_CODE (name) == SSA_NAME
    1376                 :    7593940 :                   && !bitmap_bit_p (processed, SSA_NAME_VERSION (name))
    1377                 :            :                   /* Avoid doing so for allocation calls which we
    1378                 :            :                      did not mark as necessary, it will confuse the
    1379                 :            :                      special logic we apply to malloc/free pair removal.  */
    1380                 :   23238900 :                   && (!(call = gimple_call_fndecl (stmt))
    1381                 :      43428 :                       || ((DECL_BUILT_IN_CLASS (call) != BUILT_IN_NORMAL
    1382                 :       6705 :                            || (DECL_FUNCTION_CODE (call) != BUILT_IN_ALIGNED_ALLOC
    1383                 :       6705 :                                && DECL_FUNCTION_CODE (call) != BUILT_IN_MALLOC
    1384                 :       6699 :                                && DECL_FUNCTION_CODE (call) != BUILT_IN_CALLOC
    1385                 :       6668 :                                && !ALLOCA_FUNCTION_CODE_P
    1386                 :            :                                (DECL_FUNCTION_CODE (call))))
    1387                 :      43391 :                           && !DECL_IS_REPLACEABLE_OPERATOR_NEW_P (call))))
    1388                 :            :                 {
    1389                 :      52370 :                   something_changed = true;
    1390                 :      52370 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    1391                 :            :                     {
    1392                 :          0 :                       fprintf (dump_file, "Deleting LHS of call: ");
    1393                 :          0 :                       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1394                 :          0 :                       fprintf (dump_file, "\n");
    1395                 :            :                     }
    1396                 :            : 
    1397                 :      52370 :                   gimple_call_set_lhs (stmt, NULL_TREE);
    1398                 :      52370 :                   maybe_clean_or_replace_eh_stmt (stmt, stmt);
    1399                 :      52370 :                   update_stmt (stmt);
    1400                 :      52370 :                   release_ssa_name (name);
    1401                 :            : 
    1402                 :            :                   /* GOMP_SIMD_LANE (unless three argument) or ASAN_POISON
    1403                 :            :                      without lhs is not needed.  */
    1404                 :      52370 :                   if (gimple_call_internal_p (stmt))
    1405                 :       7165 :                     switch (gimple_call_internal_fn (stmt))
    1406                 :            :                       {
    1407                 :        738 :                       case IFN_GOMP_SIMD_LANE:
    1408                 :        738 :                         if (gimple_call_num_args (stmt) >= 3
    1409                 :        738 :                             && !integer_nonzerop (gimple_call_arg (stmt, 2)))
    1410                 :            :                           break;
    1411                 :            :                         /* FALLTHRU */
    1412                 :        814 :                       case IFN_ASAN_POISON:
    1413                 :        814 :                         remove_dead_stmt (&gsi, bb, to_remove_edges);
    1414                 :        814 :                         break;
    1415                 :            :                       default:
    1416                 :            :                         break;
    1417                 :            :                       }
    1418                 :            :                 }
    1419                 :   23134000 :               else if (gimple_call_internal_p (stmt))
    1420                 :     625025 :                 switch (gimple_call_internal_fn (stmt))
    1421                 :            :                   {
    1422                 :      72188 :                   case IFN_ADD_OVERFLOW:
    1423                 :      72188 :                     maybe_optimize_arith_overflow (&gsi, PLUS_EXPR);
    1424                 :      72188 :                     break;
    1425                 :      91073 :                   case IFN_SUB_OVERFLOW:
    1426                 :      91073 :                     maybe_optimize_arith_overflow (&gsi, MINUS_EXPR);
    1427                 :      91073 :                     break;
    1428                 :      97491 :                   case IFN_MUL_OVERFLOW:
    1429                 :      97491 :                     maybe_optimize_arith_overflow (&gsi, MULT_EXPR);
    1430                 :      97491 :                     break;
    1431                 :            :                   default:
    1432                 :            :                     break;
    1433                 :            :                   }
    1434                 :            :             }
    1435                 :  319319000 :           else if (gimple_debug_bind_p (stmt))
    1436                 :            :             {
    1437                 :            :               /* We are only keeping the last debug-bind of a
    1438                 :            :                  non-DEBUG_EXPR_DECL variable in a series of
    1439                 :            :                  debug-bind stmts.  */
    1440                 :  148056000 :               tree var = gimple_debug_bind_get_var (stmt);
    1441                 :  148056000 :               if (TREE_CODE (var) != DEBUG_EXPR_DECL
    1442                 :  285847000 :                   && !bitmap_set_bit (debug_seen, DECL_UID (var)))
    1443                 :    1829280 :                 remove_dead_stmt (&gsi, bb, to_remove_edges);
    1444                 :  148056000 :               continue;
    1445                 :            :             }
    1446                 :  194449000 :           bitmap_clear (debug_seen);
    1447                 :            :         }
    1448                 :            : 
    1449                 :            :       /* Remove dead PHI nodes.  */
    1450                 :   48572100 :       something_changed |= remove_dead_phis (bb);
    1451                 :            :     }
    1452                 :            : 
    1453                 :    5204660 :   h.release ();
    1454                 :            : 
    1455                 :            :   /* Since we don't track liveness of virtual PHI nodes, it is possible that we
    1456                 :            :      rendered some PHI nodes unreachable while they are still in use.
    1457                 :            :      Mark them for renaming.  */
    1458                 :    5204660 :   if (!to_remove_edges.is_empty ())
    1459                 :            :     {
    1460                 :            :       basic_block prev_bb;
    1461                 :            : 
    1462                 :            :       /* Remove edges.  We've delayed this to not get bogus debug stmts
    1463                 :            :          during PHI node removal.  */
    1464                 :      83968 :       for (unsigned i = 0; i < to_remove_edges.length (); ++i)
    1465                 :      26587 :         remove_edge (to_remove_edges[i]);
    1466                 :      15397 :       cfg_altered = true;
    1467                 :            : 
    1468                 :      15397 :       find_unreachable_blocks ();
    1469                 :            : 
    1470                 :            :       /* Delete all unreachable basic blocks in reverse dominator order.  */
    1471                 :      15397 :       for (bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
    1472                 :     501835 :            bb != ENTRY_BLOCK_PTR_FOR_FN (cfun); bb = prev_bb)
    1473                 :            :         {
    1474                 :     486438 :           prev_bb = bb->prev_bb;
    1475                 :            : 
    1476                 :     486438 :           if (!bitmap_bit_p (bb_contains_live_stmts, bb->index)
    1477                 :     486438 :               || !(bb->flags & BB_REACHABLE))
    1478                 :            :             {
    1479                 :     152301 :               for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
    1480                 :       8943 :                    gsi_next (&gsi))
    1481                 :      26825 :                 if (virtual_operand_p (gimple_phi_result (gsi.phi ())))
    1482                 :            :                   {
    1483                 :       8939 :                     bool found = false;
    1484                 :       8939 :                     imm_use_iterator iter;
    1485                 :            : 
    1486                 :      10224 :                     FOR_EACH_IMM_USE_STMT (stmt, iter,
    1487                 :            :                                            gimple_phi_result (gsi.phi ()))
    1488                 :            :                       {
    1489                 :       8650 :                         if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
    1490                 :        152 :                           continue;
    1491                 :       8498 :                         if (gimple_code (stmt) == GIMPLE_PHI
    1492                 :       8498 :                             || gimple_plf (stmt, STMT_NECESSARY))
    1493                 :            :                           {
    1494                 :       7365 :                             found = true;
    1495                 :      17589 :                             BREAK_FROM_IMM_USE_STMT (iter);
    1496                 :            :                           }
    1497                 :            :                       }
    1498                 :       7365 :                     if (found)
    1499                 :       7365 :                       mark_virtual_phi_result_for_renaming (gsi.phi ());
    1500                 :            :                   }
    1501                 :            : 
    1502                 :     143358 :               if (!(bb->flags & BB_REACHABLE))
    1503                 :            :                 {
    1504                 :            :                   /* Speed up the removal of blocks that don't
    1505                 :            :                      dominate others.  Walking backwards, this should
    1506                 :            :                      be the common case.  ??? Do we need to recompute
    1507                 :            :                      dominators because of cfg_altered?  */
    1508                 :      27929 :                   if (!first_dom_son (CDI_DOMINATORS, bb))
    1509                 :      27522 :                     delete_basic_block (bb);
    1510                 :            :                   else
    1511                 :            :                     {
    1512                 :        407 :                       h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
    1513                 :            : 
    1514                 :       2132 :                       while (h.length ())
    1515                 :            :                         {
    1516                 :       1725 :                           bb = h.pop ();
    1517                 :       1725 :                           prev_bb = bb->prev_bb;
    1518                 :            :                           /* Rearrangements to the CFG may have failed
    1519                 :            :                              to update the dominators tree, so that
    1520                 :            :                              formerly-dominated blocks are now
    1521                 :            :                              otherwise reachable.  */
    1522                 :       1725 :                           if (!!(bb->flags & BB_REACHABLE))
    1523                 :          0 :                             continue;
    1524                 :       1725 :                           delete_basic_block (bb);
    1525                 :            :                         }
    1526                 :            : 
    1527                 :     502242 :                       h.release ();
    1528                 :            :                     }
    1529                 :            :                 }
    1530                 :            :             }
    1531                 :            :         }
    1532                 :            :     }
    1533                 :            : 
    1534                 :    5204660 :   if (bb_postorder)
    1535                 :      15397 :     free (bb_postorder);
    1536                 :    5204660 :   bb_postorder = NULL;
    1537                 :            : 
    1538                 :    5204660 :   return something_changed;
    1539                 :            : }
    1540                 :            : 
    1541                 :            : 
    1542                 :            : /* Print out removed statement statistics.  */
    1543                 :            : 
    1544                 :            : static void
    1545                 :         99 : print_stats (void)
    1546                 :            : {
    1547                 :         99 :   float percg;
    1548                 :            : 
    1549                 :         99 :   percg = ((float) stats.removed / (float) stats.total) * 100;
    1550                 :         99 :   fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
    1551                 :            :            stats.removed, stats.total, (int) percg);
    1552                 :            : 
    1553                 :         99 :   if (stats.total_phis == 0)
    1554                 :            :     percg = 0;
    1555                 :            :   else
    1556                 :          3 :     percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
    1557                 :            : 
    1558                 :         99 :   fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
    1559                 :            :            stats.removed_phis, stats.total_phis, (int) percg);
    1560                 :         99 : }
    1561                 :            : 
    1562                 :            : /* Initialization for this pass.  Set up the used data structures.  */
    1563                 :            : 
    1564                 :            : static void
    1565                 :    5204660 : tree_dce_init (bool aggressive)
    1566                 :            : {
    1567                 :    5204660 :   memset ((void *) &stats, 0, sizeof (stats));
    1568                 :            : 
    1569                 :    5204660 :   if (aggressive)
    1570                 :            :     {
    1571                 :    2318390 :       last_stmt_necessary = sbitmap_alloc (last_basic_block_for_fn (cfun));
    1572                 :    2318390 :       bitmap_clear (last_stmt_necessary);
    1573                 :    2318390 :       bb_contains_live_stmts = sbitmap_alloc (last_basic_block_for_fn (cfun));
    1574                 :    2318390 :       bitmap_clear (bb_contains_live_stmts);
    1575                 :            :     }
    1576                 :            : 
    1577                 :   10409300 :   processed = sbitmap_alloc (num_ssa_names + 1);
    1578                 :    5204660 :   bitmap_clear (processed);
    1579                 :            : 
    1580                 :    5204660 :   worklist.create (64);
    1581                 :    5204660 :   cfg_altered = false;
    1582                 :    5204660 : }
    1583                 :            : 
    1584                 :            : /* Cleanup after this pass.  */
    1585                 :            : 
    1586                 :            : static void
    1587                 :    5204660 : tree_dce_done (bool aggressive)
    1588                 :            : {
    1589                 :    5204660 :   if (aggressive)
    1590                 :            :     {
    1591                 :    2318390 :       delete cd;
    1592                 :    2318390 :       sbitmap_free (visited_control_parents);
    1593                 :    2318390 :       sbitmap_free (last_stmt_necessary);
    1594                 :    2318390 :       sbitmap_free (bb_contains_live_stmts);
    1595                 :    2318390 :       bb_contains_live_stmts = NULL;
    1596                 :            :     }
    1597                 :            : 
    1598                 :    5204660 :   sbitmap_free (processed);
    1599                 :            : 
    1600                 :    5204660 :   worklist.release ();
    1601                 :    5204660 : }
    1602                 :            : 
    1603                 :            : /* Main routine to eliminate dead code.
    1604                 :            : 
    1605                 :            :    AGGRESSIVE controls the aggressiveness of the algorithm.
    1606                 :            :    In conservative mode, we ignore control dependence and simply declare
    1607                 :            :    all but the most trivially dead branches necessary.  This mode is fast.
    1608                 :            :    In aggressive mode, control dependences are taken into account, which
    1609                 :            :    results in more dead code elimination, but at the cost of some time.
    1610                 :            : 
    1611                 :            :    FIXME: Aggressive mode before PRE doesn't work currently because
    1612                 :            :           the dominance info is not invalidated after DCE1.  This is
    1613                 :            :           not an issue right now because we only run aggressive DCE
    1614                 :            :           as the last tree SSA pass, but keep this in mind when you
    1615                 :            :           start experimenting with pass ordering.  */
    1616                 :            : 
    1617                 :            : static unsigned int
    1618                 :    5204660 : perform_tree_ssa_dce (bool aggressive)
    1619                 :            : {
    1620                 :    5204660 :   bool something_changed = 0;
    1621                 :            : 
    1622                 :    5204660 :   calculate_dominance_info (CDI_DOMINATORS);
    1623                 :            : 
    1624                 :            :   /* Preheaders are needed for SCEV to work.
    1625                 :            :      Simple lateches and recorded exits improve chances that loop will
    1626                 :            :      proved to be finite in testcases such as in loop-15.c and loop-24.c  */
    1627                 :    5204660 :   bool in_loop_pipeline = scev_initialized_p ();
    1628                 :    5204660 :   if (aggressive && ! in_loop_pipeline)
    1629                 :            :     {
    1630                 :    2170340 :       scev_initialize ();
    1631                 :    2170340 :       loop_optimizer_init (LOOPS_NORMAL
    1632                 :            :                            | LOOPS_HAVE_RECORDED_EXITS);
    1633                 :            :     }
    1634                 :            : 
    1635                 :    5204660 :   tree_dce_init (aggressive);
    1636                 :            : 
    1637                 :    5204660 :   if (aggressive)
    1638                 :            :     {
    1639                 :            :       /* Compute control dependence.  */
    1640                 :    2318390 :       calculate_dominance_info (CDI_POST_DOMINATORS);
    1641                 :    2318390 :       cd = new control_dependences ();
    1642                 :            : 
    1643                 :    4636780 :       visited_control_parents =
    1644                 :    2318390 :         sbitmap_alloc (last_basic_block_for_fn (cfun));
    1645                 :    2318390 :       bitmap_clear (visited_control_parents);
    1646                 :            : 
    1647                 :    2318390 :       mark_dfs_back_edges ();
    1648                 :            :     }
    1649                 :            : 
    1650                 :    5204660 :   find_obviously_necessary_stmts (aggressive);
    1651                 :            : 
    1652                 :    5204660 :   if (aggressive && ! in_loop_pipeline)
    1653                 :            :     {
    1654                 :    2170340 :       loop_optimizer_finalize ();
    1655                 :    2170340 :       scev_finalize ();
    1656                 :            :     }
    1657                 :            : 
    1658                 :    5204660 :   longest_chain = 0;
    1659                 :    5204660 :   total_chain = 0;
    1660                 :    5204660 :   nr_walks = 0;
    1661                 :    5204660 :   chain_ovfl = false;
    1662                 :    5204660 :   visited = BITMAP_ALLOC (NULL);
    1663                 :    5204660 :   propagate_necessity (aggressive);
    1664                 :    5204660 :   BITMAP_FREE (visited);
    1665                 :            : 
    1666                 :    5204660 :   something_changed |= eliminate_unnecessary_stmts ();
    1667                 :    5204660 :   something_changed |= cfg_altered;
    1668                 :            : 
    1669                 :            :   /* We do not update postdominators, so free them unconditionally.  */
    1670                 :    5204660 :   free_dominance_info (CDI_POST_DOMINATORS);
    1671                 :            : 
    1672                 :            :   /* If we removed paths in the CFG, then we need to update
    1673                 :            :      dominators as well.  I haven't investigated the possibility
    1674                 :            :      of incrementally updating dominators.  */
    1675                 :    5204660 :   if (cfg_altered)
    1676                 :      15397 :     free_dominance_info (CDI_DOMINATORS);
    1677                 :            : 
    1678                 :    5204660 :   statistics_counter_event (cfun, "Statements deleted", stats.removed);
    1679                 :    5204660 :   statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
    1680                 :            : 
    1681                 :            :   /* Debugging dumps.  */
    1682                 :    5204660 :   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
    1683                 :         99 :     print_stats ();
    1684                 :            : 
    1685                 :    5204660 :   tree_dce_done (aggressive);
    1686                 :            : 
    1687                 :    5204660 :   if (something_changed)
    1688                 :            :     {
    1689                 :     695605 :       free_numbers_of_iterations_estimates (cfun);
    1690                 :     695605 :       if (in_loop_pipeline)
    1691                 :      34569 :         scev_reset ();
    1692                 :     695605 :       return TODO_update_ssa | TODO_cleanup_cfg;
    1693                 :            :     }
    1694                 :            :   return 0;
    1695                 :            : }
    1696                 :            : 
    1697                 :            : /* Pass entry points.  */
    1698                 :            : static unsigned int
    1699                 :    2778380 : tree_ssa_dce (void)
    1700                 :            : {
    1701                 :          0 :   return perform_tree_ssa_dce (/*aggressive=*/false);
    1702                 :            : }
    1703                 :            : 
    1704                 :            : static unsigned int
    1705                 :    2426280 : tree_ssa_cd_dce (void)
    1706                 :            : {
    1707                 :          0 :   return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
    1708                 :            : }
    1709                 :            : 
    1710                 :            : namespace {
    1711                 :            : 
    1712                 :            : const pass_data pass_data_dce =
    1713                 :            : {
    1714                 :            :   GIMPLE_PASS, /* type */
    1715                 :            :   "dce", /* name */
    1716                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    1717                 :            :   TV_TREE_DCE, /* tv_id */
    1718                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    1719                 :            :   0, /* properties_provided */
    1720                 :            :   0, /* properties_destroyed */
    1721                 :            :   0, /* todo_flags_start */
    1722                 :            :   0, /* todo_flags_finish */
    1723                 :            : };
    1724                 :            : 
    1725                 :            : class pass_dce : public gimple_opt_pass
    1726                 :            : {
    1727                 :            : public:
    1728                 :    1604320 :   pass_dce (gcc::context *ctxt)
    1729                 :    3208640 :     : gimple_opt_pass (pass_data_dce, ctxt)
    1730                 :            :   {}
    1731                 :            : 
    1732                 :            :   /* opt_pass methods: */
    1733                 :    1403780 :   opt_pass * clone () { return new pass_dce (m_ctxt); }
    1734                 :    2779980 :   virtual bool gate (function *) { return flag_tree_dce != 0; }
    1735                 :    2778380 :   virtual unsigned int execute (function *) { return tree_ssa_dce (); }
    1736                 :            : 
    1737                 :            : }; // class pass_dce
    1738                 :            : 
    1739                 :            : } // anon namespace
    1740                 :            : 
    1741                 :            : gimple_opt_pass *
    1742                 :     200540 : make_pass_dce (gcc::context *ctxt)
    1743                 :            : {
    1744                 :     200540 :   return new pass_dce (ctxt);
    1745                 :            : }
    1746                 :            : 
    1747                 :            : namespace {
    1748                 :            : 
    1749                 :            : const pass_data pass_data_cd_dce =
    1750                 :            : {
    1751                 :            :   GIMPLE_PASS, /* type */
    1752                 :            :   "cddce", /* name */
    1753                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    1754                 :            :   TV_TREE_CD_DCE, /* tv_id */
    1755                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    1756                 :            :   0, /* properties_provided */
    1757                 :            :   0, /* properties_destroyed */
    1758                 :            :   0, /* todo_flags_start */
    1759                 :            :   0, /* todo_flags_finish */
    1760                 :            : };
    1761                 :            : 
    1762                 :            : class pass_cd_dce : public gimple_opt_pass
    1763                 :            : {
    1764                 :            : public:
    1765                 :     601620 :   pass_cd_dce (gcc::context *ctxt)
    1766                 :    1203240 :     : gimple_opt_pass (pass_data_cd_dce, ctxt)
    1767                 :            :   {}
    1768                 :            : 
    1769                 :            :   /* opt_pass methods: */
    1770                 :     401080 :   opt_pass * clone () { return new pass_cd_dce (m_ctxt); }
    1771                 :    2427230 :   virtual bool gate (function *) { return flag_tree_dce != 0; }
    1772                 :    2426280 :   virtual unsigned int execute (function *) { return tree_ssa_cd_dce (); }
    1773                 :            : 
    1774                 :            : }; // class pass_cd_dce
    1775                 :            : 
    1776                 :            : } // anon namespace
    1777                 :            : 
    1778                 :            : gimple_opt_pass *
    1779                 :     200540 : make_pass_cd_dce (gcc::context *ctxt)
    1780                 :            : {
    1781                 :     200540 :   return new pass_cd_dce (ctxt);
    1782                 :            : }
    1783                 :            : 
    1784                 :            : 
    1785                 :            : /* A cheap DCE interface.  WORKLIST is a list of possibly dead stmts and
    1786                 :            :    is consumed by this function.  The function has linear complexity in
    1787                 :            :    the number of dead stmts with a constant factor like the average SSA
    1788                 :            :    use operands number.  */
    1789                 :            : 
    1790                 :            : void
    1791                 :     644397 : simple_dce_from_worklist (bitmap worklist)
    1792                 :            : {
    1793                 :    2461930 :   while (! bitmap_empty_p (worklist))
    1794                 :            :     {
    1795                 :            :       /* Pop item.  */
    1796                 :    1817540 :       unsigned i = bitmap_first_set_bit (worklist);
    1797                 :    1817540 :       bitmap_clear_bit (worklist, i);
    1798                 :            : 
    1799                 :    1817540 :       tree def = ssa_name (i);
    1800                 :            :       /* Removed by somebody else or still in use.  */
    1801                 :    1817540 :       if (! def || ! has_zero_uses (def))
    1802                 :    1310990 :         continue;
    1803                 :            : 
    1804                 :     506546 :       gimple *t = SSA_NAME_DEF_STMT (def);
    1805                 :     506546 :       if (gimple_has_side_effects (t))
    1806                 :          0 :         continue;
    1807                 :            : 
    1808                 :            :       /* Add uses to the worklist.  */
    1809                 :     506546 :       ssa_op_iter iter;
    1810                 :     506546 :       use_operand_p use_p;
    1811                 :    1687960 :       FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
    1812                 :            :         {
    1813                 :     674869 :           tree use = USE_FROM_PTR (use_p);
    1814                 :     674869 :           if (TREE_CODE (use) == SSA_NAME
    1815                 :     674869 :               && ! SSA_NAME_IS_DEFAULT_DEF (use))
    1816                 :     626953 :             bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
    1817                 :            :         }
    1818                 :            : 
    1819                 :            :       /* Remove stmt.  */
    1820                 :     506546 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1821                 :            :         {
    1822                 :         75 :           fprintf (dump_file, "Removing dead stmt:");
    1823                 :         75 :           print_gimple_stmt (dump_file, t, 0);
    1824                 :            :         }
    1825                 :     506546 :       gimple_stmt_iterator gsi = gsi_for_stmt (t);
    1826                 :     506546 :       if (gimple_code (t) == GIMPLE_PHI)
    1827                 :      52748 :         remove_phi_node (&gsi, true);
    1828                 :            :       else
    1829                 :            :         {
    1830                 :     453798 :           gsi_remove (&gsi, true);
    1831                 :     453798 :           release_defs (t);
    1832                 :            :         }
    1833                 :            :     }
    1834                 :     644397 : }

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.