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