LCOV - code coverage report
Current view: top level - gcc - gimple-ssa-evrp.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 150 155 96.8 %
Date: 2020-05-30 12:51:24 Functions: 10 11 90.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Support routines for Value Range Propagation (VRP).
       2                 :            :    Copyright (C) 2005-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify
       7                 :            : it under the terms of the GNU General Public License as published by
       8                 :            : the Free Software Foundation; either version 3, or (at your option)
       9                 :            : any later version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful,
      12                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14                 :            : GNU General Public License for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "backend.h"
      24                 :            : #include "tree.h"
      25                 :            : #include "gimple.h"
      26                 :            : #include "tree-pass.h"
      27                 :            : #include "ssa.h"
      28                 :            : #include "gimple-pretty-print.h"
      29                 :            : #include "cfganal.h"
      30                 :            : #include "gimple-fold.h"
      31                 :            : #include "tree-eh.h"
      32                 :            : #include "gimple-iterator.h"
      33                 :            : #include "tree-cfg.h"
      34                 :            : #include "tree-ssa-loop-manip.h"
      35                 :            : #include "tree-ssa-loop.h"
      36                 :            : #include "cfgloop.h"
      37                 :            : #include "tree-scalar-evolution.h"
      38                 :            : #include "tree-ssa-propagate.h"
      39                 :            : #include "alloc-pool.h"
      40                 :            : #include "domwalk.h"
      41                 :            : #include "tree-cfgcleanup.h"
      42                 :            : #include "vr-values.h"
      43                 :            : #include "gimple-ssa-evrp-analyze.h"
      44                 :            : 
      45                 :    1543340 : class evrp_folder : public substitute_and_fold_engine
      46                 :            : {
      47                 :            :  public:
      48                 :            :   tree get_value (tree) FINAL OVERRIDE;
      49                 :    1543340 :   evrp_folder (class vr_values *vr_values_) : vr_values (vr_values_) { }
      50                 :   47925400 :   bool simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
      51                 :   47925400 :     { return vr_values->simplify_stmt_using_ranges (gsi); }
      52                 :            :   class vr_values *vr_values;
      53                 :            : 
      54                 :            :  private:
      55                 :            :   DISABLE_COPY_AND_ASSIGN (evrp_folder);
      56                 :            : };
      57                 :            : 
      58                 :            : tree
      59                 :   24706300 : evrp_folder::get_value (tree op)
      60                 :            : {
      61                 :   24706300 :   return vr_values->op_with_constant_singleton_value_range (op);
      62                 :            : }
      63                 :            : 
      64                 :            : /* evrp_dom_walker visits the basic blocks in the dominance order and set
      65                 :            :    the Value Ranges (VR) for SSA_NAMEs in the scope.  Use this VR to
      66                 :            :    discover more VRs.  */
      67                 :            : 
      68                 :            : class evrp_dom_walker : public dom_walker
      69                 :            : {
      70                 :            : public:
      71                 :    1543340 :   evrp_dom_walker ()
      72                 :    1543340 :     : dom_walker (CDI_DOMINATORS),
      73                 :            :       evrp_range_analyzer (true),
      74                 :    1543340 :       evrp_folder (evrp_range_analyzer.get_vr_values ())
      75                 :            :     {
      76                 :    1543340 :       need_eh_cleanup = BITMAP_ALLOC (NULL);
      77                 :    1543340 :     }
      78                 :    1543340 :   ~evrp_dom_walker ()
      79                 :    1573120 :     {
      80                 :    1543340 :       BITMAP_FREE (need_eh_cleanup);
      81                 :    1543340 :     }
      82                 :            :   virtual edge before_dom_children (basic_block);
      83                 :            :   virtual void after_dom_children (basic_block);
      84                 :            :   void cleanup (void);
      85                 :            : 
      86                 :            :  private:
      87                 :            :   DISABLE_COPY_AND_ASSIGN (evrp_dom_walker);
      88                 :            :   bitmap need_eh_cleanup;
      89                 :            :   auto_vec<gimple *> stmts_to_fixup;
      90                 :            :   auto_vec<gimple *> stmts_to_remove;
      91                 :            : 
      92                 :            :   class evrp_range_analyzer evrp_range_analyzer;
      93                 :            :   class evrp_folder evrp_folder;
      94                 :            : };
      95                 :            : 
      96                 :            : edge
      97                 :    9820400 : evrp_dom_walker::before_dom_children (basic_block bb)
      98                 :            : {
      99                 :    9820400 :   if (dump_file && (dump_flags & TDF_DETAILS))
     100                 :         66 :     fprintf (dump_file, "Visiting BB%d\n", bb->index);
     101                 :            : 
     102                 :    9820400 :   evrp_range_analyzer.enter (bb);
     103                 :            : 
     104                 :    9820400 :   for (gphi_iterator gpi = gsi_start_phis (bb);
     105                 :   12581700 :        !gsi_end_p (gpi); gsi_next (&gpi))
     106                 :            :     {
     107                 :    2761250 :       gphi *phi = gpi.phi ();
     108                 :    2761250 :       tree lhs = PHI_RESULT (phi);
     109                 :    5522510 :       if (virtual_operand_p (lhs))
     110                 :    1403740 :         continue;
     111                 :            : 
     112                 :    1365220 :       const value_range_equiv *vr = evrp_range_analyzer.get_value_range (lhs);
     113                 :            :       /* Mark PHIs whose lhs we fully propagate for removal.  */
     114                 :    1365220 :       tree val;
     115                 :    1365220 :       if (vr->singleton_p (&val) && may_propagate_copy (lhs, val))
     116                 :            :         {
     117                 :       7711 :           stmts_to_remove.safe_push (phi);
     118                 :       7711 :           continue;
     119                 :            :         }
     120                 :            :     }
     121                 :            : 
     122                 :    9820400 :   edge taken_edge = NULL;
     123                 :            : 
     124                 :            :   /* Visit all other stmts and discover any new VRs possible.  */
     125                 :    9820400 :   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
     126                 :   57810800 :        !gsi_end_p (gsi); gsi_next (&gsi))
     127                 :            :     {
     128                 :   47990400 :       gimple *stmt = gsi_stmt (gsi);
     129                 :   47990400 :       tree output = NULL_TREE;
     130                 :   47990400 :       gimple *old_stmt = stmt;
     131                 :   47990400 :       bool was_noreturn = (is_gimple_call (stmt)
     132                 :   47990400 :                            && gimple_call_noreturn_p (stmt));
     133                 :            : 
     134                 :   47990400 :       if (dump_file && (dump_flags & TDF_DETAILS))
     135                 :            :         {
     136                 :         99 :           fprintf (dump_file, "Visiting stmt ");
     137                 :         99 :           print_gimple_stmt (dump_file, stmt, 0);
     138                 :            :         }
     139                 :            : 
     140                 :   47990400 :       evrp_range_analyzer.record_ranges_from_stmt (stmt, false);
     141                 :            : 
     142                 :   47990400 :       if (gcond *cond = dyn_cast <gcond *> (stmt))
     143                 :            :         {
     144                 :    2412380 :           evrp_range_analyzer.vrp_visit_cond_stmt (cond, &taken_edge);
     145                 :    2412380 :           if (taken_edge)
     146                 :            :             {
     147                 :      59496 :               if (taken_edge->flags & EDGE_TRUE_VALUE)
     148                 :      42156 :                 gimple_cond_make_true (cond);
     149                 :      17340 :               else if (taken_edge->flags & EDGE_FALSE_VALUE)
     150                 :      17340 :                 gimple_cond_make_false (cond);
     151                 :            :               else
     152                 :          0 :                 gcc_unreachable ();
     153                 :      59496 :               update_stmt (stmt);
     154                 :            :             }
     155                 :            :         }
     156                 :   45578100 :       else if (stmt_interesting_for_vrp (stmt))
     157                 :            :         {
     158                 :    6192100 :           output = get_output_for_vrp (stmt);
     159                 :    6192100 :           if (output)
     160                 :            :             {
     161                 :    6125460 :               const value_range_equiv *vr
     162                 :    6125460 :                 = evrp_range_analyzer.get_value_range (output);
     163                 :            : 
     164                 :            :               /* Mark stmts whose output we fully propagate for removal.  */
     165                 :    6125460 :               tree val;
     166                 :    6125460 :               if (vr->singleton_p (&val)
     167                 :      65332 :                   && may_propagate_copy (output, val)
     168                 :      65059 :                   && !stmt_could_throw_p (cfun, stmt)
     169                 :    6190520 :                   && !gimple_has_side_effects (stmt))
     170                 :            :                 {
     171                 :      65057 :                   stmts_to_remove.safe_push (stmt);
     172                 :      65057 :                   continue;
     173                 :            :                 }
     174                 :            :             }
     175                 :            :         }
     176                 :            : 
     177                 :            :       /* Try folding stmts with the VR discovered.  */
     178                 :   47925400 :       bool did_replace = evrp_folder.replace_uses_in (stmt);
     179                 :   47925400 :       gimple_stmt_iterator prev_gsi = gsi;
     180                 :   47925400 :       gsi_prev (&prev_gsi);
     181                 :   47925400 :       if (fold_stmt (&gsi, follow_single_use_edges)
     182                 :   47925400 :           || did_replace)
     183                 :            :         {
     184                 :     476879 :           stmt = gsi_stmt (gsi);
     185                 :     476879 :           update_stmt (stmt);
     186                 :            :           did_replace = true;
     187                 :            :         }
     188                 :   47925400 :       if (evrp_folder.simplify_stmt_using_ranges (&gsi))
     189                 :            :         {
     190                 :     158134 :           stmt = gsi_stmt (gsi);
     191                 :     158134 :           update_stmt (stmt);
     192                 :            :           did_replace = true;
     193                 :            :         }
     194                 :            : 
     195                 :   47767200 :       if (did_replace)
     196                 :            :         {
     197                 :            :           /* If we wound up generating new stmts during folding
     198                 :            :              drop all their defs to VARYING.  We can't easily
     199                 :            :              process them because we've already instantiated
     200                 :            :              ranges on uses on STMT that only hold after it.  */
     201                 :     634910 :           if (gsi_end_p (prev_gsi))
     202                 :     436360 :             prev_gsi = gsi_start_bb (bb);
     203                 :            :           else
     204                 :     416730 :             gsi_next (&prev_gsi);
     205                 :     650241 :           while (gsi_stmt (prev_gsi) != gsi_stmt (gsi))
     206                 :            :             {
     207                 :      15331 :               evrp_range_analyzer.get_vr_values ()
     208                 :      15331 :                 ->set_defs_to_varying (gsi_stmt (prev_gsi));
     209                 :      15331 :               gsi_next (&prev_gsi);
     210                 :            :             }
     211                 :            : 
     212                 :            :           /* If we cleaned up EH information from the statement,
     213                 :            :              remove EH edges.  */
     214                 :     634910 :           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
     215                 :         68 :             bitmap_set_bit (need_eh_cleanup, bb->index);
     216                 :            : 
     217                 :            :           /* If we turned a not noreturn call into a noreturn one
     218                 :            :              schedule it for fixup.  */
     219                 :     634910 :           if (!was_noreturn
     220                 :     624301 :               && is_gimple_call (stmt)
     221                 :     638439 :               && gimple_call_noreturn_p (stmt))
     222                 :          0 :             stmts_to_fixup.safe_push (stmt);
     223                 :            : 
     224                 :   47991400 :           if (gimple_assign_single_p (stmt))
     225                 :            :             {
     226                 :      29197 :               tree rhs = gimple_assign_rhs1 (stmt);
     227                 :      29197 :               if (TREE_CODE (rhs) == ADDR_EXPR)
     228                 :        370 :                 recompute_tree_invariant_for_addr_expr (rhs);
     229                 :            :             }
     230                 :            :         }
     231                 :            :     }
     232                 :            : 
     233                 :            :   /* Visit BB successor PHI nodes and replace PHI args.  */
     234                 :    9820400 :   edge e;
     235                 :    9820400 :   edge_iterator ei;
     236                 :   22860200 :   FOR_EACH_EDGE (e, ei, bb->succs)
     237                 :            :     {
     238                 :   13039800 :       for (gphi_iterator gpi = gsi_start_phis (e->dest);
     239                 :   19901100 :            !gsi_end_p (gpi); gsi_next (&gpi))
     240                 :            :         {
     241                 :    6861340 :           gphi *phi = gpi.phi ();
     242                 :    6861340 :           use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
     243                 :    6861340 :           tree arg = USE_FROM_PTR (use_p);
     244                 :   11752300 :           if (TREE_CODE (arg) != SSA_NAME
     245                 :    6861340 :               || virtual_operand_p (arg))
     246                 :    4890940 :             continue;
     247                 :    1970400 :           const value_range_equiv
     248                 :    1970400 :             *vr = evrp_range_analyzer.get_value_range (arg);
     249                 :    1970400 :           tree val;
     250                 :    1970400 :           if (vr->singleton_p (&val) && may_propagate_copy (arg, val))
     251                 :      27867 :             propagate_value (use_p, val);
     252                 :            :         }
     253                 :            :     }
     254                 :            :  
     255                 :    9820400 :   return taken_edge;
     256                 :            : }
     257                 :            : 
     258                 :            : void
     259                 :    9820400 : evrp_dom_walker::after_dom_children (basic_block bb)
     260                 :            : {
     261                 :    9820400 :   evrp_range_analyzer.leave (bb);
     262                 :    9820400 : }
     263                 :            : 
     264                 :            : /* Perform any cleanups after the main phase of EVRP has completed.  */
     265                 :            : 
     266                 :            : void
     267                 :    1543340 : evrp_dom_walker::cleanup (void)
     268                 :            : {
     269                 :    1543340 :   if (dump_file)
     270                 :            :     {
     271                 :         78 :       fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
     272                 :         78 :       evrp_range_analyzer.dump_all_value_ranges (dump_file);
     273                 :         78 :       fprintf (dump_file, "\n");
     274                 :            :     }
     275                 :            : 
     276                 :            :   /* Remove stmts in reverse order to make debug stmt creation possible.  */
     277                 :    1616110 :   while (! stmts_to_remove.is_empty ())
     278                 :            :     {
     279                 :      72768 :       gimple *stmt = stmts_to_remove.pop ();
     280                 :      72768 :       if (dump_file && dump_flags & TDF_DETAILS)
     281                 :            :         {
     282                 :          5 :           fprintf (dump_file, "Removing dead stmt ");
     283                 :          5 :           print_gimple_stmt (dump_file, stmt, 0);
     284                 :          5 :           fprintf (dump_file, "\n");
     285                 :            :         }
     286                 :      72768 :       gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
     287                 :      72768 :       if (gimple_code (stmt) == GIMPLE_PHI)
     288                 :       7711 :         remove_phi_node (&gsi, true);
     289                 :            :       else
     290                 :            :         {
     291                 :      65057 :           unlink_stmt_vdef (stmt);
     292                 :      65057 :           gsi_remove (&gsi, true);
     293                 :      65057 :           release_defs (stmt);
     294                 :            :         }
     295                 :            :     }
     296                 :            : 
     297                 :    1543340 :   if (!bitmap_empty_p (need_eh_cleanup))
     298                 :         64 :     gimple_purge_all_dead_eh_edges (need_eh_cleanup);
     299                 :            : 
     300                 :            :   /* Fixup stmts that became noreturn calls.  This may require splitting
     301                 :            :      blocks and thus isn't possible during the dominator walk.  Do this
     302                 :            :      in reverse order so we don't inadvertedly remove a stmt we want to
     303                 :            :      fixup by visiting a dominating now noreturn call first.  */
     304                 :    1543340 :   while (!stmts_to_fixup.is_empty ())
     305                 :            :     {
     306                 :          0 :       gimple *stmt = stmts_to_fixup.pop ();
     307                 :          0 :       fixup_noreturn_call (stmt);
     308                 :            :     }
     309                 :            : 
     310                 :    1543340 :   evrp_folder.vr_values->cleanup_edges_and_switches ();
     311                 :    1543340 : }
     312                 :            : 
     313                 :            : /* Main entry point for the early vrp pass which is a simplified non-iterative
     314                 :            :    version of vrp where basic blocks are visited in dominance order.  Value
     315                 :            :    ranges discovered in early vrp will also be used by ipa-vrp.  */
     316                 :            : 
     317                 :            : static unsigned int
     318                 :    1543340 : execute_early_vrp ()
     319                 :            : {
     320                 :            :   /* Ideally this setup code would move into the ctor for the dominator
     321                 :            :      walk.  However, this setup can change the number of blocks which
     322                 :            :      invalidates the internal arrays that are set up by the dominator
     323                 :            :      walker.  */
     324                 :    1543340 :   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
     325                 :    1543340 :   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
     326                 :    1543340 :   scev_initialize ();
     327                 :    1543340 :   calculate_dominance_info (CDI_DOMINATORS);
     328                 :            : 
     329                 :            :   /* Walk stmts in dominance order and propagate VRP.  */
     330                 :    1543340 :   evrp_dom_walker walker;
     331                 :    1543340 :   walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
     332                 :    1543340 :   walker.cleanup ();
     333                 :            : 
     334                 :    1543340 :   scev_finalize ();
     335                 :    1543340 :   loop_optimizer_finalize ();
     336                 :    1543340 :   return 0;
     337                 :            : }
     338                 :            : 
     339                 :            : namespace {
     340                 :            : 
     341                 :            : const pass_data pass_data_early_vrp =
     342                 :            : {
     343                 :            :   GIMPLE_PASS, /* type */
     344                 :            :   "evrp", /* name */
     345                 :            :   OPTGROUP_NONE, /* optinfo_flags */
     346                 :            :   TV_TREE_EARLY_VRP, /* tv_id */
     347                 :            :   PROP_ssa, /* properties_required */
     348                 :            :   0, /* properties_provided */
     349                 :            :   0, /* properties_destroyed */
     350                 :            :   0, /* todo_flags_start */
     351                 :            :   ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
     352                 :            : };
     353                 :            : 
     354                 :            : class pass_early_vrp : public gimple_opt_pass
     355                 :            : {
     356                 :            : public:
     357                 :     201440 :   pass_early_vrp (gcc::context *ctxt)
     358                 :     402880 :     : gimple_opt_pass (pass_data_early_vrp, ctxt)
     359                 :            :     {}
     360                 :            : 
     361                 :            :   /* opt_pass methods: */
     362                 :          0 :   opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
     363                 :    1601770 :   virtual bool gate (function *)
     364                 :            :     {
     365                 :    1601770 :       return flag_tree_vrp != 0;
     366                 :            :     }
     367                 :    1543340 :   virtual unsigned int execute (function *)
     368                 :    1543340 :     { return execute_early_vrp (); }
     369                 :            : 
     370                 :            : }; // class pass_vrp
     371                 :            : } // anon namespace
     372                 :            : 
     373                 :            : gimple_opt_pass *
     374                 :     201440 : make_pass_early_vrp (gcc::context *ctxt)
     375                 :            : {
     376                 :     201440 :   return new pass_early_vrp (ctxt);
     377                 :            : }
     378                 :            : 

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.