gcc/gimple-ssa-evrp.c

   1 /* Support routines for Value Range Propagation (VRP).
   2    Copyright (C) 2005-2018 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   class vr_values *vr_values;
  51
  52  private:
  53   DISABLE_COPY_AND_ASSIGN (evrp_folder);
  54 };
  55
  56 tree
  57 evrp_folder::get_value (tree op)
  58 {
  59   return vr_values->op_with_constant_singleton_value_range (op);
  60 }
  61
  62 /* evrp_dom_walker visits the basic blocks in the dominance order and set
  63    the Value Ranges (VR) for SSA_NAMEs in the scope.  Use this VR to
  64    discover more VRs.  */
  65
  66 class evrp_dom_walker : public dom_walker
  67 {
  68 public:
  69   evrp_dom_walker ()
  70     : dom_walker (CDI_DOMINATORS),
  71       evrp_folder (evrp_range_analyzer.get_vr_values ())
  72     {
  73       need_eh_cleanup = BITMAP_ALLOC (NULL);
  74     }
  75   ~evrp_dom_walker ()
  76     {
  77       BITMAP_FREE (need_eh_cleanup);
  78     }
  79   virtual edge before_dom_children (basic_block);
  80   virtual void after_dom_children (basic_block);
  81   void cleanup (void);
  82
  83  private:
  84   DISABLE_COPY_AND_ASSIGN (evrp_dom_walker);
  85   bitmap need_eh_cleanup;
  86   auto_vec<gimple *> stmts_to_fixup;
  87   auto_vec<gimple *> stmts_to_remove;
  88
  89   class evrp_range_analyzer evrp_range_analyzer;
  90   class evrp_folder evrp_folder;
  91 };
  92
  93 edge
  94 evrp_dom_walker::before_dom_children (basic_block bb)
  95 {
  96   if (dump_file && (dump_flags & TDF_DETAILS))
  97     fprintf (dump_file, "Visiting BB%d\n", bb->index);
  98
  99   evrp_range_analyzer.enter (bb);
 100
 101   for (gphi_iterator gpi = gsi_start_phis (bb);
 102        !gsi_end_p (gpi); gsi_next (&gpi))
 103     {
 104       gphi *phi = gpi.phi ();
 105       tree lhs = PHI_RESULT (phi);
 106       if (virtual_operand_p (lhs))
 107         continue;
 108
 109       value_range *vr = evrp_range_analyzer.get_value_range (lhs);
 110       /* Mark PHIs whose lhs we fully propagate for removal.  */
 111       tree val = value_range_constant_singleton (vr);
 112       if (val && may_propagate_copy (lhs, val))
 113         {
 114           stmts_to_remove.safe_push (phi);
 115           continue;
 116         }
 117     }
 118
 119   edge taken_edge = NULL;
 120
 121   /* Visit all other stmts and discover any new VRs possible.  */
 122   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 123        !gsi_end_p (gsi); gsi_next (&gsi))
 124     {
 125       gimple *stmt = gsi_stmt (gsi);
 126       tree output = NULL_TREE;
 127       gimple *old_stmt = stmt;
 128       bool was_noreturn = (is_gimple_call (stmt)
 129                            && gimple_call_noreturn_p (stmt));
 130
 131       if (dump_file && (dump_flags & TDF_DETAILS))
 132         {
 133           fprintf (dump_file, "Visiting stmt ");
 134           print_gimple_stmt (dump_file, stmt, 0);
 135         }
 136
 137       evrp_range_analyzer.record_ranges_from_stmt (stmt, false);
 138
 139       if (gcond *cond = dyn_cast <gcond *> (stmt))
 140         {
 141           evrp_range_analyzer.vrp_visit_cond_stmt (cond, &taken_edge);
 142           if (taken_edge)
 143             {
 144               if (taken_edge->flags & EDGE_TRUE_VALUE)
 145                 gimple_cond_make_true (cond);
 146               else if (taken_edge->flags & EDGE_FALSE_VALUE)
 147                 gimple_cond_make_false (cond);
 148               else
 149                 gcc_unreachable ();
 150               update_stmt (stmt);
 151             }
 152         }
 153       else if (stmt_interesting_for_vrp (stmt))
 154         {
 155           output = get_output_for_vrp (stmt);
 156           if (output)
 157             {
 158               tree val;
 159               value_range *vr = evrp_range_analyzer.get_value_range (output);
 160
 161               /* Mark stmts whose output we fully propagate for removal.  */
 162               if ((vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
 163                   && (val = value_range_constant_singleton (vr))
 164                   && may_propagate_copy (output, val)
 165                   && !stmt_could_throw_p (stmt)
 166                   && !gimple_has_side_effects (stmt))
 167                 {
 168                   stmts_to_remove.safe_push (stmt);
 169                   continue;
 170                 }
 171             }
 172         }
 173
 174       /* Try folding stmts with the VR discovered.  */
 175       bool did_replace = evrp_folder.replace_uses_in (stmt);
 176       if (fold_stmt (&gsi, follow_single_use_edges)
 177           || did_replace)
 178         {
 179           stmt = gsi_stmt (gsi);
 180           update_stmt (stmt);
 181           did_replace = true;
 182         }
 183
 184       if (did_replace)
 185         {
 186           /* If we cleaned up EH information from the statement,
 187              remove EH edges.  */
 188           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
 189             bitmap_set_bit (need_eh_cleanup, bb->index);
 190
 191           /* If we turned a not noreturn call into a noreturn one
 192              schedule it for fixup.  */
 193           if (!was_noreturn
 194               && is_gimple_call (stmt)
 195               && gimple_call_noreturn_p (stmt))
 196             stmts_to_fixup.safe_push (stmt);
 197
 198           if (gimple_assign_single_p (stmt))
 199             {
 200               tree rhs = gimple_assign_rhs1 (stmt);
 201               if (TREE_CODE (rhs) == ADDR_EXPR)
 202                 recompute_tree_invariant_for_addr_expr (rhs);
 203             }
 204         }
 205     }
 206
 207   /* Visit BB successor PHI nodes and replace PHI args.  */
 208   edge e;
 209   edge_iterator ei;
 210   FOR_EACH_EDGE (e, ei, bb->succs)
 211     {
 212       for (gphi_iterator gpi = gsi_start_phis (e->dest);
 213            !gsi_end_p (gpi); gsi_next (&gpi))
 214         {
 215           gphi *phi = gpi.phi ();
 216           use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
 217           tree arg = USE_FROM_PTR (use_p);
 218           if (TREE_CODE (arg) != SSA_NAME
 219               || virtual_operand_p (arg))
 220             continue;
 221           value_range *vr = evrp_range_analyzer.get_value_range (arg);
 222           tree val = value_range_constant_singleton (vr);
 223           if (val && may_propagate_copy (arg, val))
 224             propagate_value (use_p, val);
 225         }
 226     }
 227
 228   return taken_edge;
 229 }
 230
 231 void
 232 evrp_dom_walker::after_dom_children (basic_block bb)
 233 {
 234   evrp_range_analyzer.leave (bb);
 235 }
 236
 237 /* Perform any cleanups after the main phase of EVRP has completed.  */
 238
 239 void
 240 evrp_dom_walker::cleanup (void)
 241 {
 242   if (dump_file)
 243     {
 244       fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
 245       evrp_range_analyzer.dump_all_value_ranges (dump_file);
 246       fprintf (dump_file, "\n");
 247     }
 248
 249   /* Remove stmts in reverse order to make debug stmt creation possible.  */
 250   while (! stmts_to_remove.is_empty ())
 251     {
 252       gimple *stmt = stmts_to_remove.pop ();
 253       if (dump_file && dump_flags & TDF_DETAILS)
 254         {
 255           fprintf (dump_file, "Removing dead stmt ");
 256           print_gimple_stmt (dump_file, stmt, 0);
 257           fprintf (dump_file, "\n");
 258         }
 259       gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 260       if (gimple_code (stmt) == GIMPLE_PHI)
 261         remove_phi_node (&gsi, true);
 262       else
 263         {
 264           unlink_stmt_vdef (stmt);
 265           gsi_remove (&gsi, true);
 266           release_defs (stmt);
 267         }
 268     }
 269
 270   if (!bitmap_empty_p (need_eh_cleanup))
 271     gimple_purge_all_dead_eh_edges (need_eh_cleanup);
 272
 273   /* Fixup stmts that became noreturn calls.  This may require splitting
 274      blocks and thus isn't possible during the dominator walk.  Do this
 275      in reverse order so we don't inadvertedly remove a stmt we want to
 276      fixup by visiting a dominating now noreturn call first.  */
 277   while (!stmts_to_fixup.is_empty ())
 278     {
 279       gimple *stmt = stmts_to_fixup.pop ();
 280       fixup_noreturn_call (stmt);
 281     }
 282 }
 283
 284 /* Main entry point for the early vrp pass which is a simplified non-iterative
 285    version of vrp where basic blocks are visited in dominance order.  Value
 286    ranges discovered in early vrp will also be used by ipa-vrp.  */
 287
 288 static unsigned int
 289 execute_early_vrp ()
 290 {
 291   /* Ideally this setup code would move into the ctor for the dominator
 292      walk.  However, this setup can change the number of blocks which
 293      invalidates the internal arrays that are set up by the dominator
 294      walker.  */
 295   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 296   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 297   scev_initialize ();
 298   calculate_dominance_info (CDI_DOMINATORS);
 299
 300   /* Walk stmts in dominance order and propagate VRP.  */
 301   evrp_dom_walker walker;
 302   walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
 303   walker.cleanup ();
 304
 305   scev_finalize ();
 306   loop_optimizer_finalize ();
 307   return 0;
 308 }
 309
 310 namespace {
 311
 312 const pass_data pass_data_early_vrp =
 313 {
 314   GIMPLE_PASS, /* type */
 315   "evrp", /* name */
 316   OPTGROUP_NONE, /* optinfo_flags */
 317   TV_TREE_EARLY_VRP, /* tv_id */
 318   PROP_ssa, /* properties_required */
 319   0, /* properties_provided */
 320   0, /* properties_destroyed */
 321   0, /* todo_flags_start */
 322   ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
 323 };
 324
 325 class pass_early_vrp : public gimple_opt_pass
 326 {
 327 public:
 328   pass_early_vrp (gcc::context *ctxt)
 329     : gimple_opt_pass (pass_data_early_vrp, ctxt)
 330     {}
 331
 332   /* opt_pass methods: */
 333   opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
 334   virtual bool gate (function *)
 335     {
 336       return flag_tree_vrp != 0;
 337     }
 338   virtual unsigned int execute (function *)
 339     { return execute_early_vrp (); }
 340
 341 }; // class pass_vrp
 342 } // anon namespace
 343
 344 gimple_opt_pass *
 345 make_pass_early_vrp (gcc::context *ctxt)
 346 {
 347   return new pass_early_vrp (ctxt);
 348 }
 349