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