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 () :
  49     substitute_and_fold_engine (),
  50     m_range_analyzer (/*update_global_ranges=*/true),
  51     simplifier (&m_range_analyzer)
  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 value_of_expr (tree name, gimple *stmt) OVERRIDE
  65   {
  66     return m_range_analyzer.value_of_expr (name, stmt);
  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.set_defs_to_varying (stmt);
  99   }
 100
 101 private:
 102   DISABLE_COPY_AND_ASSIGN (evrp_folder);
 103   evrp_range_analyzer m_range_analyzer;
 104   simplify_using_ranges simplifier;
 105 };
 106
 107 /* Main entry point for the early vrp pass which is a simplified non-iterative
 108    version of vrp where basic blocks are visited in dominance order.  Value
 109    ranges discovered in early vrp will also be used by ipa-vrp.  */
 110
 111 static unsigned int
 112 execute_early_vrp ()
 113 {
 114   /* Ideally this setup code would move into the ctor for the folder
 115      However, this setup can change the number of blocks which
 116      invalidates the internal arrays that are set up by the dominator
 117      walker in substitute_and_fold_engine.  */
 118   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 119   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 120   scev_initialize ();
 121   calculate_dominance_info (CDI_DOMINATORS);
 122
 123   evrp_folder folder;
 124   folder.substitute_and_fold ();
 125
 126   scev_finalize ();
 127   loop_optimizer_finalize ();
 128   return 0;
 129 }
 130
 131 namespace {
 132
 133 const pass_data pass_data_early_vrp =
 134 {
 135   GIMPLE_PASS, /* type */
 136   "evrp", /* name */
 137   OPTGROUP_NONE, /* optinfo_flags */
 138   TV_TREE_EARLY_VRP, /* tv_id */
 139   PROP_ssa, /* properties_required */
 140   0, /* properties_provided */
 141   0, /* properties_destroyed */
 142   0, /* todo_flags_start */
 143   ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
 144 };
 145
 146 class pass_early_vrp : public gimple_opt_pass
 147 {
 148 public:
 149   pass_early_vrp (gcc::context *ctxt)
 150     : gimple_opt_pass (pass_data_early_vrp, ctxt)
 151     {}
 152
 153   /* opt_pass methods: */
 154   opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
 155   virtual bool gate (function *)
 156     {
 157       return flag_tree_vrp != 0;
 158     }
 159   virtual unsigned int execute (function *)
 160     { return execute_early_vrp (); }
 161
 162 }; // class pass_vrp
 163 } // anon namespace
 164
 165 gimple_opt_pass *
 166 make_pass_early_vrp (gcc::context *ctxt)
 167 {
 168   return new pass_early_vrp (ctxt);
 169 }