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