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