gcc/gimple-ssa-evrp.c

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