gcc/gimple-range-path.cc

   1 /* Basic block path solver.
   2    Copyright (C) 2021 Free Software Foundation, Inc.
   3    Contributed by Aldy Hernandez <aldyh@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15  for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "backend.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "cfganal.h"
  28 #include "value-range.h"
  29 #include "gimple-range.h"
  30 #include "tree-pretty-print.h"
  31 #include "gimple-range-path.h"
  32 #include "ssa.h"
  33
  34 // Internal construct to help facilitate debugging of solver.
  35 #define DEBUG_SOLVER (0 && dump_file)
  36
  37 path_range_query::path_range_query (gimple_ranger &ranger)
  38   : m_ranger (ranger)
  39 {
  40   m_cache = new ssa_global_cache;
  41   m_has_cache_entry = BITMAP_ALLOC (NULL);
  42   m_path = NULL;
  43 }
  44
  45 path_range_query::~path_range_query ()
  46 {
  47   BITMAP_FREE (m_has_cache_entry);
  48   delete m_cache;
  49 }
  50
  51 // Mark cache entry for NAME as unused.
  52
  53 void
  54 path_range_query::clear_cache (tree name)
  55 {
  56   unsigned v = SSA_NAME_VERSION (name);
  57   bitmap_clear_bit (m_has_cache_entry, v);
  58 }
  59
  60 // If NAME has a cache entry, return it in R, and return TRUE.
  61
  62 inline bool
  63 path_range_query::get_cache (irange &r, tree name)
  64 {
  65   if (!gimple_range_ssa_p (name))
  66     return get_global_range_query ()->range_of_expr (r, name);
  67
  68   unsigned v = SSA_NAME_VERSION (name);
  69   if (bitmap_bit_p (m_has_cache_entry, v))
  70     return m_cache->get_global_range (r, name);
  71
  72   return false;
  73 }
  74
  75 // Set the cache entry for NAME to R.
  76
  77 void
  78 path_range_query::set_cache (const irange &r, tree name)
  79 {
  80   unsigned v = SSA_NAME_VERSION (name);
  81   bitmap_set_bit (m_has_cache_entry, v);
  82   m_cache->set_global_range (name, r);
  83 }
  84
  85 void
  86 path_range_query::dump (FILE *dump_file)
  87 {
  88   if (m_path->is_empty ())
  89     return;
  90
  91   unsigned i;
  92   bitmap_iterator bi;
  93   extern void dump_ranger (FILE *, const vec<basic_block> &);
  94
  95   fprintf (dump_file, "Path is (length=%d):\n", m_path->length ());
  96   dump_ranger (dump_file, *m_path);
  97
  98   fprintf (dump_file, "Imports:\n");
  99   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
 100     {
 101       tree name = ssa_name (i);
 102       print_generic_expr (dump_file, name, TDF_SLIM);
 103       fprintf (dump_file, "\n");
 104     }
 105
 106   m_cache->dump (dump_file);
 107 }
 108
 109 void
 110 path_range_query::debug ()
 111 {
 112   dump (stderr);
 113 }
 114
 115 // Return the range of NAME at the end of the path being analyzed.
 116
 117 bool
 118 path_range_query::range_of_expr (irange &r, tree name, gimple *stmt)
 119 {
 120   if (!irange::supports_type_p (TREE_TYPE (name)))
 121     return false;
 122
 123   if (get_cache (r, name))
 124     return true;
 125
 126
 127   basic_block bb = stmt ? gimple_bb (stmt) : exit_bb ();
 128   if (stmt && range_defined_in_block (r, name, bb))
 129     {
 130       set_cache (r, name);
 131       return true;
 132     }
 133
 134   r.set_varying (TREE_TYPE (name));
 135   return true;
 136 }
 137
 138 // Return the range of STMT at the end of the path being analyzed.
 139 // Anything but the final conditional in a BB will return VARYING.
 140
 141 bool
 142 path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
 143 {
 144   tree type = gimple_range_type (stmt);
 145
 146   if (!irange::supports_type_p (type))
 147     return false;
 148
 149   if (gimple_code (stmt) == GIMPLE_COND && fold_range (r, stmt, this))
 150     return true;
 151
 152   r.set_varying (type);
 153   return true;
 154 }
 155
 156 // Initialize the current path to PATH.  The current block is set to
 157 // the entry block to the path.
 158 //
 159 // Note that the blocks are in reverse order, so the exit block is
 160 // path[0].
 161
 162 void
 163 path_range_query::set_path (const vec<basic_block> &path)
 164 {
 165   gcc_checking_assert (path.length () > 1);
 166   m_path = &path;
 167   m_pos = m_path->length () - 1;
 168   bitmap_clear (m_has_cache_entry);
 169 }
 170
 171 // Return the range of the result of PHI in R.
 172
 173 void
 174 path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
 175 {
 176   tree name = gimple_phi_result (phi);
 177   basic_block bb = gimple_bb (phi);
 178
 179   // We experimented with querying ranger's range_on_entry here, but
 180   // the performance penalty was too high, for hardly any improvements.
 181   if (at_entry ())
 182     {
 183       // Try fold just in case we can resolve simple things like PHI <5(99), 6(88)>.
 184       if (!fold_range (r, phi, this))
 185         r.set_varying (TREE_TYPE (name));
 186
 187       return;
 188     }
 189
 190   basic_block prev = prev_bb ();
 191   edge e_in = find_edge (prev, bb);
 192   unsigned nargs = gimple_phi_num_args (phi);
 193
 194   for (size_t i = 0; i < nargs; ++i)
 195     if (e_in == gimple_phi_arg_edge (phi, i))
 196       {
 197         tree arg = gimple_phi_arg_def (phi, i);
 198
 199         if (!get_cache (r, arg))
 200           r.set_varying (TREE_TYPE (name));
 201
 202         return;
 203       }
 204   gcc_unreachable ();
 205 }
 206
 207 // If NAME is defined in BB, set R to the range of NAME, and return
 208 // TRUE.  Otherwise, return FALSE.
 209
 210 bool
 211 path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
 212 {
 213   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
 214   basic_block def_bb = gimple_bb (def_stmt);
 215
 216   if (def_bb != bb)
 217     return false;
 218
 219   if (gimple_code (def_stmt) == GIMPLE_PHI)
 220     ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
 221   else if (!fold_range (r, def_stmt, this))
 222     r.set_varying (TREE_TYPE (name));
 223
 224   if (DEBUG_SOLVER && (bb || !r.varying_p ()))
 225     {
 226       fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1);
 227       print_generic_expr (dump_file, name, TDF_SLIM);
 228       fprintf (dump_file, " is ");
 229       r.dump (dump_file);
 230       fprintf (dump_file, "\n");
 231     }
 232
 233   // We may have an artificial statement not in the IL.
 234   if (!bb && r.varying_p ())
 235     return false;
 236
 237   return true;
 238 }
 239
 240 // Precompute ranges defined in the current block, or ranges
 241 // that are exported on an edge to the next block.
 242
 243 void
 244 path_range_query::precompute_ranges_in_block (basic_block bb)
 245 {
 246   bitmap_iterator bi;
 247   int_range_max r, cached_range;
 248   unsigned i;
 249
 250   // Force recalculation of any names in the cache that are defined in
 251   // this block.  This can happen on interdependent SSA/phis in loops.
 252   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
 253     {
 254       tree name = ssa_name (i);
 255       gimple *def_stmt = SSA_NAME_DEF_STMT (name);
 256       basic_block def_bb = gimple_bb (def_stmt);
 257
 258       if (def_bb == bb)
 259         clear_cache (name);
 260     }
 261
 262   // Solve imports defined in this block.
 263   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
 264     {
 265       tree name = ssa_name (i);
 266
 267       if (range_defined_in_block (r, name, bb))
 268         set_cache (r, name);
 269     }
 270
 271   if (at_exit ())
 272     return;
 273
 274   // Solve imports that are exported to the next block.
 275   edge e = find_edge (bb, next_bb ());
 276   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
 277     {
 278       tree name = ssa_name (i);
 279       gori_compute &g = m_ranger.gori ();
 280       bitmap exports = g.exports (bb);
 281
 282       if (bitmap_bit_p (exports, i))
 283         {
 284           if (g.outgoing_edge_range_p (r, e, name, *this))
 285             {
 286               if (get_cache (cached_range, name))
 287                 r.intersect (cached_range);
 288
 289               set_cache (r, name);
 290               if (DEBUG_SOLVER)
 291                 {
 292                   fprintf (dump_file, "outgoing_edge_range_p for ");
 293                   print_generic_expr (dump_file, name, TDF_SLIM);
 294                   fprintf (dump_file, " on edge %d->%d ",
 295                            e->src->index, e->dest->index);
 296                   fprintf (dump_file, "is ");
 297                   r.dump (dump_file);
 298                   fprintf (dump_file, "\n");
 299                 }
 300             }
 301         }
 302     }
 303 }
 304
 305 // Precompute the ranges for IMPORTS along PATH.
 306 //
 307 // IMPORTS are the set of SSA names, any of which could potentially
 308 // change the value of the final conditional in PATH.
 309
 310 void
 311 path_range_query::precompute_ranges (const vec<basic_block> &path,
 312                                      const bitmap_head *imports)
 313 {
 314   set_path (path);
 315   m_imports = imports;
 316
 317   if (DEBUG_SOLVER)
 318     {
 319       fprintf (dump_file, "\npath_range_query: precompute_ranges for path: ");
 320       for (unsigned i = path.length (); i > 0; --i)
 321         {
 322           basic_block bb = path[i - 1];
 323           fprintf (dump_file, "BB %d", bb->index);
 324           if (i > 1)
 325             fprintf (dump_file, ", ");
 326         }
 327       fprintf (dump_file, "\n");
 328     }
 329
 330   while (1)
 331     {
 332       basic_block bb = curr_bb ();
 333
 334       precompute_ranges_in_block (bb);
 335
 336       if (at_exit ())
 337         break;
 338
 339       move_next ();
 340     }
 341
 342   if (DEBUG_SOLVER)
 343     dump (dump_file);
 344 }