LCOV - code coverage report
Current view: top level - gcc - tree-ssa-dce.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 98.2 % 998 980
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 39 39
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Dead code elimination pass for the GNU compiler.
       2              :    Copyright (C) 2002-2026 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              : #include "tree-ssa.h"
      71              : #include "ipa-modref-tree.h"
      72              : #include "ipa-modref.h"
      73              : #include "memmodel.h"
      74              : 
      75              : static struct stmt_stats
      76              : {
      77              :   int total;
      78              :   int total_phis;
      79              :   int removed;
      80              :   int removed_phis;
      81              : } stats;
      82              : 
      83              : #define STMT_NECESSARY GF_PLF_1
      84              : 
      85              : static vec<gimple *> worklist;
      86              : 
      87              : /* Vector indicating an SSA name has already been processed and marked
      88              :    as necessary.  */
      89              : static sbitmap processed;
      90              : 
      91              : /* Vector indicating that the last statement of a basic block has already
      92              :    been marked as necessary.  */
      93              : static sbitmap last_stmt_necessary;
      94              : 
      95              : /* Vector indicating that BB contains statements that are live.  */
      96              : static sbitmap bb_contains_live_stmts;
      97              : 
      98              : /* Before we can determine whether a control branch is dead, we need to
      99              :    compute which blocks are control dependent on which edges.
     100              : 
     101              :    We expect each block to be control dependent on very few edges so we
     102              :    use a bitmap for each block recording its edges.  An array holds the
     103              :    bitmap.  The Ith bit in the bitmap is set if that block is dependent
     104              :    on the Ith edge.  */
     105              : static control_dependences *cd;
     106              : 
     107              : /* Vector indicating that a basic block has already had all the edges
     108              :    processed that it is control dependent on.  */
     109              : static sbitmap visited_control_parents;
     110              : 
     111              : /* TRUE if this pass alters the CFG (by removing control statements).
     112              :    FALSE otherwise.
     113              : 
     114              :    If this pass alters the CFG, then it will arrange for the dominators
     115              :    to be recomputed.  */
     116              : static bool cfg_altered;
     117              : 
     118              : /* When non-NULL holds map from basic block index into the postorder.  */
     119              : static int *bb_postorder;
     120              : 
     121              : 
     122              : /* True if we should treat any stmt with a vdef as necessary.  */
     123              : 
     124              : static inline bool
     125    277374784 : keep_all_vdefs_p ()
     126              : {
     127    277374784 :   return optimize_debug;
     128              : }
     129              : 
     130              : /* 1 if CALLEE is the function __cxa_atexit.
     131              :    2 if CALLEE is the function __aeabi_atexit.
     132              :    0 otherwise.   */
     133              : 
     134              : static inline int
     135     88537064 : is_cxa_atexit (const_tree callee)
     136              : {
     137     88537064 :   if (callee != NULL_TREE
     138     88537064 :       && strcmp (IDENTIFIER_POINTER (DECL_NAME (callee)), "__cxa_atexit") == 0)
     139              :     return 1;
     140     88414092 :   if (callee != NULL_TREE
     141     88414092 :       && strcmp (IDENTIFIER_POINTER (DECL_NAME (callee)), "__aeabi_atexit") == 0)
     142            0 :     return 2;
     143              :   return 0;
     144              : }
     145              : 
     146              : /* True if STMT is a call to __cxa_atexit (or __aeabi_atexit)
     147              :    and the function argument to that call is a const  or pure
     148              :    non-looping function decl.  */
     149              : 
     150              : static inline bool
     151     88537064 : is_removable_cxa_atexit_call (gimple *stmt)
     152              : {
     153     88537064 :   tree callee = gimple_call_fndecl (stmt);
     154     88537064 :   int functype = is_cxa_atexit (callee);
     155     88537064 :   if (!functype)
     156              :     return false;
     157       122972 :   if (gimple_call_num_args (stmt) != 3)
     158              :     return false;
     159              : 
     160              :   /* The function argument is the 1st argument for __cxa_atexit
     161              :      or the 2nd argument for __eabi_atexit. */
     162       245944 :   tree arg = gimple_call_arg (stmt, functype == 2 ? 1 : 0);
     163       122972 :   if (TREE_CODE (arg) != ADDR_EXPR)
     164              :     return false;
     165       122972 :   arg = TREE_OPERAND (arg, 0);
     166       122972 :   if (TREE_CODE (arg) != FUNCTION_DECL)
     167              :     return false;
     168       122972 :   int flags = flags_from_decl_or_type (arg);
     169              : 
     170              :   /* If the function is noreturn then it cannot be removed. */
     171       122972 :   if (flags & ECF_NORETURN)
     172              :     return false;
     173              : 
     174              :   /* The function needs to be const or pure and non looping.  */
     175       122814 :   return (flags & (ECF_CONST|ECF_PURE))
     176       122814 :           && !(flags & ECF_LOOPING_CONST_OR_PURE);
     177              : }
     178              : 
     179              : /* If STMT is not already marked necessary, mark it, and add it to the
     180              :    worklist if ADD_TO_WORKLIST is true.  */
     181              : 
     182              : static inline void
     183    500134700 : mark_stmt_necessary (gimple *stmt, bool add_to_worklist)
     184              : {
     185    500134700 :   gcc_assert (stmt);
     186              : 
     187    500134700 :   if (gimple_plf (stmt, STMT_NECESSARY))
     188              :     return;
     189              : 
     190    500134500 :   if (dump_file && (dump_flags & TDF_DETAILS))
     191              :     {
     192          852 :       fprintf (dump_file, "Marking useful stmt: ");
     193          852 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
     194          852 :       fprintf (dump_file, "\n");
     195              :     }
     196              : 
     197    500134500 :   gimple_set_plf (stmt, STMT_NECESSARY, true);
     198    500134500 :   if (add_to_worklist)
     199    110260570 :     worklist.safe_push (stmt);
     200    110260570 :   if (add_to_worklist && bb_contains_live_stmts && !is_gimple_debug (stmt))
     201     38697723 :     bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
     202              : }
     203              : 
     204              : 
     205              : /* Mark the statement defining operand OP as necessary.  */
     206              : 
     207              : static inline void
     208    346513469 : mark_operand_necessary (tree op)
     209              : {
     210    346513469 :   gimple *stmt;
     211    346513469 :   int ver;
     212              : 
     213    346513469 :   gcc_assert (op);
     214              : 
     215    346513469 :   ver = SSA_NAME_VERSION (op);
     216    346513469 :   if (bitmap_bit_p (processed, ver))
     217              :     {
     218    126806911 :       stmt = SSA_NAME_DEF_STMT (op);
     219    126806911 :       gcc_assert (gimple_nop_p (stmt)
     220              :                   || gimple_plf (stmt, STMT_NECESSARY));
     221    189479279 :       return;
     222              :     }
     223    219706558 :   bitmap_set_bit (processed, ver);
     224              : 
     225    219706558 :   stmt = SSA_NAME_DEF_STMT (op);
     226    219706558 :   gcc_assert (stmt);
     227              : 
     228    219706558 :   if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
     229              :     return;
     230              : 
     231    157034190 :   if (dump_file && (dump_flags & TDF_DETAILS))
     232              :     {
     233          266 :       fprintf (dump_file, "marking necessary through ");
     234          266 :       print_generic_expr (dump_file, op);
     235          266 :       fprintf (dump_file, " stmt ");
     236          266 :       print_gimple_stmt (dump_file, stmt, 0);
     237              :     }
     238              : 
     239    157034190 :   gimple_set_plf (stmt, STMT_NECESSARY, true);
     240    157034190 :   if (bb_contains_live_stmts)
     241     53824351 :     bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index);
     242    157034190 :   worklist.safe_push (stmt);
     243              : }
     244              : 
     245              : /* Return true if STMT is a call to allocation function that can be
     246              :    optimized out if the memory block is never used for anything else
     247              :    than NULL pointer check or free.
     248              :    If NON_NULL_CHECK is false, we can further assume that return value
     249              :    is never checked to be non-NULL.
     250              :    Don't return true if it is called with constant size (or sizes for calloc)
     251              :    and the size is excessively large (larger than PTRDIFF_MAX, for calloc
     252              :    either argument larger than PTRDIFF_MAX or both constant and their product
     253              :    larger than PTRDIFF_MAX).  */
     254              : 
     255              : static bool
     256     36964070 : is_removable_allocation_p (gcall *stmt, bool non_null_check)
     257              : {
     258     36964070 :   int arg = -1;
     259     36964070 :   tree callee = gimple_call_fndecl (stmt), a1, a2;
     260     36964070 :   if (callee != NULL_TREE
     261     36964070 :       && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
     262      9316902 :     switch (DECL_FUNCTION_CODE (callee))
     263              :       {
     264       617558 :       case BUILT_IN_MALLOC:
     265       617558 :         arg = 1;
     266       617558 :         goto do_malloc;
     267          150 :       case BUILT_IN_ALIGNED_ALLOC:
     268          150 :         arg = 2;
     269          150 :         goto do_malloc;
     270         5883 :       case BUILT_IN_CALLOC:
     271         5883 :         arg = 3;
     272         5883 :         goto do_malloc;
     273       122080 :       CASE_BUILT_IN_ALLOCA:
     274       122080 :         arg = 1;
     275       122080 :         goto do_malloc;
     276              :       case BUILT_IN_STRDUP:
     277              :       case BUILT_IN_STRNDUP:
     278              :         arg = 0;
     279              :         /* FALLTHRU */
     280       749904 :       do_malloc:
     281       749904 :         if (non_null_check)
     282              :           {
     283       128218 :             if (flag_malloc_dce <= 1)
     284              :               return false;
     285              :           }
     286       621686 :         else if (!flag_malloc_dce)
     287              :           return false;
     288              :         break;
     289              : 
     290              :       case BUILT_IN_GOMP_ALLOC:
     291     36963758 :         arg = 2;
     292              :         break;
     293              : 
     294              :       default:;
     295              :       }
     296              : 
     297     36963758 :   if (arg == -1
     298     36963758 :       && callee != NULL_TREE
     299     34029941 :       && flag_allocation_dce
     300     34026497 :       && gimple_call_from_new_or_delete (stmt)
     301     38288320 :       && DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee))
     302              :     arg = 1;
     303              : 
     304     36532484 :   switch (arg)
     305              :     {
     306              :     case -1:
     307              :       return false;
     308              :     case 0:
     309              :       return true;
     310      1176709 :     case 1:
     311      1176709 :     case 2:
     312      1176709 :       if (gimple_call_num_args (stmt) < (unsigned) arg)
     313              :         return false;
     314      1176703 :       a1 = gimple_call_arg (stmt, arg - 1);
     315      1176703 :       if (tree_fits_uhwi_p (a1)
     316      1176703 :           && (tree_to_uhwi (a1)
     317       610729 :               > tree_to_uhwi (TYPE_MAX_VALUE (ptrdiff_type_node))))
     318              :         return false;
     319              :       return true;
     320         5883 :     case 3:
     321         5883 :       if (gimple_call_num_args (stmt) < 2)
     322              :         return false;
     323         5883 :       a1 = gimple_call_arg (stmt, 0);
     324         5883 :       a2 = gimple_call_arg (stmt, 1);
     325         5883 :       if (tree_fits_uhwi_p (a1)
     326         5883 :           && (tree_to_uhwi (a1)
     327         4874 :               > tree_to_uhwi (TYPE_MAX_VALUE (ptrdiff_type_node))))
     328              :         return false;
     329         5861 :       if (tree_fits_uhwi_p (a2)
     330         5861 :           && (tree_to_uhwi (a2)
     331         5133 :               > tree_to_uhwi (TYPE_MAX_VALUE (ptrdiff_type_node))))
     332              :         return false;
     333        11678 :       if (TREE_CODE (a1) == INTEGER_CST
     334         4842 :           && TREE_CODE (a2) == INTEGER_CST
     335        10266 :           && (wi::to_widest (a1) * wi::to_widest (a2)
     336        10266 :               > tree_to_uhwi (TYPE_MAX_VALUE (ptrdiff_type_node))))
     337              :         return false;
     338              :       return true;
     339              :     default:
     340              :       gcc_unreachable ();
     341              :     }
     342              : }
     343              : 
     344              : /* Return true if STMT is an assignment
     345              :      foo = (ptr != NULL)
     346              :      foo = (ptr == NULL)
     347              :    or a conditional
     348              :      if (ptr != NULL)
     349              :      if (ptr == NULL)
     350              :    where ptr was returned by a removable allocation function.  */
     351              : 
     352              : static bool
     353    247823447 : checks_return_value_of_removable_allocation_p (gimple *stmt)
     354              : {
     355    247823447 :   enum tree_code code;
     356    247823447 :   tree ptr, value;
     357              : 
     358    247823447 :   if (gassign *assign = dyn_cast <gassign *> (stmt))
     359              :     {
     360    167139313 :       code = gimple_assign_rhs_code (assign);
     361    167139313 :       ptr = gimple_assign_rhs1 (assign);
     362    167139313 :       value = gimple_assign_rhs2 (assign);
     363              :     }
     364    279569513 :   else if (gcond *cond = dyn_cast <gcond *> (stmt))
     365              :     {
     366     31875587 :       code = gimple_cond_code (cond);
     367     31875587 :       ptr = gimple_cond_lhs (cond);
     368     31875587 :       value = gimple_cond_rhs (cond);
     369              :     }
     370              :   else
     371              :     return false;
     372              : 
     373    199014900 :   if (code != EQ_EXPR && code != NE_EXPR)
     374              :     return false;
     375              : 
     376     26071376 :   if (!integer_zerop (value) || TREE_CODE (ptr) != SSA_NAME)
     377              :     return false;
     378              : 
     379     14035886 :   gcall *def_stmt = dyn_cast <gcall *> (SSA_NAME_DEF_STMT (ptr));
     380      3509997 :   return def_stmt && is_removable_allocation_p (def_stmt, true);
     381              : }
     382              : 
     383              : 
     384              : /* Mark STMT as necessary if it obviously is.  Add it to the worklist if
     385              :    it can make other statements necessary.
     386              : 
     387              :    If AGGRESSIVE is false, control statements are conservatively marked as
     388              :    necessary.  */
     389              : 
     390              : static void
     391    640473936 : mark_stmt_if_obviously_necessary (gimple *stmt, bool aggressive)
     392              : {
     393              :   /* Statements that are implicitly live.  Most function calls, asm
     394              :      and return statements are required.  Labels and GIMPLE_BIND nodes
     395              :      are kept because they are control flow, and we have no way of
     396              :      knowing whether they can be removed.  DCE can eliminate all the
     397              :      other statements in a block, and CFG can then remove the block
     398              :      and labels.  */
     399    640473936 :   switch (gimple_code (stmt))
     400              :     {
     401      7056783 :     case GIMPLE_PREDICT:
     402      7056783 :     case GIMPLE_LABEL:
     403      7056783 :       mark_stmt_necessary (stmt, false);
     404      7056783 :       return;
     405              : 
     406     10356842 :     case GIMPLE_ASM:
     407     10356842 :     case GIMPLE_RESX:
     408     10356842 :     case GIMPLE_RETURN:
     409     10356842 :       mark_stmt_necessary (stmt, true);
     410     10356842 :       return;
     411              : 
     412     38477604 :     case GIMPLE_CALL:
     413     38477604 :       {
     414     38477604 :         gcall *call = as_a <gcall *> (stmt);
     415              : 
     416              :         /* Never elide a noreturn call we pruned control-flow for.
     417              :            Same for statements that can alter control flow in unpredictable
     418              :            ways.  */
     419     38477604 :         if (gimple_call_ctrl_altering_p (call))
     420              :           {
     421      5320334 :             mark_stmt_necessary (call, true);
     422      5320334 :             return;
     423              :           }
     424              : 
     425     33157270 :         if (is_removable_allocation_p (call, false))
     426              :           return;
     427              : 
     428              : 
     429              :         /* For __cxa_atexit calls, don't mark as necessary right away. */
     430     32295350 :         if (is_removable_cxa_atexit_call (call))
     431              :           return;
     432              : 
     433              :         /* A relaxed atomic load with no LHS has no observable effect:
     434              :            the value is discarded and relaxed ordering provides no
     435              :            inter-thread synchronisation guarantee.  Don't mark it
     436              :            necessary so DCE can remove it. */
     437     32294861 :         if (gimple_call_builtin_p (call, BUILT_IN_NORMAL))
     438      6447331 :           switch (DECL_FUNCTION_CODE (gimple_call_fndecl (call)))
     439              :             {
     440       429378 :             case BUILT_IN_ATOMIC_LOAD_1:
     441       429378 :             case BUILT_IN_ATOMIC_LOAD_2:
     442       429378 :             case BUILT_IN_ATOMIC_LOAD_4:
     443       429378 :             case BUILT_IN_ATOMIC_LOAD_8:
     444       429378 :             case BUILT_IN_ATOMIC_LOAD_16:
     445       429378 :               {
     446       429378 :               tree model_arg = gimple_call_arg (call, 1);
     447       429378 :               if (TREE_CODE (model_arg) == INTEGER_CST
     448       429378 :                   && is_mm_relaxed (memmodel_from_int (tree_to_uhwi (model_arg))))
     449              :                 return;
     450              :               break;
     451              :               }
     452              :             default:
     453              :               break;
     454              :             }
     455              : 
     456              :         /* IFN_GOACC_LOOP calls are necessary in that they are used to
     457              :            represent parameter (i.e. step, bound) of a lowered OpenACC
     458              :            partitioned loop.  But this kind of partitioned loop might not
     459              :            survive from aggressive loop removal for it has loop exit and
     460              :            is assumed to be finite.  Therefore, we need to explicitly mark
     461              :            these calls. (An example is libgomp.oacc-c-c++-common/pr84955.c) */
     462     32199756 :         if (gimple_call_internal_p (call, IFN_GOACC_LOOP))
     463              :           {
     464        27733 :             mark_stmt_necessary (call, true);
     465        27733 :             return;
     466              :           }
     467              :         break;
     468              :       }
     469              : 
     470    383215174 :     case GIMPLE_DEBUG:
     471              :       /* Debug temps without a value are not useful.  ??? If we could
     472              :          easily locate the debug temp bind stmt for a use thereof,
     473              :          would could refrain from marking all debug temps here, and
     474              :          mark them only if they're used.  */
     475    383215174 :       if (gimple_debug_nonbind_marker_p (stmt)
     476    298644628 :           || !gimple_debug_bind_p (stmt)
     477    297586066 :           || gimple_debug_bind_has_value_p (stmt)
     478    516961490 :           || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL)
     479    382817147 :         mark_stmt_necessary (stmt, false);
     480              :       return;
     481              : 
     482         1970 :     case GIMPLE_GOTO:
     483         1970 :       gcc_assert (!simple_goto_p (stmt));
     484         1970 :       mark_stmt_necessary (stmt, true);
     485         1970 :       return;
     486              : 
     487     31912017 :     case GIMPLE_COND:
     488     31912017 :       gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
     489              :       /* Fall through.  */
     490              : 
     491     32075907 :     case GIMPLE_SWITCH:
     492     32075907 :       if (! aggressive)
     493     21227726 :         mark_stmt_necessary (stmt, true);
     494              :       break;
     495              : 
     496    169249102 :     case GIMPLE_ASSIGN:
     497              :       /* Mark indirect CLOBBERs to be lazily removed if their SSA operands
     498              :          do not prevail.  That also makes control flow leading to them
     499              :          not necessary in aggressive mode.  */
     500    180230403 :       if (gimple_clobber_p (stmt) && !zero_ssa_operands (stmt, SSA_OP_USE))
     501              :         return;
     502              :       break;
     503              : 
     504              :     default:
     505              :       break;
     506              :     }
     507              : 
     508              :   /* If the statement has volatile operands, it needs to be preserved.
     509              :      Same for statements that can alter control flow in unpredictable
     510              :      ways.  */
     511    232659226 :   if (gimple_has_side_effects (stmt) || is_ctrl_altering_stmt (stmt))
     512              :     {
     513     42586439 :       mark_stmt_necessary (stmt, true);
     514     42586439 :       return;
     515              :     }
     516              : 
     517              :   /* If a statement could throw, it can be deemed necessary unless we
     518              :      are allowed to remove dead EH.  Test this after checking for
     519              :      new/delete operators since we always elide their EH.  */
     520    190072787 :   if (!cfun->can_delete_dead_exceptions
     521    190072787 :       && stmt_could_throw_p (cfun, stmt))
     522              :     {
     523      5816487 :       mark_stmt_necessary (stmt, true);
     524      5816487 :       return;
     525              :     }
     526              : 
     527    229794619 :   if ((gimple_vdef (stmt) && keep_all_vdefs_p ())
     528    229775871 :       || stmt_may_clobber_global_p (stmt, false))
     529              :     {
     530     14114217 :       mark_stmt_necessary (stmt, true);
     531     14114217 :       return;
     532              :     }
     533              : 
     534              :   return;
     535              : }
     536              : 
     537              : 
     538              : /* Mark the last statement of BB as necessary.  */
     539              : 
     540              : static bool
     541     43884568 : mark_last_stmt_necessary (basic_block bb)
     542              : {
     543     43884568 :   if (!bitmap_set_bit (last_stmt_necessary, bb->index))
     544              :     return true;
     545              : 
     546     17309500 :   bitmap_set_bit (bb_contains_live_stmts, bb->index);
     547              : 
     548              :   /* We actually mark the statement only if it is a control statement.  */
     549     17309500 :   gimple *stmt = *gsi_last_bb (bb);
     550     17309500 :   if (stmt && is_ctrl_stmt (stmt))
     551              :     {
     552     10809022 :       mark_stmt_necessary (stmt, true);
     553     10809022 :       return true;
     554              :     }
     555              :   return false;
     556              : }
     557              : 
     558              : 
     559              : /* Mark control dependent edges of BB as necessary.  We have to do this only
     560              :    once for each basic block so we set the appropriate bit after we're done.
     561              : 
     562              :    When IGNORE_SELF is true, ignore BB in the list of control dependences.  */
     563              : 
     564              : static void
     565     32783389 : mark_control_dependent_edges_necessary (basic_block bb, bool ignore_self)
     566              : {
     567     32783389 :   bitmap_iterator bi;
     568     32783389 :   unsigned edge_number;
     569     32783389 :   bool skipped = false;
     570              : 
     571     32783389 :   gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
     572              : 
     573     32783389 :   if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     574      3626874 :     return;
     575              : 
     576     71660037 :   EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
     577              :                             0, edge_number, bi)
     578              :     {
     579     42503522 :       basic_block cd_bb = cd->get_edge_src (edge_number);
     580              : 
     581     42503522 :       if (ignore_self && cd_bb == bb)
     582              :         {
     583        75560 :           skipped = true;
     584        75560 :           continue;
     585              :         }
     586              : 
     587     42427962 :       if (!mark_last_stmt_necessary (cd_bb))
     588      6497946 :         mark_control_dependent_edges_necessary (cd_bb, false);
     589              :     }
     590              : 
     591     29156515 :   if (!skipped)
     592     29080955 :     bitmap_set_bit (visited_control_parents, bb->index);
     593              : }
     594              : 
     595              : 
     596              : /* Find obviously necessary statements.  These are things like most function
     597              :    calls, and stores to file level variables.
     598              : 
     599              :    If EL is NULL, control statements are conservatively marked as
     600              :    necessary.  Otherwise it contains the list of edges used by control
     601              :    dependence analysis.  */
     602              : 
     603              : static void
     604      8302670 : find_obviously_necessary_stmts (bool aggressive)
     605              : {
     606      8302670 :   basic_block bb;
     607      8302670 :   gimple_stmt_iterator gsi;
     608      8302670 :   edge e;
     609      8302670 :   gimple *phi, *stmt;
     610      8302670 :   int flags;
     611              : 
     612     92466678 :   FOR_EACH_BB_FN (bb, cfun)
     613              :     {
     614              :       /* PHI nodes are never inherently necessary.  */
     615    119664629 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     616              :         {
     617     35500621 :           phi = gsi_stmt (gsi);
     618     35500621 :           gimple_set_plf (phi, STMT_NECESSARY, false);
     619              :         }
     620              : 
     621              :       /* Check all statements in the block.  */
     622    808801952 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     623              :         {
     624    640473936 :           stmt = gsi_stmt (gsi);
     625    640473936 :           gimple_set_plf (stmt, STMT_NECESSARY, false);
     626    640473936 :           mark_stmt_if_obviously_necessary (stmt, aggressive);
     627              :         }
     628              :     }
     629              : 
     630              :   /* Pure and const functions are finite and thus have no infinite loops in
     631              :      them.  */
     632      8302670 :   flags = flags_from_decl_or_type (current_function_decl);
     633      8302670 :   if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
     634       973802 :     return;
     635              : 
     636              :   /* Prevent the empty possibly infinite loops from being removed.  This is
     637              :      needed to make the logic in remove_dead_stmt work to identify the
     638              :      correct edge to keep when removing a controlling condition.  */
     639      7328868 :   if (aggressive)
     640              :     {
     641      3433596 :       if (mark_irreducible_loops ())
     642       334248 :         FOR_EACH_BB_FN (bb, cfun)
     643              :           {
     644       327800 :             edge_iterator ei;
     645       814871 :             FOR_EACH_EDGE (e, ei, bb->succs)
     646       487071 :               if ((e->flags & EDGE_DFS_BACK)
     647        36641 :                   && (e->flags & EDGE_IRREDUCIBLE_LOOP))
     648              :                 {
     649        12387 :                   if (dump_file)
     650            0 :                     fprintf (dump_file, "Marking back edge of irreducible "
     651            0 :                              "loop %i->%i\n", e->src->index, e->dest->index);
     652        12387 :                   mark_control_dependent_edges_necessary (e->dest, false);
     653              :                 }
     654              :           }
     655              : 
     656     12138535 :       for (auto loop : loops_list (cfun, 0))
     657              :         /* For loops without an exit do not mark any condition.  */
     658      1837747 :         if (loop->exits->next->e && !finite_loop_p (loop))
     659              :           {
     660       281180 :             if (dump_file)
     661            1 :               fprintf (dump_file, "cannot prove finiteness of loop %i\n",
     662              :                        loop->num);
     663       281180 :             mark_control_dependent_edges_necessary (loop->latch, false);
     664      3433596 :           }
     665              :     }
     666              : }
     667              : 
     668              : 
     669              : /* Return true if REF is based on an aliased base, otherwise false.  */
     670              : 
     671              : static bool
     672    100312360 : ref_may_be_aliased (tree ref)
     673              : {
     674    100312360 :   if (TREE_CODE (ref) == WITH_SIZE_EXPR)
     675            0 :     ref = TREE_OPERAND (ref, 0);
     676    180011656 :   while (handled_component_p (ref))
     677     79699296 :     ref = TREE_OPERAND (ref, 0);
     678    100312360 :   if ((TREE_CODE (ref) == MEM_REF || TREE_CODE (ref) == TARGET_MEM_REF)
     679    100312360 :       && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR)
     680     16078859 :     ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
     681    100312360 :   return !(DECL_P (ref)
     682     66923201 :            && !may_be_aliased (ref));
     683              : }
     684              : 
     685              : static bitmap visited = NULL;
     686              : static unsigned int longest_chain = 0;
     687              : static unsigned int total_chain = 0;
     688              : static unsigned int nr_walks = 0;
     689              : static bool chain_ovfl = false;
     690              : 
     691              : /* Worker for the walker that marks reaching definitions of REF,
     692              :    which is based on a non-aliased decl, necessary.  It returns
     693              :    true whenever the defining statement of the current VDEF is
     694              :    a kill for REF, as no dominating may-defs are necessary for REF
     695              :    anymore.  DATA points to the basic-block that contains the
     696              :    stmt that refers to REF.  */
     697              : 
     698              : static bool
     699     40657746 : mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
     700              : {
     701     40657746 :   gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
     702              : 
     703              :   /* All stmts we visit are necessary.  */
     704     40657746 :   if (! gimple_clobber_p (def_stmt))
     705     40448659 :     mark_operand_necessary (vdef);
     706              : 
     707              :   /* If the stmt lhs kills ref, then we can stop walking.  */
     708     40657746 :   if (gimple_has_lhs (def_stmt)
     709     29461891 :       && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME
     710              :       /* The assignment is not necessarily carried out if it can throw
     711              :          and we can catch it in the current function where we could inspect
     712              :          the previous value.
     713              :          ???  We only need to care about the RHS throwing.  For aggregate
     714              :          assignments or similar calls and non-call exceptions the LHS
     715              :          might throw as well.  */
     716     38489239 :       && !stmt_can_throw_internal (cfun, def_stmt))
     717              :     {
     718     25161444 :       tree base, lhs = gimple_get_lhs (def_stmt);
     719     25161444 :       poly_int64 size, offset, max_size;
     720     25161444 :       bool reverse;
     721     25161444 :       ao_ref_base (ref);
     722     25161444 :       base
     723     25161444 :         = get_ref_base_and_extent (lhs, &offset, &size, &max_size, &reverse);
     724              :       /* We can get MEM[symbol: sZ, index: D.8862_1] here,
     725              :          so base == refd->base does not always hold.  */
     726     25161444 :       if (base == ref->base)
     727              :         {
     728              :           /* For a must-alias check we need to be able to constrain
     729              :              the accesses properly.  */
     730     23101842 :           if (known_eq (size, max_size)
     731     23101842 :               && known_subrange_p (ref->offset, ref->max_size, offset, size))
     732      8702080 :             return true;
     733              :           /* Or they need to be exactly the same.  */
     734     14400410 :           else if (ref->ref
     735              :                    /* Make sure there is no induction variable involved
     736              :                       in the references (gcc.c-torture/execute/pr42142.c).
     737              :                       The simplest way is to check if the kill dominates
     738              :                       the use.  */
     739              :                    /* But when both are in the same block we cannot
     740              :                       easily tell whether we came from a backedge
     741              :                       unless we decide to compute stmt UIDs
     742              :                       (see PR58246).  */
     743     14400410 :                    && (basic_block) data != gimple_bb (def_stmt)
     744      6785567 :                    && dominated_by_p (CDI_DOMINATORS, (basic_block) data,
     745      6785567 :                                       gimple_bb (def_stmt))
     746     18608479 :                    && operand_equal_p (ref->ref, lhs, 0))
     747              :             return true;
     748              :         }
     749              :     }
     750              : 
     751              :   /* Otherwise keep walking.  */
     752              :   return false;
     753              : }
     754              : 
     755              : static void
     756     13677479 : mark_aliased_reaching_defs_necessary (gimple *stmt, tree ref)
     757              : {
     758              :   /* Should have been caught before calling this function.  */
     759     13677479 :   gcc_checking_assert (!keep_all_vdefs_p ());
     760              : 
     761     13677479 :   unsigned int chain;
     762     13677479 :   ao_ref refd;
     763     13677479 :   gcc_assert (!chain_ovfl);
     764     13677479 :   ao_ref_init (&refd, ref);
     765     27354958 :   chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt),
     766              :                               mark_aliased_reaching_defs_necessary_1,
     767     13677479 :                               gimple_bb (stmt), NULL);
     768     13677479 :   if (chain > longest_chain)
     769      2286840 :     longest_chain = chain;
     770     13677479 :   total_chain += chain;
     771     13677479 :   nr_walks++;
     772     13677479 : }
     773              : 
     774              : /* Worker for the walker that marks reaching definitions of REF, which
     775              :    is not based on a non-aliased decl.  For simplicity we need to end
     776              :    up marking all may-defs necessary that are not based on a non-aliased
     777              :    decl.  The only job of this walker is to skip may-defs based on
     778              :    a non-aliased decl.  */
     779              : 
     780              : static bool
     781     77903440 : mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED,
     782              :                                     tree vdef, void *data ATTRIBUTE_UNUSED)
     783              : {
     784     77903440 :   gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
     785              : 
     786              :   /* We have to skip already visited (and thus necessary) statements
     787              :      to make the chaining work after we dropped back to simple mode.  */
     788     77903440 :   if (chain_ovfl
     789     77903440 :       && bitmap_bit_p (processed, SSA_NAME_VERSION (vdef)))
     790              :     {
     791      2533420 :       gcc_assert (gimple_nop_p (def_stmt)
     792              :                   || gimple_plf (def_stmt, STMT_NECESSARY));
     793              :       return false;
     794              :     }
     795              : 
     796              :   /* We want to skip stores to non-aliased variables.  */
     797     75370020 :   if (!chain_ovfl
     798     75370020 :       && gimple_assign_single_p (def_stmt))
     799              :     {
     800     50440842 :       tree lhs = gimple_assign_lhs (def_stmt);
     801     50440842 :       if (!ref_may_be_aliased (lhs))
     802              :         return false;
     803              :     }
     804              : 
     805              :   /* We want to skip statements that do not constitute stores but have
     806              :      a virtual definition.  */
     807     62859946 :   if (gcall *call = dyn_cast <gcall *> (def_stmt))
     808              :     {
     809     24089289 :       tree callee = gimple_call_fndecl (call);
     810     24089289 :       if (callee != NULL_TREE
     811     24089289 :           && fndecl_built_in_p (callee, BUILT_IN_NORMAL))
     812      4202931 :         switch (DECL_FUNCTION_CODE (callee))
     813              :           {
     814              :           case BUILT_IN_MALLOC:
     815              :           case BUILT_IN_ALIGNED_ALLOC:
     816              :           case BUILT_IN_CALLOC:
     817              :           CASE_BUILT_IN_ALLOCA:
     818              :           case BUILT_IN_STRDUP:
     819              :           case BUILT_IN_STRNDUP:
     820              :           case BUILT_IN_FREE:
     821              :           case BUILT_IN_GOMP_ALLOC:
     822              :           case BUILT_IN_GOMP_FREE:
     823              :             return false;
     824              : 
     825              :           default:;
     826              :           }
     827              : 
     828     23378867 :       if (callee != NULL_TREE
     829     22087738 :           && (DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee)
     830     21735186 :               || DECL_IS_OPERATOR_DELETE_P (callee))
     831     24339603 :           && gimple_call_from_new_or_delete (call))
     832              :         return false;
     833     22425298 :       if (is_removable_cxa_atexit_call (call))
     834              :         return false;
     835              :     }
     836              : 
     837     61195697 :   if (! gimple_clobber_p (def_stmt))
     838     55927952 :     mark_operand_necessary (vdef);
     839              : 
     840              :   return false;
     841              : }
     842              : 
     843              : static void
     844     72044454 : mark_all_reaching_defs_necessary (gimple *stmt)
     845              : {
     846              :   /* Should have been caught before calling this function.  */
     847     72044454 :   gcc_checking_assert (!keep_all_vdefs_p ());
     848    144088908 :   walk_aliased_vdefs (NULL, gimple_vuse (stmt),
     849              :                       mark_all_reaching_defs_necessary_1, NULL, &visited);
     850     72044454 : }
     851              : 
     852              : /* Return true for PHI nodes with one or identical arguments
     853              :    can be removed.  */
     854              : static bool
     855     18813878 : degenerate_phi_p (gimple *phi)
     856              : {
     857     18813878 :   unsigned int i;
     858     18813878 :   tree op = gimple_phi_arg_def (phi, 0);
     859     19589068 :   for (i = 1; i < gimple_phi_num_args (phi); i++)
     860     17722534 :     if (gimple_phi_arg_def (phi, i) != op)
     861              :       return false;
     862              :   return true;
     863              : }
     864              : 
     865              : /* Return that NEW_CALL and DELETE_CALL are a valid pair of new
     866              :    and delete  operators.  */
     867              : 
     868              : static bool
     869        56347 : valid_new_delete_pair_p (gimple *new_call, gimple *delete_call)
     870              : {
     871        56347 :   tree new_asm = DECL_ASSEMBLER_NAME (gimple_call_fndecl (new_call));
     872        56347 :   tree delete_asm = DECL_ASSEMBLER_NAME (gimple_call_fndecl (delete_call));
     873        56347 :   return valid_new_delete_pair_p (new_asm, delete_asm);
     874              : }
     875              : 
     876              : /* Propagate necessity using the operands of necessary statements.
     877              :    Process the uses on each statement in the worklist, and add all
     878              :    feeding statements which contribute to the calculation of this
     879              :    value to the worklist.
     880              : 
     881              :    In conservative mode, EL is NULL.  */
     882              : 
     883              : static void
     884      8302670 : propagate_necessity (bool aggressive)
     885              : {
     886      8302670 :   gimple *stmt;
     887              : 
     888      8302670 :   if (dump_file && (dump_flags & TDF_DETAILS))
     889          208 :     fprintf (dump_file, "\nProcessing worklist:\n");
     890              : 
     891    275597430 :   while (worklist.length () > 0)
     892              :     {
     893              :       /* Take STMT from worklist.  */
     894    267294760 :       stmt = worklist.pop ();
     895              : 
     896    267294760 :       if (dump_file && (dump_flags & TDF_DETAILS))
     897              :         {
     898         1099 :           fprintf (dump_file, "processing: ");
     899         1099 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
     900         1099 :           fprintf (dump_file, "\n");
     901              :         }
     902              : 
     903    267294760 :       if (aggressive)
     904              :         {
     905              :           /* Mark the last statement of the basic blocks on which the block
     906              :              containing STMT is control dependent, but only if we haven't
     907              :              already done so.  */
     908     92522074 :           basic_block bb = gimple_bb (stmt);
     909     92522074 :           if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     910     92522074 :               && !bitmap_bit_p (visited_control_parents, bb->index))
     911     19463778 :             mark_control_dependent_edges_necessary (bb, false);
     912              :         }
     913              : 
     914    267294760 :       if (gimple_code (stmt) == GIMPLE_PHI
     915              :           /* We do not process virtual PHI nodes nor do we track their
     916              :              necessity.  */
     917    305856210 :           && !virtual_operand_p (gimple_phi_result (stmt)))
     918              :         {
     919              :           /* PHI nodes are somewhat special in that each PHI alternative has
     920              :              data and control dependencies.  All the statements feeding the
     921              :              PHI node's arguments are always necessary.  In aggressive mode,
     922              :              we also consider the control dependent edges leading to the
     923              :              predecessor block associated with each PHI alternative as
     924              :              necessary.  */
     925     19280725 :           gphi *phi = as_a <gphi *> (stmt);
     926     19280725 :           size_t k;
     927              : 
     928     83990766 :           for (k = 0; k < gimple_phi_num_args (stmt); k++)
     929              :             {
     930     45429316 :               tree arg = PHI_ARG_DEF (stmt, k);
     931     45429316 :               if (TREE_CODE (arg) == SSA_NAME)
     932     33504554 :                 mark_operand_necessary (arg);
     933              :             }
     934              : 
     935              :           /* For PHI operands it matters from where the control flow arrives
     936              :              to the BB.  Consider the following example:
     937              : 
     938              :              a=exp1;
     939              :              b=exp2;
     940              :              if (test)
     941              :                 ;
     942              :              else
     943              :                 ;
     944              :              c=PHI(a,b)
     945              : 
     946              :              We need to mark control dependence of the empty basic blocks, since they
     947              :              contains computation of PHI operands.
     948              : 
     949              :              Doing so is too restrictive in the case the predecestor block is in
     950              :              the loop. Consider:
     951              : 
     952              :               if (b)
     953              :                 {
     954              :                   int i;
     955              :                   for (i = 0; i<1000; ++i)
     956              :                     ;
     957              :                   j = 0;
     958              :                 }
     959              :               return j;
     960              : 
     961              :              There is PHI for J in the BB containing return statement.
     962              :              In this case the control dependence of predecestor block (that is
     963              :              within the empty loop) also contains the block determining number
     964              :              of iterations of the block that would prevent removing of empty
     965              :              loop in this case.
     966              : 
     967              :              This scenario can be avoided by splitting critical edges.
     968              :              To save the critical edge splitting pass we identify how the control
     969              :              dependence would look like if the edge was split.
     970              : 
     971              :              Consider the modified CFG created from current CFG by splitting
     972              :              edge B->C.  In the postdominance tree of modified CFG, C' is
     973              :              always child of C.  There are two cases how children of C' can look
     974              :              like:
     975              : 
     976              :                 1) C' is leaf
     977              : 
     978              :                    In this case the only basic block C' is control dependent on is B.
     979              : 
     980              :                 2) C' has single child that is B
     981              : 
     982              :                    In this case control dependence of C' is same as control
     983              :                    dependence of B in original CFG except for block B itself.
     984              :                    (since C' postdominate B in modified CFG)
     985              : 
     986              :              Now how to decide what case happens?  There are two basic options:
     987              : 
     988              :                 a) C postdominate B.  Then C immediately postdominate B and
     989              :                    case 2 happens iff there is no other way from B to C except
     990              :                    the edge B->C.
     991              : 
     992              :                    There is other way from B to C iff there is successor of B that
     993              :                    is not postdominated by B.  Testing this condition is somewhat
     994              :                    expensive, because we need to iterate all successors of B.
     995              :                    We are safe to assume that this does not happen: we will mark B
     996              :                    as needed when processing the other path from B to C that is
     997              :                    control dependent on B and marking control dependencies of B
     998              :                    itself is harmless because they will be processed anyway after
     999              :                    processing control statement in B.
    1000              : 
    1001              :                 b) C does not postdominate B.  Always case 1 happens since there is
    1002              :                    path from C to exit that does not go through B and thus also C'.  */
    1003              : 
    1004     32403964 :           if (aggressive && !degenerate_phi_p (stmt))
    1005              :             {
    1006     20569939 :               for (k = 0; k < gimple_phi_num_args (stmt); k++)
    1007              :                 {
    1008     14412453 :                   basic_block arg_bb = gimple_phi_arg_edge (phi, k)->src;
    1009              : 
    1010     14412453 :                   if (gimple_bb (stmt)
    1011     14412453 :                       != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb))
    1012              :                     {
    1013      1456606 :                       if (!mark_last_stmt_necessary (arg_bb))
    1014         2532 :                         mark_control_dependent_edges_necessary (arg_bb, false);
    1015              :                     }
    1016     12955847 :                   else if (arg_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
    1017     12955847 :                            && !bitmap_bit_p (visited_control_parents,
    1018              :                                          arg_bb->index))
    1019      6525566 :                     mark_control_dependent_edges_necessary (arg_bb, true);
    1020              :                 }
    1021              :             }
    1022              :         }
    1023              :       else
    1024              :         {
    1025              :           /* Propagate through the operands.  Examine all the USE, VUSE and
    1026              :              VDEF operands in this statement.  Mark all the statements
    1027              :              which feed this statement's uses as necessary.  */
    1028    248014035 :           ssa_op_iter iter;
    1029    248014035 :           tree use;
    1030              : 
    1031              :           /* If this is a call to free which is directly fed by an
    1032              :              allocation function do not mark that necessary through
    1033              :              processing the argument.  */
    1034    248014035 :           bool is_delete_operator
    1035    248014035 :             = (is_gimple_call (stmt)
    1036     38442837 :                && gimple_call_from_new_or_delete (as_a <gcall *> (stmt))
    1037    249280124 :                && gimple_call_operator_delete_p (as_a <gcall *> (stmt)));
    1038    247121163 :           if (is_delete_operator
    1039    247121163 :               || gimple_call_builtin_p (stmt, BUILT_IN_FREE)
    1040    246782758 :               || gimple_call_builtin_p (stmt, BUILT_IN_GOMP_FREE))
    1041              :             {
    1042      1231277 :               tree ptr = gimple_call_arg (stmt, 0);
    1043      1231277 :               gcall *def_stmt;
    1044              :               /* If the pointer we free is defined by an allocation
    1045              :                  function do not add the call to the worklist.  */
    1046      1231277 :               if (TREE_CODE (ptr) == SSA_NAME
    1047      1229916 :                   && (def_stmt = dyn_cast <gcall *> (SSA_NAME_DEF_STMT (ptr)))
    1048      1449329 :                   && is_removable_allocation_p (def_stmt, false))
    1049              :                 {
    1050       194991 :                   if (is_delete_operator
    1051       194991 :                       && !valid_new_delete_pair_p (def_stmt, stmt))
    1052          143 :                     mark_operand_necessary (gimple_call_arg (stmt, 0));
    1053              : 
    1054              :                   /* Delete operators can have alignment and (or) size
    1055              :                      as next arguments.  When being a SSA_NAME, they
    1056              :                      must be marked as necessary.  Similarly GOMP_free.  */
    1057       194991 :                   if (gimple_call_num_args (stmt) >= 2)
    1058       102064 :                     for (unsigned i = 1; i < gimple_call_num_args (stmt);
    1059              :                          i++)
    1060              :                       {
    1061        51083 :                         tree arg = gimple_call_arg (stmt, i);
    1062        51083 :                         if (TREE_CODE (arg) == SSA_NAME)
    1063         8791 :                           mark_operand_necessary (arg);
    1064              :                       }
    1065              : 
    1066    108187709 :                   continue;
    1067       194991 :                 }
    1068              :             }
    1069              : 
    1070    247819044 :           if (checks_return_value_of_removable_allocation_p (stmt))
    1071       125118 :             continue;
    1072              : 
    1073    464317296 :           FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
    1074    216623370 :             mark_operand_necessary (use);
    1075              : 
    1076    247693926 :           use = gimple_vuse (stmt);
    1077    214032907 :           if (!use)
    1078    101579394 :             continue;
    1079              : 
    1080              :           /* No need to search for vdefs if we intrinsicly keep them all.  */
    1081    146114532 :           if (keep_all_vdefs_p ())
    1082        68207 :             continue;
    1083              : 
    1084              :           /* If we dropped to simple mode make all immediately
    1085              :              reachable definitions necessary.  */
    1086    146046325 :           if (chain_ovfl)
    1087              :             {
    1088      3665032 :               mark_all_reaching_defs_necessary (stmt);
    1089      3665032 :               continue;
    1090              :             }
    1091              : 
    1092              :           /* For statements that may load from memory (have a VUSE) we
    1093              :              have to mark all reaching (may-)definitions as necessary.
    1094              :              We partition this task into two cases:
    1095              :               1) explicit loads based on decls that are not aliased
    1096              :               2) implicit loads (like calls) and explicit loads not
    1097              :                  based on decls that are not aliased (like indirect
    1098              :                  references or loads from globals)
    1099              :              For 1) we mark all reaching may-defs as necessary, stopping
    1100              :              at dominating kills.  For 2) we want to mark all dominating
    1101              :              references necessary, but non-aliased ones which we handle
    1102              :              in 1).  By keeping a global visited bitmap for references
    1103              :              we walk for 2) we avoid quadratic behavior for those.  */
    1104              : 
    1105    142381293 :           if (gcall *call = dyn_cast <gcall *> (stmt))
    1106              :             {
    1107     35025155 :               tree callee = gimple_call_fndecl (call);
    1108     35025155 :               unsigned i;
    1109              : 
    1110     36233894 :               if (callee != NULL_TREE
    1111     33433289 :                   && (DECL_IS_REPLACEABLE_OPERATOR_NEW_P (callee)
    1112     33055688 :                       || DECL_IS_OPERATOR_DELETE_P (callee))
    1113     36246600 :                   && gimple_call_from_new_or_delete (call))
    1114      1208739 :                 continue;
    1115              : 
    1116     33816416 :               if (is_removable_cxa_atexit_call (call))
    1117            0 :                 continue;
    1118              : 
    1119              :               bool all_refs = false;
    1120              :               /* Calls implicitly load from memory, their arguments
    1121              :                  in addition may explicitly perform memory loads.  */
    1122    103631470 :               for (i = 0; i < gimple_call_num_args (call); ++i)
    1123              :                 {
    1124     69815054 :                   tree arg = gimple_call_arg (call, i);
    1125    135451170 :                   if (TREE_CODE (arg) == SSA_NAME
    1126     69815054 :                       || is_gimple_min_invariant (arg))
    1127     65636116 :                     continue;
    1128      4178938 :                   if (TREE_CODE (arg) == WITH_SIZE_EXPR)
    1129          664 :                     arg = TREE_OPERAND (arg, 0);
    1130      4178938 :                   if (!ref_may_be_aliased (arg))
    1131      3771187 :                     mark_aliased_reaching_defs_necessary (call, arg);
    1132              :                   else
    1133              :                     all_refs = true;
    1134              :                 }
    1135              : 
    1136     33816416 :               if (!all_refs && ipa_modref_callee_reads_no_memory_p (call))
    1137      1346228 :                 continue;
    1138     32470188 :               mark_all_reaching_defs_necessary (call);
    1139              :             }
    1140    107356138 :           else if (gimple_assign_single_p (stmt))
    1141              :             {
    1142     99064379 :               tree rhs;
    1143              :               /* If this is a load mark things necessary.  */
    1144     99064379 :               rhs = gimple_assign_rhs1 (stmt);
    1145     99064379 :               if (TREE_CODE (rhs) != SSA_NAME
    1146     80444199 :                   && !is_gimple_min_invariant (rhs)
    1147    154834448 :                   && TREE_CODE (rhs) != CONSTRUCTOR)
    1148              :                 {
    1149     44947594 :                   if (!ref_may_be_aliased (rhs))
    1150      9231893 :                     mark_aliased_reaching_defs_necessary (stmt, rhs);
    1151              :                   else
    1152     35715701 :                     mark_all_reaching_defs_necessary (stmt);
    1153              :                 }
    1154              :             }
    1155      8291759 :           else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
    1156              :             {
    1157      8123224 :               tree rhs = gimple_return_retval (return_stmt);
    1158              :               /* A return statement may perform a load.  */
    1159      8123224 :               if (rhs
    1160      4489408 :                   && TREE_CODE (rhs) != SSA_NAME
    1161      1454600 :                   && !is_gimple_min_invariant (rhs)
    1162      8816830 :                   && TREE_CODE (rhs) != CONSTRUCTOR)
    1163              :                 {
    1164       693606 :                   if (!ref_may_be_aliased (rhs))
    1165       668608 :                     mark_aliased_reaching_defs_necessary (stmt, rhs);
    1166              :                   else
    1167        24998 :                     mark_all_reaching_defs_necessary (stmt);
    1168              :                 }
    1169              :             }
    1170       168535 :           else if (gasm *asm_stmt = dyn_cast <gasm *> (stmt))
    1171              :             {
    1172       167351 :               unsigned i;
    1173       167351 :               mark_all_reaching_defs_necessary (stmt);
    1174              :               /* Inputs may perform loads.  */
    1175       478753 :               for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i)
    1176              :                 {
    1177       144051 :                   tree op = TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
    1178       144051 :                   if (TREE_CODE (op) != SSA_NAME
    1179        90261 :                       && !is_gimple_min_invariant (op)
    1180        51380 :                       && TREE_CODE (op) != CONSTRUCTOR
    1181       195431 :                       && !ref_may_be_aliased (op))
    1182         5791 :                     mark_aliased_reaching_defs_necessary (stmt, op);
    1183              :                 }
    1184              :             }
    1185         1184 :           else if (gimple_code (stmt) == GIMPLE_TRANSACTION)
    1186              :             {
    1187              :               /* The beginning of a transaction is a memory barrier.  */
    1188              :               /* ??? If we were really cool, we'd only be a barrier
    1189              :                  for the memories touched within the transaction.  */
    1190         1184 :               mark_all_reaching_defs_necessary (stmt);
    1191              :             }
    1192              :           else
    1193            0 :             gcc_unreachable ();
    1194              : 
    1195              :           /* If we over-used our alias oracle budget drop to simple
    1196              :              mode.  The cost metric allows quadratic behavior
    1197              :              (number of uses times number of may-defs queries) up to
    1198              :              a constant maximal number of queries and after that falls back to
    1199              :              super-linear complexity.  */
    1200    139826326 :           if (/* Constant but quadratic for small functions.  */
    1201    139826326 :               total_chain > 128 * 128
    1202              :               /* Linear in the number of may-defs.  */
    1203      1205073 :               && total_chain > 32 * longest_chain
    1204              :               /* Linear in the number of uses.  */
    1205         4479 :               && total_chain > nr_walks * 32)
    1206              :             {
    1207         4370 :               chain_ovfl = true;
    1208         4370 :               if (visited)
    1209         4370 :                 bitmap_clear (visited);
    1210              :             }
    1211              :         }
    1212              :     }
    1213      8302670 : }
    1214              : 
    1215              : /* Remove dead PHI nodes from block BB.  */
    1216              : 
    1217              : static bool
    1218     84164101 : remove_dead_phis (basic_block bb)
    1219              : {
    1220     84164101 :   bool something_changed = false;
    1221     84164101 :   gphi *phi;
    1222     84164101 :   gphi_iterator gsi;
    1223              : 
    1224    119664722 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
    1225              :     {
    1226     35500621 :       stats.total_phis++;
    1227     35500621 :       phi = gsi.phi ();
    1228              : 
    1229              :       /* We do not track necessity of virtual PHI nodes.  Instead do
    1230              :          very simple dead PHI removal here.  */
    1231     71001242 :       if (virtual_operand_p (gimple_phi_result (phi)))
    1232              :         {
    1233              :           /* Virtual PHI nodes with one or identical arguments
    1234              :              can be removed.  */
    1235     15882554 :           if (!loops_state_satisfies_p (LOOP_CLOSED_SSA)
    1236     15882554 :               && degenerate_phi_p (phi))
    1237              :             {
    1238      1342689 :               tree vdef = gimple_phi_result (phi);
    1239      1342689 :               tree vuse = gimple_phi_arg_def (phi, 0);
    1240              : 
    1241      1342689 :               use_operand_p use_p;
    1242      1342689 :               imm_use_iterator iter;
    1243      1342689 :               gimple *use_stmt;
    1244      3561827 :               FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef)
    1245      4503488 :                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    1246      2251744 :                   SET_USE (use_p, vuse);
    1247      1342689 :               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef)
    1248      1342689 :                   && TREE_CODE (vuse) == SSA_NAME)
    1249          471 :                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1;
    1250              :             }
    1251              :           else
    1252     14539865 :             gimple_set_plf (phi, STMT_NECESSARY, true);
    1253              :         }
    1254              : 
    1255     35500621 :       if (!gimple_plf (phi, STMT_NECESSARY))
    1256              :         {
    1257      1680031 :           something_changed = true;
    1258      1680031 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1259              :             {
    1260            9 :               fprintf (dump_file, "Deleting : ");
    1261            9 :               print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
    1262            9 :               fprintf (dump_file, "\n");
    1263              :             }
    1264              : 
    1265      1680031 :           remove_phi_node (&gsi, true);
    1266      1680031 :           stats.removed_phis++;
    1267      1680031 :           continue;
    1268              :         }
    1269              : 
    1270     33820590 :       gsi_next (&gsi);
    1271              :     }
    1272     84164101 :   return something_changed;
    1273              : }
    1274              : 
    1275              : 
    1276              : /* Remove dead statement pointed to by iterator I.  Receives the basic block BB
    1277              :    containing I so that we don't have to look it up.  */
    1278              : 
    1279              : static void
    1280      9835679 : remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb,
    1281              :                   vec<edge> &to_remove_edges)
    1282              : {
    1283      9835679 :   gimple *stmt = gsi_stmt (*i);
    1284              : 
    1285      9835679 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1286              :     {
    1287          125 :       fprintf (dump_file, "Deleting : ");
    1288          125 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1289          125 :       fprintf (dump_file, "\n");
    1290              :     }
    1291              : 
    1292      9835679 :   stats.removed++;
    1293              : 
    1294              :   /* If we have determined that a conditional branch statement contributes
    1295              :      nothing to the program, then we not only remove it, but we need to update
    1296              :      the CFG.  We can chose any of edges out of BB as long as we are sure to not
    1297              :      close infinite loops.  This is done by always choosing the edge closer to
    1298              :      exit in inverted_rev_post_order_compute order.  */
    1299      9835679 :   if (is_ctrl_stmt (stmt))
    1300              :     {
    1301        39359 :       edge_iterator ei;
    1302        39359 :       edge e = NULL, e2;
    1303              : 
    1304              :       /* See if there is only one non-abnormal edge.  */
    1305        39359 :       if (single_succ_p (bb))
    1306            0 :         e = single_succ_edge (bb);
    1307              :       /* Otherwise chose one that is closer to bb with live statement in it.
    1308              :          To be able to chose one, we compute inverted post order starting from
    1309              :          all BBs with live statements.  */
    1310            0 :       if (!e)
    1311              :         {
    1312        39359 :           if (!bb_postorder)
    1313              :             {
    1314        20163 :               int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
    1315        20163 :               int n = inverted_rev_post_order_compute (cfun, rpo,
    1316              :                                                        &bb_contains_live_stmts);
    1317        20163 :               bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
    1318       816355 :               for (int i = 0; i < n; ++i)
    1319       796192 :                  bb_postorder[rpo[i]] = i;
    1320        20163 :               free (rpo);
    1321              :             }
    1322       118098 :           FOR_EACH_EDGE (e2, ei, bb->succs)
    1323        78739 :             if (!e || e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
    1324        39380 :                 || bb_postorder [e->dest->index]
    1325        39380 :                    >= bb_postorder [e2->dest->index])
    1326        61184 :               e = e2;
    1327              :         }
    1328        39359 :       gcc_assert (e);
    1329        39359 :       e->probability = profile_probability::always ();
    1330              : 
    1331              :       /* The edge is no longer associated with a conditional, so it does
    1332              :          not have TRUE/FALSE flags.
    1333              :          We are also safe to drop EH/ABNORMAL flags and turn them into
    1334              :          normal control flow, because we know that all the destinations (including
    1335              :          those odd edges) are equivalent for program execution.  */
    1336        39359 :       e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_EH | EDGE_ABNORMAL);
    1337              : 
    1338              :       /* The lone outgoing edge from BB will be a fallthru edge.  */
    1339        39359 :       e->flags |= EDGE_FALLTHRU;
    1340              : 
    1341              :       /* Remove the remaining outgoing edges.  */
    1342       118098 :       FOR_EACH_EDGE (e2, ei, bb->succs)
    1343        78739 :         if (e != e2)
    1344              :           {
    1345              :             /* If we made a BB unconditionally exit a loop or removed
    1346              :                an entry into an irreducible region, then this transform
    1347              :                alters the set of BBs in the loop.  Schedule a fixup.  */
    1348        39380 :             if (loop_exit_edge_p (bb->loop_father, e)
    1349        39380 :                 || (e2->dest->flags & BB_IRREDUCIBLE_LOOP))
    1350        22238 :               loops_state_set (LOOPS_NEED_FIXUP);
    1351        39380 :             to_remove_edges.safe_push (e2);
    1352              :           }
    1353              :     }
    1354              : 
    1355              :   /* If this is a store into a variable that is being optimized away,
    1356              :      add a debug bind stmt if possible.  */
    1357      9835679 :   if (MAY_HAVE_DEBUG_BIND_STMTS
    1358      9169575 :       && gimple_assign_single_p (stmt)
    1359     10147354 :       && is_gimple_val (gimple_assign_rhs1 (stmt)))
    1360              :     {
    1361       171328 :       tree lhs = gimple_assign_lhs (stmt);
    1362       145826 :       if ((VAR_P (lhs) || TREE_CODE (lhs) == PARM_DECL)
    1363        25581 :           && !DECL_IGNORED_P (lhs)
    1364         5558 :           && is_gimple_reg_type (TREE_TYPE (lhs))
    1365           50 :           && !is_global_var (lhs)
    1366       171378 :           && !DECL_HAS_VALUE_EXPR_P (lhs))
    1367              :         {
    1368           50 :           tree rhs = gimple_assign_rhs1 (stmt);
    1369           50 :           gdebug *note
    1370           50 :             = gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt);
    1371           50 :           gsi_insert_after (i, note, GSI_SAME_STMT);
    1372              :         }
    1373              :     }
    1374              : 
    1375      9835679 :   unlink_stmt_vdef (stmt);
    1376      9835679 :   gsi_remove (i, true);
    1377      9835679 :   release_defs (stmt);
    1378      9835679 : }
    1379              : 
    1380              : /* Helper for maybe_optimize_arith_overflow.  Find in *TP if there are any
    1381              :    uses of data (SSA_NAME) other than REALPART_EXPR referencing it.  */
    1382              : 
    1383              : static tree
    1384           26 : find_non_realpart_uses (tree *tp, int *walk_subtrees, void *data)
    1385              : {
    1386           26 :   if (TYPE_P (*tp) || TREE_CODE (*tp) == REALPART_EXPR)
    1387            0 :     *walk_subtrees = 0;
    1388           26 :   if (*tp == (tree) data)
    1389           13 :     return *tp;
    1390              :   return NULL_TREE;
    1391              : }
    1392              : 
    1393              : /* If the IMAGPART_EXPR of the {ADD,SUB,MUL}_OVERFLOW result is never used,
    1394              :    but REALPART_EXPR is, optimize the {ADD,SUB,MUL}_OVERFLOW internal calls
    1395              :    into plain unsigned {PLUS,MINUS,MULT}_EXPR, and if needed reset debug
    1396              :    uses.  */
    1397              : 
    1398              : static void
    1399       287430 : maybe_optimize_arith_overflow (gimple_stmt_iterator *gsi,
    1400              :                                enum tree_code subcode)
    1401              : {
    1402       287430 :   gimple *stmt = gsi_stmt (*gsi);
    1403       287430 :   tree lhs = gimple_call_lhs (stmt);
    1404              : 
    1405       287430 :   if (lhs == NULL || TREE_CODE (lhs) != SSA_NAME)
    1406       287250 :     return;
    1407              : 
    1408       287430 :   imm_use_iterator imm_iter;
    1409       287430 :   use_operand_p use_p;
    1410       287430 :   bool has_debug_uses = false;
    1411       287430 :   bool has_realpart_uses = false;
    1412       287430 :   bool has_other_uses = false;
    1413       296245 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
    1414              :     {
    1415       296065 :       gimple *use_stmt = USE_STMT (use_p);
    1416       296065 :       if (is_gimple_debug (use_stmt))
    1417              :         has_debug_uses = true;
    1418       292232 :       else if (is_gimple_assign (use_stmt)
    1419       291197 :                && gimple_assign_rhs_code (use_stmt) == REALPART_EXPR
    1420       297214 :                && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == lhs)
    1421              :         has_realpart_uses = true;
    1422              :       else
    1423              :         {
    1424              :           has_other_uses = true;
    1425              :           break;
    1426              :         }
    1427       287430 :     }
    1428              : 
    1429       287430 :   if (!has_realpart_uses || has_other_uses)
    1430              :     return;
    1431              : 
    1432          180 :   tree arg0 = gimple_call_arg (stmt, 0);
    1433          180 :   tree arg1 = gimple_call_arg (stmt, 1);
    1434          180 :   location_t loc = gimple_location (stmt);
    1435          180 :   tree type = TREE_TYPE (TREE_TYPE (lhs));
    1436          180 :   tree utype = unsigned_type_for (type);
    1437          180 :   tree result = fold_build2_loc (loc, subcode, utype,
    1438              :                                  fold_convert_loc (loc, utype, arg0),
    1439              :                                  fold_convert_loc (loc, utype, arg1));
    1440          180 :   result = fold_convert_loc (loc, type, result);
    1441              : 
    1442          180 :   if (has_debug_uses)
    1443              :     {
    1444           13 :       gimple *use_stmt;
    1445           39 :       FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs)
    1446              :         {
    1447           26 :           if (!gimple_debug_bind_p (use_stmt))
    1448           13 :             continue;
    1449           13 :           tree v = gimple_debug_bind_get_value (use_stmt);
    1450           13 :           if (walk_tree (&v, find_non_realpart_uses, lhs, NULL))
    1451              :             {
    1452           13 :               gimple_debug_bind_reset_value (use_stmt);
    1453           13 :               update_stmt (use_stmt);
    1454              :             }
    1455           13 :         }
    1456              :     }
    1457              : 
    1458          180 :   if (TREE_CODE (result) == INTEGER_CST && TREE_OVERFLOW (result))
    1459            0 :     result = drop_tree_overflow (result);
    1460          180 :   tree overflow = build_zero_cst (type);
    1461          180 :   tree ctype = build_complex_type (type);
    1462          180 :   if (TREE_CODE (result) == INTEGER_CST)
    1463            0 :     result = build_complex (ctype, result, overflow);
    1464              :   else
    1465          180 :     result = build2_loc (gimple_location (stmt), COMPLEX_EXPR,
    1466              :                          ctype, result, overflow);
    1467              : 
    1468          180 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1469              :     {
    1470            0 :       fprintf (dump_file, "Transforming call: ");
    1471            0 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1472            0 :       fprintf (dump_file, "because the overflow result is never used into: ");
    1473            0 :       print_generic_stmt (dump_file, result, TDF_SLIM);
    1474            0 :       fprintf (dump_file, "\n");
    1475              :     }
    1476              : 
    1477          180 :   gimplify_and_update_call_from_tree (gsi, result);
    1478              : }
    1479              : 
    1480              : /* Returns whether the control parents of BB are preserved.  */
    1481              : 
    1482              : static bool
    1483       369122 : control_parents_preserved_p (basic_block bb)
    1484              : {
    1485              :   /* If we marked the control parents from BB they are preserved.  */
    1486       369122 :   if (bitmap_bit_p (visited_control_parents, bb->index))
    1487              :     return true;
    1488              : 
    1489              :   /* But they can also end up being marked from elsewhere.  */
    1490         7104 :   bitmap_iterator bi;
    1491         7104 :   unsigned edge_number;
    1492        11215 :   EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
    1493              :                             0, edge_number, bi)
    1494              :     {
    1495         7226 :       basic_block cd_bb = cd->get_edge_src (edge_number);
    1496         7226 :       if (cd_bb != bb
    1497         7226 :           && !bitmap_bit_p (last_stmt_necessary, cd_bb->index))
    1498              :         return false;
    1499              :     }
    1500              :   /* And cache the result.  */
    1501         3989 :   bitmap_set_bit (visited_control_parents, bb->index);
    1502         3989 :   return true;
    1503              : }
    1504              : 
    1505              : /* If basic block is empty, we can remove conditionals that controls
    1506              :    its execution.  However in some cases the empty BB can stay live
    1507              :    (such as when it was a header of empty loop).  In this case we
    1508              :    need to update its count.  Since regions of dead BBs are acyclic
    1509              :    we simply propagate counts forward from live BBs to dead ones.  */
    1510              : 
    1511              : static void
    1512        20196 : propagate_counts ()
    1513              : {
    1514        20196 :   basic_block bb;
    1515        20196 :   auto_vec<basic_block, 16> queue;
    1516        20196 :   hash_map <basic_block, int> cnt;
    1517              : 
    1518       732075 :   FOR_EACH_BB_FN (bb, cfun)
    1519       711879 :     if (!bitmap_bit_p (bb_contains_live_stmts, bb->index))
    1520              :       {
    1521       153027 :         int n = 0;
    1522       635182 :         for (edge e : bb->preds)
    1523       176101 :           if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
    1524       176101 :               && !bitmap_bit_p (bb_contains_live_stmts, e->src->index))
    1525        31505 :             n++;
    1526       153027 :         if (!n)
    1527       124403 :           queue.safe_push (bb);
    1528       153027 :         cnt.put (bb, n);
    1529              :       }
    1530       191493 :   while (!queue.is_empty ())
    1531              :     {
    1532       151101 :       basic_block bb = queue.pop ();
    1533       151101 :       profile_count sum = profile_count::zero ();
    1534              : 
    1535       475493 :       for (edge e : bb->preds)
    1536              :         {
    1537       173291 :           sum += e->count ();
    1538       173291 :           gcc_checking_assert (!cnt.get (e->src));
    1539              :         }
    1540              :       /* If we have partial profile and some counts of incoming edges are
    1541              :          unknown, it is probably better to keep the existing count.
    1542              :          We could also propagate bi-directionally.  */
    1543       151101 :       if (sum.initialized_p () && !(sum == bb->count))
    1544              :         {
    1545        18758 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1546              :             {
    1547            3 :               fprintf (dump_file, "Updating count of empty bb %i from ",
    1548              :                        bb->index);
    1549            3 :               bb->count.dump (dump_file);
    1550            3 :               fprintf (dump_file, " to ");
    1551            3 :               sum.dump (dump_file);
    1552            3 :               fprintf (dump_file, "\n");
    1553              :             }
    1554        18758 :           bb->count = sum;
    1555              :         }
    1556       151101 :       cnt.remove (bb);
    1557       604404 :       for (edge e : bb->succs)
    1558       151101 :         if (int *n = cnt.get (e->dest))
    1559              :           {
    1560        29579 :             (*n)--;
    1561        29579 :             if (!*n)
    1562        26698 :               queue.safe_push (e->dest);
    1563              :           }
    1564              :     }
    1565              :   /* Do not check that all blocks has been processed, since for
    1566              :      empty infinite loops this is not the case.  */
    1567        20196 : }
    1568              : 
    1569              : /* Eliminate unnecessary statements. Any instruction not marked as necessary
    1570              :    contributes nothing to the program, and can be deleted.  */
    1571              : 
    1572              : static bool
    1573      8302670 : eliminate_unnecessary_stmts (bool aggressive)
    1574              : {
    1575      8302670 :   bool something_changed = false;
    1576      8302670 :   basic_block bb;
    1577      8302670 :   gimple_stmt_iterator gsi, psi;
    1578      8302670 :   gimple *stmt;
    1579      8302670 :   auto_vec<edge> to_remove_edges;
    1580              : 
    1581      8302670 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1582          208 :     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
    1583              : 
    1584      8302670 :   bool had_setjmp = cfun->calls_setjmp;
    1585      8302670 :   clear_special_calls ();
    1586              : 
    1587              :   /* Walking basic blocks and statements in reverse order avoids
    1588              :      releasing SSA names before any other DEFs that refer to them are
    1589              :      released.  This helps avoid loss of debug information, as we get
    1590              :      a chance to propagate all RHSs of removed SSAs into debug uses,
    1591              :      rather than only the latest ones.  E.g., consider:
    1592              : 
    1593              :      x_3 = y_1 + z_2;
    1594              :      a_5 = x_3 - b_4;
    1595              :      # DEBUG a => a_5
    1596              : 
    1597              :      If we were to release x_3 before a_5, when we reached a_5 and
    1598              :      tried to substitute it into the debug stmt, we'd see x_3 there,
    1599              :      but x_3's DEF, type, etc would have already been disconnected.
    1600              :      By going backwards, the debug stmt first changes to:
    1601              : 
    1602              :      # DEBUG a => x_3 - b_4
    1603              : 
    1604              :      and then to:
    1605              : 
    1606              :      # DEBUG a => y_1 + z_2 - b_4
    1607              : 
    1608              :      as desired.  */
    1609      8302670 :   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
    1610      8302670 :   auto_vec<basic_block> h;
    1611      8302670 :   h = get_all_dominated_blocks (CDI_DOMINATORS,
    1612     16605340 :                                 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
    1613              : 
    1614     92466771 :   while (h.length ())
    1615              :     {
    1616     84164101 :       bb = h.pop ();
    1617              : 
    1618              :       /* Remove dead statements.  */
    1619     84164101 :       auto_bitmap debug_seen;
    1620     84164101 :       hash_set<int_hash <location_t, 0>> locs_seen;
    1621    808802138 :       for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi)
    1622              :         {
    1623    640473936 :           stmt = gsi_stmt (gsi);
    1624              : 
    1625    640473936 :           psi = gsi;
    1626    640473936 :           gsi_prev (&psi);
    1627              : 
    1628    640473936 :           stats.total++;
    1629              : 
    1630              :           /* We can mark a call to free as not necessary if the
    1631              :              defining statement of its argument is not necessary
    1632              :              (and thus is getting removed).  */
    1633    640473936 :           if (gimple_plf (stmt, STMT_NECESSARY)
    1634    640473936 :               && (gimple_call_builtin_p (stmt, BUILT_IN_FREE)
    1635    637549560 :                   || (is_gimple_call (stmt)
    1636     38104432 :                       && gimple_call_from_new_or_delete (as_a <gcall *> (stmt))
    1637      1266089 :                       && gimple_call_operator_delete_p (as_a <gcall *> (stmt)))))
    1638              :             {
    1639      1231277 :               tree ptr = gimple_call_arg (stmt, 0);
    1640      1231277 :               if (TREE_CODE (ptr) == SSA_NAME)
    1641              :                 {
    1642      1229916 :                   gimple *def_stmt = SSA_NAME_DEF_STMT (ptr);
    1643      1229916 :                   if (!gimple_nop_p (def_stmt)
    1644      1229916 :                       && !gimple_plf (def_stmt, STMT_NECESSARY))
    1645         7219 :                     gimple_set_plf (stmt, STMT_NECESSARY, false);
    1646              :                 }
    1647              :             }
    1648              : 
    1649              :           /* Comparisons of the return value of an allocation against NULL
    1650              :              can be turned to a constant if the allocation itself is
    1651              :              unnecessary.  */
    1652    640473936 :           if (gimple_plf (stmt, STMT_NECESSARY) && is_gimple_assign (stmt)
    1653    167137814 :               && (gimple_assign_rhs_code (stmt) == EQ_EXPR
    1654    166320789 :                   || gimple_assign_rhs_code (stmt) == NE_EXPR)
    1655    642103222 :               && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
    1656              :             {
    1657      1629027 :               tree rhs1 = gimple_assign_rhs1 (stmt);
    1658      1629027 :               gimple *def_stmt = SSA_NAME_DEF_STMT (rhs1);
    1659      1629027 :               if (!gimple_nop_p (def_stmt)
    1660      1629027 :                   && !gimple_plf (def_stmt, STMT_NECESSARY))
    1661              :                 {
    1662         1499 :                   gcc_checking_assert
    1663              :                     (checks_return_value_of_removable_allocation_p (stmt));
    1664         1499 :                   tree lhs = gimple_assign_lhs (stmt);
    1665         1499 :                   bool is_ne = gimple_assign_rhs_code (stmt) == NE_EXPR;
    1666         1499 :                   tree cst = constant_boolean_node (is_ne, TREE_TYPE (lhs));
    1667         1499 :                   gimple_assign_set_rhs_with_ops (&gsi, TREE_CODE (cst), cst);
    1668         1499 :                   update_stmt (gsi_stmt (gsi));
    1669              :                 }
    1670              :             }
    1671              : 
    1672              :           /* Conditional checking that return value of allocation is non-NULL
    1673              :              can be turned to constant if the allocation itself
    1674              :              is unnecessary.  */
    1675    640473936 :           if (gimple_plf (stmt, STMT_NECESSARY)
    1676    637880746 :               && gimple_code (stmt) == GIMPLE_COND
    1677    672346619 :               && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME)
    1678              :             {
    1679     31868572 :               gimple *def_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
    1680     31868572 :               if (!gimple_nop_p (def_stmt)
    1681     31868572 :                   && !gimple_plf (def_stmt, STMT_NECESSARY))
    1682              :                 {
    1683         2904 :                   gcc_checking_assert
    1684              :                         (checks_return_value_of_removable_allocation_p (stmt));
    1685         2904 :                   gimple_cond_set_lhs (as_a <gcond *>(stmt),
    1686              :                                        build_one_cst
    1687         2904 :                                          (TREE_TYPE (gimple_cond_rhs (stmt))));
    1688         2904 :                   update_stmt (stmt);
    1689              :                 }
    1690              :             }
    1691              : 
    1692              :           /* If GSI is not necessary then remove it.  */
    1693    640473936 :           if (!gimple_plf (stmt, STMT_NECESSARY))
    1694              :             {
    1695              :               /* Keep clobbers that we can keep live live.  */
    1696      2593190 :               if (gimple_clobber_p (stmt))
    1697              :                 {
    1698       878360 :                   ssa_op_iter iter;
    1699       878360 :                   use_operand_p use_p;
    1700       878360 :                   bool dead = false;
    1701      1754387 :                   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
    1702              :                     {
    1703       878360 :                       tree name = USE_FROM_PTR (use_p);
    1704       878360 :                       if (!SSA_NAME_IS_DEFAULT_DEF (name)
    1705       878360 :                           && !bitmap_bit_p (processed, SSA_NAME_VERSION (name)))
    1706              :                         {
    1707              :                           dead = true;
    1708              :                           break;
    1709              :                         }
    1710              :                     }
    1711      1751272 :                   if (!dead
    1712              :                       /* When doing CD-DCE we have to ensure all controls
    1713              :                          of the stmt are still live.  */
    1714       878360 :                       && (!aggressive || control_parents_preserved_p (bb)))
    1715              :                     {
    1716       872912 :                       bitmap_clear (debug_seen);
    1717       872912 :                       continue;
    1718              :                     }
    1719              :                 }
    1720      1720278 :               if (!is_gimple_debug (stmt))
    1721      1322251 :                 something_changed = true;
    1722      1720278 :               remove_dead_stmt (&gsi, bb, to_remove_edges);
    1723      1720278 :               continue;
    1724      1720278 :             }
    1725    637880746 :           else if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
    1726              :             {
    1727     38435618 :               tree name = gimple_call_lhs (call_stmt);
    1728              : 
    1729     38435618 :               notice_special_calls (call_stmt);
    1730              : 
    1731              :               /* When LHS of var = call (); is dead, simplify it into
    1732              :                  call (); saving one operand.  */
    1733     38435618 :               if (name
    1734     14847155 :                   && TREE_CODE (name) == SSA_NAME
    1735     12449865 :                   && !bitmap_bit_p (processed, SSA_NAME_VERSION (name))
    1736              :                   /* Avoid doing so for allocation calls which we
    1737              :                      did not mark as necessary, it will confuse the
    1738              :                      special logic we apply to malloc/free pair removal.  */
    1739     38514369 :                   && !is_removable_allocation_p (call_stmt, false))
    1740              :                 {
    1741        78665 :                   something_changed = true;
    1742        78665 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    1743              :                     {
    1744            1 :                       fprintf (dump_file, "Deleting LHS of call: ");
    1745            1 :                       print_gimple_stmt (dump_file, call_stmt, 0, TDF_SLIM);
    1746            1 :                       fprintf (dump_file, "\n");
    1747              :                     }
    1748              : 
    1749        78665 :                   gimple_call_set_lhs (call_stmt, NULL_TREE);
    1750        78665 :                   maybe_clean_or_replace_eh_stmt (call_stmt, call_stmt);
    1751        78665 :                   update_stmt (call_stmt);
    1752        78665 :                   release_ssa_name (name);
    1753              : 
    1754              :                   /* __builtin_stack_save without lhs is not needed.  */
    1755        78665 :                   if (gimple_call_builtin_p (call_stmt, BUILT_IN_STACK_SAVE))
    1756           37 :                     remove_dead_stmt (&gsi, bb, to_remove_edges);
    1757              :                   /* GOMP_SIMD_LANE (unless three argument) or ASAN_POISON
    1758              :                      without lhs is not needed.  */
    1759        78628 :                   else if (gimple_call_internal_p (call_stmt))
    1760         7364 :                     switch (gimple_call_internal_fn (call_stmt))
    1761              :                       {
    1762          756 :                       case IFN_GOMP_SIMD_LANE:
    1763          756 :                         if (gimple_call_num_args (call_stmt) >= 3
    1764          789 :                             && !integer_nonzerop
    1765           33 :                                         (gimple_call_arg (call_stmt, 2)))
    1766              :                           break;
    1767              :                         /* FALLTHRU */
    1768          846 :                       case IFN_ASAN_POISON:
    1769          846 :                         remove_dead_stmt (&gsi, bb, to_remove_edges);
    1770          846 :                         break;
    1771              :                       default:
    1772              :                         break;
    1773              :                       }
    1774              :                 }
    1775     38356953 :               else if (gimple_call_internal_p (call_stmt))
    1776      1065382 :                 switch (gimple_call_internal_fn (call_stmt))
    1777              :                   {
    1778        88755 :                   case IFN_ADD_OVERFLOW:
    1779        88755 :                     maybe_optimize_arith_overflow (&gsi, PLUS_EXPR);
    1780        88755 :                     break;
    1781        95658 :                   case IFN_SUB_OVERFLOW:
    1782        95658 :                     maybe_optimize_arith_overflow (&gsi, MINUS_EXPR);
    1783        95658 :                     break;
    1784        98166 :                   case IFN_MUL_OVERFLOW:
    1785        98166 :                     maybe_optimize_arith_overflow (&gsi, MULT_EXPR);
    1786        98166 :                     break;
    1787        26942 :                   case IFN_UADDC:
    1788        26942 :                     if (integer_zerop (gimple_call_arg (call_stmt, 2)))
    1789         2781 :                       maybe_optimize_arith_overflow (&gsi, PLUS_EXPR);
    1790              :                     break;
    1791        15100 :                   case IFN_USUBC:
    1792        15100 :                     if (integer_zerop (gimple_call_arg (call_stmt, 2)))
    1793         2070 :                       maybe_optimize_arith_overflow (&gsi, MINUS_EXPR);
    1794              :                     break;
    1795              :                   default:
    1796              :                     break;
    1797              :                   }
    1798              :             }
    1799    599445128 :           else if (gimple_debug_bind_p (stmt))
    1800              :             {
    1801              :               /* We are only keeping the last debug-bind of a
    1802              :                  non-DEBUG_EXPR_DECL variable in a series of
    1803              :                  debug-bind stmts.  */
    1804    297188039 :               tree var = gimple_debug_bind_get_var (stmt);
    1805    297188039 :               if (TREE_CODE (var) != DEBUG_EXPR_DECL
    1806    297188039 :                   && !bitmap_set_bit (debug_seen, DECL_UID (var)))
    1807      8093669 :                 remove_dead_stmt (&gsi, bb, to_remove_edges);
    1808    297188039 :               continue;
    1809    297188039 :             }
    1810    302257089 :           else if (gimple_debug_begin_stmt_p (stmt))
    1811              :             {
    1812              :               /* We are only keeping the last debug-begin in a series of
    1813              :                  debug-begin stmts.  */
    1814     28296770 :               if (locs_seen.add (gimple_location (stmt)))
    1815        20849 :                 remove_dead_stmt (&gsi, bb, to_remove_edges);
    1816     28296770 :               continue;
    1817              :             }
    1818    312395937 :           locs_seen.empty ();
    1819    312395937 :           bitmap_clear (debug_seen);
    1820              :         }
    1821              : 
    1822              :       /* Remove dead PHI nodes.  */
    1823     84164101 :       something_changed |= remove_dead_phis (bb);
    1824     84164101 :     }
    1825              : 
    1826              :   /* First remove queued edges.  */
    1827      8302670 :   if (!to_remove_edges.is_empty ())
    1828              :     {
    1829              :       /* Remove edges.  We've delayed this to not get bogus debug stmts
    1830              :          during PHI node removal.  */
    1831        59543 :       for (unsigned i = 0; i < to_remove_edges.length (); ++i)
    1832        39380 :         remove_edge (to_remove_edges[i]);
    1833        20163 :       cfg_altered = true;
    1834              :     }
    1835              :   /* When we cleared calls_setjmp we can purge all abnormal edges.  Do so.
    1836              :      ???  We'd like to assert that setjmp calls do not pop out of nothing
    1837              :      but we currently lack a per-stmt way of noting whether a call was
    1838              :      recognized as returns-twice (or rather receives-control).  */
    1839      8302670 :   if (!cfun->calls_setjmp && had_setjmp)
    1840              :     {
    1841              :       /* Make sure we only remove the edges, not dominated blocks.  Using
    1842              :          gimple_purge_dead_abnormal_call_edges would do that and we
    1843              :          cannot free dominators yet.  */
    1844         3823 :       FOR_EACH_BB_FN (bb, cfun)
    1845         9815 :         if (gcall *stmt = safe_dyn_cast <gcall *> (*gsi_last_bb (bb)))
    1846         2094 :           if (!stmt_can_make_abnormal_goto (stmt))
    1847              :             {
    1848          750 :               edge_iterator ei;
    1849          750 :               edge e;
    1850         1022 :               for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
    1851              :                 {
    1852          272 :                   if (e->flags & EDGE_ABNORMAL)
    1853              :                     {
    1854          112 :                       if (e->flags & EDGE_FALLTHRU)
    1855            0 :                         e->flags &= ~EDGE_ABNORMAL;
    1856              :                       else
    1857          112 :                         remove_edge (e);
    1858          112 :                       cfg_altered = true;
    1859              :                     }
    1860              :                   else
    1861          160 :                     ei_next (&ei);
    1862              :                 }
    1863              :             }
    1864              :     }
    1865              : 
    1866              :   /* Now remove the unreachable blocks.  */
    1867      8302670 :   if (cfg_altered)
    1868              :     {
    1869        20204 :       basic_block prev_bb;
    1870              : 
    1871        20204 :       find_unreachable_blocks ();
    1872              : 
    1873              :       /* Delete all unreachable basic blocks in reverse dominator order.  */
    1874        20204 :       for (bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
    1875       775087 :            bb != ENTRY_BLOCK_PTR_FOR_FN (cfun); bb = prev_bb)
    1876              :         {
    1877       754883 :           prev_bb = bb->prev_bb;
    1878              : 
    1879       754883 :           if ((bb_contains_live_stmts
    1880       754836 :                && !bitmap_bit_p (bb_contains_live_stmts, bb->index))
    1881      1313774 :               || !(bb->flags & BB_REACHABLE))
    1882              :             {
    1883              :               /* Since we don't track liveness of virtual PHI nodes, it is
    1884              :                  possible that we rendered some PHI nodes unreachable while
    1885              :                  they are still in use.  Mark them for renaming.  */
    1886       211684 :               for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
    1887        15692 :                    gsi_next (&gsi))
    1888        47074 :                 if (virtual_operand_p (gimple_phi_result (gsi.phi ())))
    1889              :                   {
    1890        15690 :                     bool found = false;
    1891        15690 :                     imm_use_iterator iter;
    1892              : 
    1893        15838 :                     FOR_EACH_IMM_USE_STMT (stmt, iter,
    1894              :                                            gimple_phi_result (gsi.phi ()))
    1895              :                       {
    1896        15185 :                         if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
    1897          121 :                           continue;
    1898        15064 :                         if (gimple_code (stmt) == GIMPLE_PHI
    1899        15064 :                             || gimple_plf (stmt, STMT_NECESSARY))
    1900              :                           {
    1901              :                             found = true;
    1902              :                             break;
    1903              :                           }
    1904        15690 :                       }
    1905        15690 :                     if (found)
    1906        15037 :                       mark_virtual_phi_result_for_renaming (gsi.phi ());
    1907              :                   }
    1908              : 
    1909       195992 :               if (!(bb->flags & BB_REACHABLE))
    1910              :                 {
    1911              :                   /* Speed up the removal of blocks that don't
    1912              :                      dominate others.  Walking backwards, this should
    1913              :                      be the common case.  ??? Do we need to recompute
    1914              :                      dominators because of cfg_altered?  */
    1915        42965 :                   if (!first_dom_son (CDI_DOMINATORS, bb))
    1916        42512 :                     delete_basic_block (bb);
    1917              :                   else
    1918              :                     {
    1919          453 :                       h = get_all_dominated_blocks (CDI_DOMINATORS, bb);
    1920              : 
    1921         2095 :                       while (h.length ())
    1922              :                         {
    1923         1642 :                           bb = h.pop ();
    1924         1642 :                           prev_bb = bb->prev_bb;
    1925              :                           /* Rearrangements to the CFG may have failed
    1926              :                              to update the dominators tree, so that
    1927              :                              formerly-dominated blocks are now
    1928              :                              otherwise reachable.  */
    1929         1642 :                           if (!!(bb->flags & BB_REACHABLE))
    1930            0 :                             continue;
    1931         1642 :                           delete_basic_block (bb);
    1932              :                         }
    1933              : 
    1934          453 :                       h.release ();
    1935              :                     }
    1936              :                 }
    1937              :             }
    1938              :         }
    1939        20204 :       if (bb_contains_live_stmts)
    1940        20196 :         propagate_counts ();
    1941              :     }
    1942              : 
    1943      8302670 :   if (bb_postorder)
    1944        20163 :     free (bb_postorder);
    1945      8302670 :   bb_postorder = NULL;
    1946              : 
    1947      8302670 :   return something_changed;
    1948      8302670 : }
    1949              : 
    1950              : 
    1951              : /* Print out removed statement statistics.  */
    1952              : 
    1953              : static void
    1954          214 : print_stats (void)
    1955              : {
    1956          214 :   float percg;
    1957              : 
    1958          214 :   percg = ((float) stats.removed / (float) stats.total) * 100;
    1959          214 :   fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
    1960              :            stats.removed, stats.total, (int) percg);
    1961              : 
    1962          214 :   if (stats.total_phis == 0)
    1963              :     percg = 0;
    1964              :   else
    1965           38 :     percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
    1966              : 
    1967          214 :   fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
    1968              :            stats.removed_phis, stats.total_phis, (int) percg);
    1969          214 : }
    1970              : 
    1971              : /* Initialization for this pass.  Set up the used data structures.  */
    1972              : 
    1973              : static void
    1974      8302670 : tree_dce_init (bool aggressive)
    1975              : {
    1976      8302670 :   memset ((void *) &stats, 0, sizeof (stats));
    1977              : 
    1978      8302670 :   if (aggressive)
    1979              :     {
    1980      3628376 :       last_stmt_necessary = sbitmap_alloc (last_basic_block_for_fn (cfun));
    1981      3628376 :       bitmap_clear (last_stmt_necessary);
    1982      3628376 :       bb_contains_live_stmts = sbitmap_alloc (last_basic_block_for_fn (cfun));
    1983      3628376 :       bitmap_clear (bb_contains_live_stmts);
    1984              :     }
    1985              : 
    1986     16605340 :   processed = sbitmap_alloc (num_ssa_names + 1);
    1987      8302670 :   bitmap_clear (processed);
    1988              : 
    1989      8302670 :   worklist.create (64);
    1990      8302670 :   cfg_altered = false;
    1991      8302670 : }
    1992              : 
    1993              : /* Cleanup after this pass.  */
    1994              : 
    1995              : static void
    1996      8302670 : tree_dce_done (bool aggressive)
    1997              : {
    1998      8302670 :   if (aggressive)
    1999              :     {
    2000      3628376 :       delete cd;
    2001      3628376 :       sbitmap_free (visited_control_parents);
    2002      3628376 :       sbitmap_free (last_stmt_necessary);
    2003      3628376 :       sbitmap_free (bb_contains_live_stmts);
    2004      3628376 :       bb_contains_live_stmts = NULL;
    2005              :     }
    2006              : 
    2007      8302670 :   sbitmap_free (processed);
    2008              : 
    2009      8302670 :   worklist.release ();
    2010      8302670 : }
    2011              : 
    2012              : 
    2013              : /* Main routine to eliminate dead code.
    2014              : 
    2015              :    AGGRESSIVE controls the aggressiveness of the algorithm.
    2016              :    In conservative mode, we ignore control dependence and simply declare
    2017              :    all but the most trivially dead branches necessary.  This mode is fast.
    2018              :    In aggressive mode, control dependences are taken into account, which
    2019              :    results in more dead code elimination, but at the cost of some time.  */
    2020              : 
    2021              : static unsigned int
    2022      8302670 : perform_tree_ssa_dce (bool aggressive)
    2023              : {
    2024      8302670 :   bool something_changed = 0;
    2025      8302670 :   unsigned todo = 0;
    2026              : 
    2027              :   /* Preheaders are needed for SCEV to work.
    2028              :      Simple lateches and recorded exits improve chances that loop will
    2029              :      proved to be finite in testcases such as in loop-15.c and loop-24.c  */
    2030      8302670 :   bool in_loop_pipeline = scev_initialized_p ();
    2031      8302670 :   if (aggressive && ! in_loop_pipeline)
    2032              :     {
    2033      3397239 :       loop_optimizer_init (LOOPS_NORMAL
    2034              :                            | LOOPS_HAVE_RECORDED_EXITS);
    2035      3397239 :       scev_initialize ();
    2036              :     }
    2037              : 
    2038      8302670 :   if (aggressive && make_forwarders_with_degenerate_phis (cfun))
    2039              :     todo |= TODO_cleanup_cfg;
    2040              : 
    2041      8302670 :   calculate_dominance_info (CDI_DOMINATORS);
    2042              : 
    2043      8302670 :   tree_dce_init (aggressive);
    2044              : 
    2045      8302670 :   if (aggressive)
    2046              :     {
    2047              :       /* Compute control dependence.  */
    2048      3628376 :       calculate_dominance_info (CDI_POST_DOMINATORS);
    2049      3628376 :       cd = new control_dependences ();
    2050              : 
    2051      7256752 :       visited_control_parents =
    2052      3628376 :         sbitmap_alloc (last_basic_block_for_fn (cfun));
    2053      3628376 :       bitmap_clear (visited_control_parents);
    2054              : 
    2055      3628376 :       mark_dfs_back_edges ();
    2056              :     }
    2057              : 
    2058      8302670 :   find_obviously_necessary_stmts (aggressive);
    2059              : 
    2060      8302670 :   if (aggressive && ! in_loop_pipeline)
    2061              :     {
    2062      3397239 :       scev_finalize ();
    2063      3397239 :       loop_optimizer_finalize ();
    2064              :     }
    2065              : 
    2066      8302670 :   longest_chain = 0;
    2067      8302670 :   total_chain = 0;
    2068      8302670 :   nr_walks = 0;
    2069      8302670 :   chain_ovfl = false;
    2070      8302670 :   visited = BITMAP_ALLOC (NULL);
    2071      8302670 :   propagate_necessity (aggressive);
    2072      8302670 :   BITMAP_FREE (visited);
    2073              : 
    2074      8302670 :   something_changed |= eliminate_unnecessary_stmts (aggressive);
    2075      8302670 :   something_changed |= cfg_altered;
    2076              : 
    2077              :   /* We do not update postdominators, so free them unconditionally.  */
    2078      8302670 :   free_dominance_info (CDI_POST_DOMINATORS);
    2079              : 
    2080              :   /* If we removed paths in the CFG, then we need to update
    2081              :      dominators as well.  I haven't investigated the possibility
    2082              :      of incrementally updating dominators.  */
    2083      8302670 :   if (cfg_altered)
    2084        20204 :     free_dominance_info (CDI_DOMINATORS);
    2085              : 
    2086      8302670 :   statistics_counter_event (cfun, "Statements deleted", stats.removed);
    2087      8302670 :   statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis);
    2088              : 
    2089              :   /* Debugging dumps.  */
    2090      8302670 :   if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
    2091          214 :     print_stats ();
    2092              : 
    2093      8302670 :   tree_dce_done (aggressive);
    2094              : 
    2095      8302670 :   if (something_changed)
    2096              :     {
    2097       629040 :       free_numbers_of_iterations_estimates (cfun);
    2098       629040 :       if (in_loop_pipeline)
    2099        67632 :         scev_reset ();
    2100              :       todo |= TODO_update_ssa | TODO_cleanup_cfg;
    2101              :     }
    2102      8302670 :   return todo;
    2103              : }
    2104              : 
    2105              : namespace {
    2106              : 
    2107              : const pass_data pass_data_dce =
    2108              : {
    2109              :   GIMPLE_PASS, /* type */
    2110              :   "dce", /* name */
    2111              :   OPTGROUP_NONE, /* optinfo_flags */
    2112              :   TV_TREE_DCE, /* tv_id */
    2113              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    2114              :   0, /* properties_provided */
    2115              :   0, /* properties_destroyed */
    2116              :   0, /* todo_flags_start */
    2117              :   0, /* todo_flags_finish */
    2118              : };
    2119              : 
    2120              : class pass_dce_base : public gimple_opt_pass
    2121              : {
    2122              : public:
    2123              :   /* opt_pass methods: */
    2124      8306511 :   bool gate (function *) final override { return flag_tree_dce != 0; }
    2125      2971800 :   void set_pass_param (unsigned n, bool param) final override
    2126              :     {
    2127      2971800 :       gcc_assert (n == 0 || n == 1);
    2128      2971800 :       if (n == 0)
    2129      1783080 :         update_address_taken_p = param;
    2130      1188720 :       else if (n == 1)
    2131      1188720 :         remove_unused_locals_p = param;
    2132      2971800 :     }
    2133              : 
    2134              : protected:
    2135      3268980 :   pass_dce_base (const pass_data &data, gcc::context *ctxt)
    2136      6537960 :     : gimple_opt_pass (data, ctxt)
    2137              :   {}
    2138      8302670 :   unsigned int execute_dce (function *, bool aggressive)
    2139              :     {
    2140      8302670 :       return (perform_tree_ssa_dce (aggressive)
    2141      8302670 :               | (remove_unused_locals_p ? TODO_remove_unused_locals : 0)
    2142      8302670 :               | (update_address_taken_p ? TODO_update_address_taken : 0));
    2143              :     }
    2144              : 
    2145              : private:
    2146              :   bool update_address_taken_p = false;
    2147              :   bool remove_unused_locals_p = false;
    2148              : }; // class pass_dce_base
    2149              : 
    2150              : 
    2151              : class pass_dce : public pass_dce_base
    2152              : {
    2153              : public:
    2154      2377440 :   pass_dce (gcc::context *ctxt)
    2155      4754880 :     : pass_dce_base (pass_data_dce, ctxt)
    2156              :   {}
    2157              : 
    2158              :   /* opt_pass methods: */
    2159      2080260 :   opt_pass * clone () final override { return new pass_dce (m_ctxt); }
    2160      4467921 :   unsigned int execute (function *func) final override
    2161              :     {
    2162      4467921 :       return execute_dce (func, /*aggressive=*/false);
    2163              :     }
    2164              : 
    2165              : }; // class pass_dce
    2166              : 
    2167              : } // anon namespace
    2168              : 
    2169              : gimple_opt_pass *
    2170       297180 : make_pass_dce (gcc::context *ctxt)
    2171              : {
    2172       297180 :   return new pass_dce (ctxt);
    2173              : }
    2174              : 
    2175              : namespace {
    2176              : 
    2177              : const pass_data pass_data_cd_dce =
    2178              : {
    2179              :   GIMPLE_PASS, /* type */
    2180              :   "cddce", /* name */
    2181              :   OPTGROUP_NONE, /* optinfo_flags */
    2182              :   TV_TREE_CD_DCE, /* tv_id */
    2183              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    2184              :   0, /* properties_provided */
    2185              :   0, /* properties_destroyed */
    2186              :   0, /* todo_flags_start */
    2187              :   0, /* todo_flags_finish */
    2188              : };
    2189              : 
    2190              : class pass_cd_dce : public pass_dce_base
    2191              : {
    2192              : public:
    2193       891540 :   pass_cd_dce (gcc::context *ctxt)
    2194      1783080 :     : pass_dce_base (pass_data_cd_dce, ctxt)
    2195              :   {}
    2196              : 
    2197              :   /* opt_pass methods: */
    2198       594360 :   opt_pass * clone () final override { return new pass_cd_dce (m_ctxt); }
    2199      3834749 :   unsigned int execute (function *func) final override
    2200              :     {
    2201      3834749 :       return execute_dce (func, /*aggressive=*/optimize >= 2);
    2202              :     }
    2203              : 
    2204              : }; // class pass_cd_dce
    2205              : 
    2206              : } // anon namespace
    2207              : 
    2208              : gimple_opt_pass *
    2209       297180 : make_pass_cd_dce (gcc::context *ctxt)
    2210              : {
    2211       297180 :   return new pass_cd_dce (ctxt);
    2212              : }
    2213              : 
    2214              : 
    2215              : /* A cheap DCE interface.  WORKLIST is a list of possibly dead stmts and
    2216              :    is consumed by this function.  The function has linear complexity in
    2217              :    the number of dead stmts with a constant factor like the average SSA
    2218              :    use operands number.
    2219              :    If no_delete is true (defaults to false) then rather than deleting the
    2220              :    statement, it is replaced with an assignment to 0.  This allows the
    2221              :    same elimination of statement dependencies, but delays the actual statement
    2222              :    removal from the IL until the next time DCE is run and they are detected
    2223              :    as dead statements with no uses. */
    2224              : 
    2225              : void
    2226     38990546 : simple_dce_from_worklist (bitmap worklist, bitmap need_eh_cleanup,
    2227              :                           bool no_delete)
    2228              : {
    2229     38990546 :   int phiremoved = 0;
    2230     38990546 :   int stmtremoved = 0;
    2231     74955939 :   while (! bitmap_empty_p (worklist))
    2232              :     {
    2233              :       /* Pop item.  */
    2234     35965393 :       unsigned i = bitmap_clear_first_set_bit (worklist);
    2235              : 
    2236     35965393 :       tree def = ssa_name (i);
    2237              :       /* Removed by somebody else or still in use.
    2238              :          Note use in itself for a phi node is not counted as still in use.  */
    2239     35965393 :       if (!def)
    2240     14662535 :         continue;
    2241     35798274 :       if (!has_zero_uses (def))
    2242              :         {
    2243     14455865 :           gimple *def_stmt = SSA_NAME_DEF_STMT (def);
    2244              : 
    2245     14455865 :           if (gimple_code (def_stmt) != GIMPLE_PHI)
    2246     14451048 :             continue;
    2247              : 
    2248      2667453 :           imm_use_iterator use_iter;
    2249      2667453 :           use_operand_p use_p;
    2250      2667453 :           bool canremove = true;
    2251              : 
    2252      2753560 :           FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
    2253              :             {
    2254      2748743 :               gimple *use_stmt = USE_STMT (use_p);
    2255              :               /* Ignore debug statements. */
    2256      2748743 :               if (is_gimple_debug (use_stmt))
    2257        78521 :                 continue;
    2258      2670222 :               if (use_stmt != def_stmt)
    2259              :                 {
    2260              :                   canremove = false;
    2261              :                   break;
    2262              :                 }
    2263      2667453 :             }
    2264      2667453 :           if (!canremove)
    2265      2662636 :             continue;
    2266              :         }
    2267              : 
    2268     21347226 :       gimple *t = SSA_NAME_DEF_STMT (def);
    2269     21347226 :       if (gimple_has_side_effects (t))
    2270              :         {
    2271        41861 :           gcall *call = dyn_cast <gcall *> (t);
    2272              :           // Remove the lhs for a call if not no_delete.
    2273        41861 :           if (call && !no_delete)
    2274              :             {
    2275        37137 :               gimple_call_set_lhs (call, NULL_TREE);
    2276        37137 :               update_stmt (call);
    2277        37137 :               release_ssa_name (def);
    2278              :             }
    2279        41861 :           continue;
    2280        41861 :         }
    2281              : 
    2282              :       /* The defining statement needs to be defining only this name.
    2283              :          ASM is the only statement that can define more than one
    2284              :          name. */
    2285     21305365 :       if (is_a<gasm *>(t)
    2286     21305365 :           && !single_ssa_def_operand (t, SSA_OP_ALL_DEFS))
    2287           15 :         continue;
    2288              : 
    2289              :       /* Don't remove statements that are needed for non-call
    2290              :          eh to work.  */
    2291     21305350 :       if (stmt_unremovable_because_of_non_call_eh_p (cfun, t))
    2292         2492 :         continue;
    2293              : 
    2294              :       /* Tell the caller that we removed a statement that might
    2295              :          throw so it could cleanup the cfg for that block. */
    2296     21302858 :       if (need_eh_cleanup && stmt_could_throw_p (cfun, t))
    2297          129 :         bitmap_set_bit (need_eh_cleanup, gimple_bb (t)->index);
    2298              : 
    2299              :       /* Add uses to the worklist.  */
    2300     21302858 :       ssa_op_iter iter;
    2301     21302858 :       use_operand_p use_p;
    2302     59684560 :       FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
    2303              :         {
    2304     17078844 :           tree use = USE_FROM_PTR (use_p);
    2305     17078844 :           if (TREE_CODE (use) == SSA_NAME
    2306     17078844 :               && ! SSA_NAME_IS_DEFAULT_DEF (use))
    2307     15355798 :             bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
    2308              :         }
    2309              : 
    2310              :       /* Remove stmt.  */
    2311     21302858 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2312              :         {
    2313          638 :           fprintf (dump_file, "Removing dead stmt:");
    2314          638 :           print_gimple_stmt (dump_file, t, 0);
    2315              :         }
    2316     21302858 :       gimple_stmt_iterator gsi = gsi_for_stmt (t);
    2317     21302858 :       if (gimple_code (t) == GIMPLE_PHI)
    2318              :         {
    2319      3179715 :           if (no_delete)
    2320              :             {
    2321           45 :               gphi *phi = as_a<gphi *> (t);
    2322           45 :               tree zero = build_zero_cst (TREE_TYPE (def));
    2323           45 :               edge_iterator ei;
    2324           45 :               edge e;
    2325          118 :               FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
    2326           73 :                 if (!(e->flags & EDGE_ABNORMAL))
    2327           69 :                   SET_PHI_ARG_DEF (phi, e->dest_idx, zero);
    2328           45 :               reset_flow_sensitive_info (def);
    2329              :             }
    2330              :           else
    2331      3179670 :             remove_phi_node (&gsi, true);
    2332              : 
    2333      3179715 :           phiremoved++;
    2334              :         }
    2335              :       else
    2336              :         {
    2337     18123143 :           unlink_stmt_vdef (t);
    2338     18123143 :           if (no_delete)
    2339              :             {
    2340          399 :               tree zero = build_zero_cst (TREE_TYPE (def));
    2341          399 :               gassign *new_stmt = gimple_build_assign (def, zero);
    2342          399 :               gsi_replace (&gsi, new_stmt, true);
    2343          399 :               reset_flow_sensitive_info (def);
    2344              :             }
    2345              :           else
    2346              :             {
    2347     18122744 :               gsi_remove (&gsi, true);
    2348     18122744 :               release_defs (t);
    2349              :             }
    2350     18123143 :           stmtremoved++;
    2351              :         }
    2352              :     }
    2353     77980568 :   statistics_counter_event (cfun, no_delete ? "PHIs rewritten" : "PHIs removed",
    2354              :                             phiremoved);
    2355     77980568 :   statistics_counter_event (cfun, no_delete ? "Statements rewritten"
    2356              :                                             : "Statements removed", stmtremoved);
    2357     38990546 : }
        

Generated by: LCOV version 2.5.0-beta

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