gcc/gimple-ssa-evrp.c

   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 class evrp_folder : public substitute_and_fold_engine
  46 {
  47  public:
  48   tree get_value (tree) FINAL OVERRIDE;
  49   evrp_folder (class vr_values *vr_values_) : vr_values (vr_values_) { }
  50   bool simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
  51     { 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 evrp_folder::get_value (tree op)
  60 {
  61   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   evrp_dom_walker ()
  72     : dom_walker (CDI_DOMINATORS),
  73       evrp_range_analyzer (true),
  74       evrp_folder (evrp_range_analyzer.get_vr_values ())
  75     {
  76       need_eh_cleanup = BITMAP_ALLOC (NULL);
  77     }
  78   ~evrp_dom_walker ()
  79     {
  80       BITMAP_FREE (need_eh_cleanup);
  81     }
  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 evrp_dom_walker::before_dom_children (basic_block bb)
  98 {
  99   if (dump_file && (dump_flags & TDF_DETAILS))
 100     fprintf (dump_file, "Visiting BB%d\n", bb->index);
 101
 102   evrp_range_analyzer.enter (bb);
 103
 104   for (gphi_iterator gpi = gsi_start_phis (bb);
 105        !gsi_end_p (gpi); gsi_next (&gpi))
 106     {
 107       gphi *phi = gpi.phi ();
 108       tree lhs = PHI_RESULT (phi);
 109       if (virtual_operand_p (lhs))
 110         continue;
 111
 112       const value_range_equiv *vr = evrp_range_analyzer.get_value_range (lhs);
 113       /* Mark PHIs whose lhs we fully propagate for removal.  */
 114       tree val;
 115       if (vr->singleton_p (&val) && may_propagate_copy (lhs, val))
 116         {
 117           stmts_to_remove.safe_push (phi);
 118           continue;
 119         }
 120     }
 121
 122   edge taken_edge = NULL;
 123
 124   /* Visit all other stmts and discover any new VRs possible.  */
 125   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 126        !gsi_end_p (gsi); gsi_next (&gsi))
 127     {
 128       gimple *stmt = gsi_stmt (gsi);
 129       tree output = NULL_TREE;
 130       gimple *old_stmt = stmt;
 131       bool was_noreturn = (is_gimple_call (stmt)
 132                            && gimple_call_noreturn_p (stmt));
 133
 134       if (dump_file && (dump_flags & TDF_DETAILS))
 135         {
 136           fprintf (dump_file, "Visiting stmt ");
 137           print_gimple_stmt (dump_file, stmt, 0);
 138         }
 139
 140       evrp_range_analyzer.record_ranges_from_stmt (stmt, false);
 141
 142       if (gcond *cond = dyn_cast <gcond *> (stmt))
 143         {
 144           evrp_range_analyzer.vrp_visit_cond_stmt (cond, &taken_edge);
 145           if (taken_edge)
 146             {
 147               if (taken_edge->flags & EDGE_TRUE_VALUE)
 148                 gimple_cond_make_true (cond);
 149               else if (taken_edge->flags & EDGE_FALSE_VALUE)
 150                 gimple_cond_make_false (cond);
 151               else
 152                 gcc_unreachable ();
 153               update_stmt (stmt);
 154             }
 155         }
 156       else if (stmt_interesting_for_vrp (stmt))
 157         {
 158           output = get_output_for_vrp (stmt);
 159           if (output)
 160             {
 161               const value_range_equiv *vr
 162                 = evrp_range_analyzer.get_value_range (output);
 163
 164               /* Mark stmts whose output we fully propagate for removal.  */
 165               tree val;
 166               if (vr->singleton_p (&val)
 167                   && may_propagate_copy (output, val)
 168                   && !stmt_could_throw_p (cfun, stmt)
 169                   && !gimple_has_side_effects (stmt))
 170                 {
 171                   stmts_to_remove.safe_push (stmt);
 172                   continue;
 173                 }
 174             }
 175         }
 176
 177       /* Try folding stmts with the VR discovered.  */
 178       bool did_replace = evrp_folder.replace_uses_in (stmt);
 179       gimple_stmt_iterator prev_gsi = gsi;
 180       gsi_prev (&prev_gsi);
 181       if (fold_stmt (&gsi, follow_single_use_edges)
 182           || did_replace)
 183         {
 184           stmt = gsi_stmt (gsi);
 185           update_stmt (stmt);
 186           did_replace = true;
 187         }
 188       if (evrp_folder.simplify_stmt_using_ranges (&gsi))
 189         {
 190           stmt = gsi_stmt (gsi);
 191           update_stmt (stmt);
 192           did_replace = true;
 193         }
 194
 195       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           if (gsi_end_p (prev_gsi))
 202             prev_gsi = gsi_start_bb (bb);
 203           else
 204             gsi_next (&prev_gsi);
 205           while (gsi_stmt (prev_gsi) != gsi_stmt (gsi))
 206             {
 207               evrp_range_analyzer.get_vr_values ()
 208                 ->set_defs_to_varying (gsi_stmt (prev_gsi));
 209               gsi_next (&prev_gsi);
 210             }
 211
 212           /* If we cleaned up EH information from the statement,
 213              remove EH edges.  */
 214           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
 215             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           if (!was_noreturn
 220               && is_gimple_call (stmt)
 221               && gimple_call_noreturn_p (stmt))
 222             stmts_to_fixup.safe_push (stmt);
 223
 224           if (gimple_assign_single_p (stmt))
 225             {
 226               tree rhs = gimple_assign_rhs1 (stmt);
 227               if (TREE_CODE (rhs) == ADDR_EXPR)
 228                 recompute_tree_invariant_for_addr_expr (rhs);
 229             }
 230         }
 231     }
 232
 233   /* Visit BB successor PHI nodes and replace PHI args.  */
 234   edge e;
 235   edge_iterator ei;
 236   FOR_EACH_EDGE (e, ei, bb->succs)
 237     {
 238       for (gphi_iterator gpi = gsi_start_phis (e->dest);
 239            !gsi_end_p (gpi); gsi_next (&gpi))
 240         {
 241           gphi *phi = gpi.phi ();
 242           use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
 243           tree arg = USE_FROM_PTR (use_p);
 244           if (TREE_CODE (arg) != SSA_NAME
 245               || virtual_operand_p (arg))
 246             continue;
 247           const value_range_equiv
 248             *vr = evrp_range_analyzer.get_value_range (arg);
 249           tree val;
 250           if (vr->singleton_p (&val) && may_propagate_copy (arg, val))
 251             propagate_value (use_p, val);
 252         }
 253     }
 254
 255   return taken_edge;
 256 }
 257
 258 void
 259 evrp_dom_walker::after_dom_children (basic_block bb)
 260 {
 261   evrp_range_analyzer.leave (bb);
 262 }
 263
 264 /* Perform any cleanups after the main phase of EVRP has completed.  */
 265
 266 void
 267 evrp_dom_walker::cleanup (void)
 268 {
 269   if (dump_file)
 270     {
 271       fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
 272       evrp_range_analyzer.dump_all_value_ranges (dump_file);
 273       fprintf (dump_file, "\n");
 274     }
 275
 276   /* Remove stmts in reverse order to make debug stmt creation possible.  */
 277   while (! stmts_to_remove.is_empty ())
 278     {
 279       gimple *stmt = stmts_to_remove.pop ();
 280       if (dump_file && dump_flags & TDF_DETAILS)
 281         {
 282           fprintf (dump_file, "Removing dead stmt ");
 283           print_gimple_stmt (dump_file, stmt, 0);
 284           fprintf (dump_file, "\n");
 285         }
 286       gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 287       if (gimple_code (stmt) == GIMPLE_PHI)
 288         remove_phi_node (&gsi, true);
 289       else
 290         {
 291           unlink_stmt_vdef (stmt);
 292           gsi_remove (&gsi, true);
 293           release_defs (stmt);
 294         }
 295     }
 296
 297   if (!bitmap_empty_p (need_eh_cleanup))
 298     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   while (!stmts_to_fixup.is_empty ())
 305     {
 306       gimple *stmt = stmts_to_fixup.pop ();
 307       fixup_noreturn_call (stmt);
 308     }
 309
 310   evrp_folder.vr_values->cleanup_edges_and_switches ();
 311 }
 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 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   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 325   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 326   scev_initialize ();
 327   calculate_dominance_info (CDI_DOMINATORS);
 328
 329   /* Walk stmts in dominance order and propagate VRP.  */
 330   evrp_dom_walker walker;
 331   walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
 332   walker.cleanup ();
 333
 334   scev_finalize ();
 335   loop_optimizer_finalize ();
 336   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   pass_early_vrp (gcc::context *ctxt)
 358     : gimple_opt_pass (pass_data_early_vrp, ctxt)
 359     {}
 360
 361   /* opt_pass methods: */
 362   opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
 363   virtual bool gate (function *)
 364     {
 365       return flag_tree_vrp != 0;
 366     }
 367   virtual unsigned int execute (function *)
 368     { return execute_early_vrp (); }
 369
 370 }; // class pass_vrp
 371 } // anon namespace
 372
 373 gimple_opt_pass *
 374 make_pass_early_vrp (gcc::context *ctxt)
 375 {
 376   return new pass_early_vrp (ctxt);
 377 }
 378