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   evrp_folder () : m_range_analyzer (/*update_global_ranges=*/true),
  49     m_vr_values (m_range_analyzer.get_vr_values ())
  50   {
  51   }
  52
  53   ~evrp_folder ()
  54   {
  55     m_vr_values->cleanup_edges_and_switches ();
  56
  57     if (dump_file)
  58       {
  59         fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
  60         m_range_analyzer.dump_all_value_ranges (dump_file);
  61         fprintf (dump_file, "\n");
  62       }
  63   }
  64
  65   tree get_value (tree op, gimple *stmt ATTRIBUTE_UNUSED) OVERRIDE
  66   {
  67     return m_vr_values->op_with_constant_singleton_value_range (op);
  68   }
  69
  70   void pre_fold_bb (basic_block bb) OVERRIDE
  71   {
  72     if (dump_file && (dump_flags & TDF_DETAILS))
  73       fprintf (dump_file, "evrp visiting BB%d\n", bb->index);
  74     m_range_analyzer.enter (bb);
  75   }
  76
  77   void pre_fold_stmt (gimple *stmt) OVERRIDE
  78   {
  79     if (dump_file && (dump_flags & TDF_DETAILS))
  80       {
  81         fprintf (dump_file, "evrp visiting stmt ");
  82         print_gimple_stmt (dump_file, stmt, 0);
  83       }
  84     m_range_analyzer.record_ranges_from_stmt (stmt, false);
  85   }
  86
  87   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
  88   {
  89     return m_vr_values->simplify_stmt_using_ranges (gsi);
  90   }
  91
  92   void post_fold_bb (basic_block bb) OVERRIDE
  93   {
  94     m_range_analyzer.leave (bb);
  95   }
  96
  97   void post_new_stmt (gimple *stmt) OVERRIDE
  98   {
  99     m_vr_values->set_defs_to_varying (stmt);
 100   }
 101
 102 private:
 103   DISABLE_COPY_AND_ASSIGN (evrp_folder);
 104   class evrp_range_analyzer m_range_analyzer;
 105   class vr_values *m_vr_values;
 106 };
 107
 108 /* Main entry point for the early vrp pass which is a simplified non-iterative
 109    version of vrp where basic blocks are visited in dominance order.  Value
 110    ranges discovered in early vrp will also be used by ipa-vrp.  */
 111
 112 static unsigned int
 113 execute_early_vrp ()
 114 {
 115   /* Ideally this setup code would move into the ctor for the folder
 116      However, this setup can change the number of blocks which
 117      invalidates the internal arrays that are set up by the dominator
 118      walker in substitute_and_fold_engine.  */
 119   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 120   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 121   scev_initialize ();
 122   calculate_dominance_info (CDI_DOMINATORS);
 123
 124   evrp_folder folder;
 125   folder.substitute_and_fold ();
 126
 127   scev_finalize ();
 128   loop_optimizer_finalize ();
 129   return 0;
 130 }
 131
 132 namespace {
 133
 134 const pass_data pass_data_early_vrp =
 135 {
 136   GIMPLE_PASS, /* type */
 137   "evrp", /* name */
 138   OPTGROUP_NONE, /* optinfo_flags */
 139   TV_TREE_EARLY_VRP, /* tv_id */
 140   PROP_ssa, /* properties_required */
 141   0, /* properties_provided */
 142   0, /* properties_destroyed */
 143   0, /* todo_flags_start */
 144   ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
 145 };
 146
 147 class pass_early_vrp : public gimple_opt_pass
 148 {
 149 public:
 150   pass_early_vrp (gcc::context *ctxt)
 151     : gimple_opt_pass (pass_data_early_vrp, ctxt)
 152     {}
 153
 154   /* opt_pass methods: */
 155   opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
 156   virtual bool gate (function *)
 157     {
 158       return flag_tree_vrp != 0;
 159     }
 160   virtual unsigned int execute (function *)
 161     { return execute_early_vrp (); }
 162
 163 }; // class pass_vrp
 164 } // anon namespace
 165
 166 gimple_opt_pass *
 167 make_pass_early_vrp (gcc::context *ctxt)
 168 {
 169   return new pass_early_vrp (ctxt);
 170 }