gcc/gimple-ssa-evrp.c

   1 /* Support routines for Value Range Propagation (VRP).
   2    Copyright (C) 2005-2021 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 #include "gimple-range.h"
  45
  46 // This is the classic EVRP folder which uses a dominator walk and pushes
  47 // ranges into the next block if it is a single predecessor block.
  48
  49 class evrp_folder : public substitute_and_fold_engine
  50 {
  51 public:
  52   evrp_folder () :
  53     substitute_and_fold_engine (),
  54     m_range_analyzer (/*update_global_ranges=*/true),
  55     simplifier (&m_range_analyzer)
  56   { }
  57
  58   ~evrp_folder ()
  59   {
  60     if (dump_file)
  61       {
  62         fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
  63         m_range_analyzer.dump_all_value_ranges (dump_file);
  64         fprintf (dump_file, "\n");
  65       }
  66   }
  67
  68   tree value_of_expr (tree name, gimple *stmt) OVERRIDE
  69   {
  70     return m_range_analyzer.value_of_expr (name, stmt);
  71   }
  72
  73   void pre_fold_bb (basic_block bb) OVERRIDE
  74   {
  75     if (dump_file && (dump_flags & TDF_DETAILS))
  76       fprintf (dump_file, "evrp visiting BB%d\n", bb->index);
  77     m_range_analyzer.enter (bb);
  78   }
  79
  80   void pre_fold_stmt (gimple *stmt) OVERRIDE
  81   {
  82     if (dump_file && (dump_flags & TDF_DETAILS))
  83       {
  84         fprintf (dump_file, "evrp visiting stmt ");
  85         print_gimple_stmt (dump_file, stmt, 0);
  86       }
  87     m_range_analyzer.record_ranges_from_stmt (stmt, false);
  88   }
  89
  90   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
  91   {
  92     return simplifier.simplify (gsi);
  93   }
  94
  95   void post_fold_bb (basic_block bb) OVERRIDE
  96   {
  97     m_range_analyzer.leave (bb);
  98   }
  99
 100   void post_new_stmt (gimple *stmt) OVERRIDE
 101   {
 102     m_range_analyzer.set_defs_to_varying (stmt);
 103   }
 104
 105 protected:
 106   DISABLE_COPY_AND_ASSIGN (evrp_folder);
 107   evrp_range_analyzer m_range_analyzer;
 108   simplify_using_ranges simplifier;
 109 };
 110
 111 // This is a ranger based folder which continues to use the dominator
 112 // walk to access the substitute and fold machinery.  Ranges are calculated
 113 // on demand.
 114
 115 class rvrp_folder : public substitute_and_fold_engine
 116 {
 117 public:
 118
 119   rvrp_folder () : substitute_and_fold_engine (), m_simplifier ()
 120   {
 121     if (param_evrp_mode & EVRP_MODE_TRACE)
 122       m_ranger = new trace_ranger ();
 123     else
 124       m_ranger = new gimple_ranger ();
 125     m_simplifier.set_range_query (m_ranger);
 126   }
 127
 128   ~rvrp_folder ()
 129   {
 130     if (dump_file && (dump_flags & TDF_DETAILS))
 131       m_ranger->dump (dump_file);
 132     delete m_ranger;
 133   }
 134
 135   tree value_of_expr (tree name, gimple *s = NULL) OVERRIDE
 136   {
 137     return m_ranger->value_of_expr (name, s);
 138   }
 139
 140   tree value_on_edge (edge e, tree name) OVERRIDE
 141   {
 142     return m_ranger->value_on_edge (e, name);
 143   }
 144
 145   tree value_of_stmt (gimple *s, tree name = NULL) OVERRIDE
 146   {
 147     return m_ranger->value_of_stmt (s, name);
 148   }
 149
 150   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
 151   {
 152     return m_simplifier.simplify (gsi);
 153   }
 154
 155 private:
 156   DISABLE_COPY_AND_ASSIGN (rvrp_folder);
 157   gimple_ranger *m_ranger;
 158   simplify_using_ranges m_simplifier;
 159 };
 160
 161 // In a hybrid folder, start with an EVRP folder, and add the required
 162 // fold_stmt bits to either try the ranger first or second.
 163 //
 164 // The 3 value_* routines will always query both EVRP and the ranger for
 165 // a result, and ensure they return the same value.  If either returns a value
 166 // when the other doesn't, it is flagged in the listing, and the discoverd
 167 // value is returned.
 168 //
 169 // The simplifier is unable to process 2 different sources, thus we try to
 170 // use one engine, and if it fails to simplify, try using the other engine.
 171 // It is reported when the first attempt fails and the second succeeds.
 172
 173 class hybrid_folder : public evrp_folder
 174 {
 175 public:
 176   hybrid_folder (bool evrp_first)
 177   {
 178     if (param_evrp_mode & EVRP_MODE_TRACE)
 179       m_ranger = new trace_ranger ();
 180     else
 181       m_ranger = new gimple_ranger ();
 182
 183     if (evrp_first)
 184       {
 185         first = &m_range_analyzer;
 186         second = m_ranger;
 187       }
 188      else
 189       {
 190         first = m_ranger;
 191         second = &m_range_analyzer;
 192       }
 193   }
 194
 195   ~hybrid_folder ()
 196   {
 197     if (dump_file && (dump_flags & TDF_DETAILS))
 198       m_ranger->dump (dump_file);
 199     delete m_ranger;
 200   }
 201
 202   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
 203     {
 204       simplifier.set_range_query (first);
 205       if (simplifier.simplify (gsi))
 206         return true;
 207
 208       simplifier.set_range_query (second);
 209       if (simplifier.simplify (gsi))
 210         {
 211           if (dump_file)
 212             fprintf (dump_file, "EVRP:hybrid: Second query simplifed stmt\n");
 213           return true;
 214         }
 215       return false;
 216     }
 217
 218   tree value_of_expr (tree name, gimple *) OVERRIDE;
 219   tree value_on_edge (edge, tree name) OVERRIDE;
 220   tree value_of_stmt (gimple *, tree name) OVERRIDE;
 221
 222 private:
 223   DISABLE_COPY_AND_ASSIGN (hybrid_folder);
 224   gimple_ranger *m_ranger;
 225   range_query *first;
 226   range_query *second;
 227   tree choose_value (tree evrp_val, tree ranger_val);
 228 };
 229
 230
 231 tree
 232 hybrid_folder::value_of_expr (tree op, gimple *stmt)
 233 {
 234   tree evrp_ret = evrp_folder::value_of_expr (op, stmt);
 235   tree ranger_ret = m_ranger->value_of_expr (op, stmt);
 236   return choose_value (evrp_ret, ranger_ret);
 237 }
 238
 239 tree
 240 hybrid_folder::value_on_edge (edge e, tree op)
 241 {
 242   // Call evrp::value_of_expr directly.  Otherwise another dual call is made
 243   // via hybrid_folder::value_of_expr, but without an edge.
 244   tree evrp_ret = evrp_folder::value_of_expr (op, NULL);
 245   tree ranger_ret = m_ranger->value_on_edge (e, op);
 246   return choose_value (evrp_ret, ranger_ret);
 247 }
 248
 249 tree
 250 hybrid_folder::value_of_stmt (gimple *stmt, tree op)
 251 {
 252   // Call evrp::value_of_expr directly.  Otherwise another dual call is made
 253   // via hybrid_folder::value_of_expr, but without a stmt.
 254   tree evrp_ret;
 255   if (op)
 256     evrp_ret = evrp_folder::value_of_expr (op, NULL);
 257   else
 258     evrp_ret = NULL_TREE;
 259
 260   tree ranger_ret = m_ranger->value_of_stmt (stmt, op);
 261   return choose_value (evrp_ret, ranger_ret);
 262 }
 263
 264 // Given trees returned by EVRP and Ranger, choose/report the value to use
 265 // by the folder.
 266
 267 tree
 268 hybrid_folder::choose_value (tree evrp_val, tree ranger_val)
 269 {
 270   // If both found the same value, just return it.
 271   if (evrp_val && ranger_val && !compare_values (evrp_val, ranger_val))
 272     return evrp_val;
 273
 274   // If neither returned a value, return NULL_TREE.
 275   if (!ranger_val && !evrp_val)
 276     return NULL_TREE;
 277
 278   // Otherwise there is a discrepancy to flag.
 279   if (dump_file)
 280     {
 281       if (evrp_val && ranger_val)
 282         fprintf (dump_file, "EVRP:hybrid: Disagreement\n");
 283       if (evrp_val)
 284         {
 285           fprintf (dump_file, "EVRP:hybrid: EVRP found singleton ");
 286           print_generic_expr (dump_file, evrp_val);
 287           fprintf (dump_file, "\n");
 288         }
 289       if (ranger_val)
 290         {
 291           fprintf (dump_file, "EVRP:hybrid: RVRP found singleton ");
 292           print_generic_expr (dump_file, ranger_val);
 293           fprintf (dump_file, "\n");
 294         }
 295     }
 296
 297   // If one value was found, return it.
 298   if (!evrp_val)
 299     return ranger_val;
 300   if (!ranger_val)
 301     return evrp_val;
 302
 303   // If values are different, return the first calculated value.
 304   if ((param_evrp_mode & EVRP_MODE_RVRP_FIRST) == EVRP_MODE_RVRP_FIRST)
 305     return ranger_val;
 306   return evrp_val;
 307 }
 308
 309 /* Main entry point for the early vrp pass which is a simplified non-iterative
 310    version of vrp where basic blocks are visited in dominance order.  Value
 311    ranges discovered in early vrp will also be used by ipa-vrp.  */
 312
 313 static unsigned int
 314 execute_early_vrp ()
 315 {
 316   /* Ideally this setup code would move into the ctor for the folder
 317      However, this setup can change the number of blocks which
 318      invalidates the internal arrays that are set up by the dominator
 319      walker in substitute_and_fold_engine.  */
 320   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
 321   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
 322   scev_initialize ();
 323   calculate_dominance_info (CDI_DOMINATORS);
 324
 325   // Only the last 2 bits matter for choosing the folder.
 326   switch (param_evrp_mode & EVRP_MODE_RVRP_FIRST)
 327     {
 328     case EVRP_MODE_EVRP_ONLY:
 329       {
 330         evrp_folder folder;
 331         folder.substitute_and_fold ();
 332         break;
 333       }
 334     case EVRP_MODE_RVRP_ONLY:
 335       {
 336         rvrp_folder folder;
 337         folder.substitute_and_fold ();
 338         break;
 339       }
 340     case EVRP_MODE_EVRP_FIRST:
 341       {
 342         hybrid_folder folder (true);
 343         folder.substitute_and_fold ();
 344         break;
 345       }
 346     case EVRP_MODE_RVRP_FIRST:
 347       {
 348         hybrid_folder folder (false);
 349         folder.substitute_and_fold ();
 350         break;
 351       }
 352     default:
 353       gcc_unreachable ();
 354     }
 355
 356   scev_finalize ();
 357   loop_optimizer_finalize ();
 358   return 0;
 359 }
 360
 361 namespace {
 362
 363 const pass_data pass_data_early_vrp =
 364 {
 365   GIMPLE_PASS, /* type */
 366   "evrp", /* name */
 367   OPTGROUP_NONE, /* optinfo_flags */
 368   TV_TREE_EARLY_VRP, /* tv_id */
 369   PROP_ssa, /* properties_required */
 370   0, /* properties_provided */
 371   0, /* properties_destroyed */
 372   0, /* todo_flags_start */
 373   ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
 374 };
 375
 376 class pass_early_vrp : public gimple_opt_pass
 377 {
 378 public:
 379   pass_early_vrp (gcc::context *ctxt)
 380     : gimple_opt_pass (pass_data_early_vrp, ctxt)
 381     {}
 382
 383   /* opt_pass methods: */
 384   opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
 385   virtual bool gate (function *)
 386     {
 387       return flag_tree_vrp != 0;
 388     }
 389   virtual unsigned int execute (function *)
 390     { return execute_early_vrp (); }
 391
 392 }; // class pass_vrp
 393 } // anon namespace
 394
 395 gimple_opt_pass *
 396 make_pass_early_vrp (gcc::context *ctxt)
 397 {
 398   return new pass_early_vrp (ctxt);
 399 }