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:\n");
  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)
 225     {
 226       fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb->index);
 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   return true;
 233 }
 234
 235 // Precompute ranges defined in the current block, or ranges
 236 // that are exported on an edge to the next block.
 237
 238 void
 239 path_range_query::precompute_ranges_in_block (basic_block bb)
 240 {
 241   bitmap_iterator bi;
 242   int_range_max r, cached_range;
 243   unsigned i;
 244
 245   // Force recalculation of any names in the cache that are defined in
 246   // this block.  This can happen on interdependent SSA/phis in loops.
 247   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
 248     {
 249       tree name = ssa_name (i);
 250       gimple *def_stmt = SSA_NAME_DEF_STMT (name);
 251       basic_block def_bb = gimple_bb (def_stmt);
 252
 253       if (def_bb == bb)
 254         clear_cache (name);
 255     }
 256
 257   // Solve imports defined in this block.
 258   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
 259     {
 260       tree name = ssa_name (i);
 261
 262       if (range_defined_in_block (r, name, bb))
 263         set_cache (r, name);
 264     }
 265
 266   if (at_exit ())
 267     return;
 268
 269   // Solve imports that are exported to the next block.
 270   edge e = find_edge (bb, next_bb ());
 271   EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
 272     {
 273       tree name = ssa_name (i);
 274       gori_compute &g = m_ranger.gori ();
 275       bitmap exports = g.exports (bb);
 276
 277       if (bitmap_bit_p (exports, i))
 278         {
 279           if (g.outgoing_edge_range_p (r, e, name, *this))
 280             {
 281               if (get_cache (cached_range, name))
 282                 r.intersect (cached_range);
 283
 284               set_cache (r, name);
 285               if (DEBUG_SOLVER)
 286                 {
 287                   fprintf (dump_file, "outgoing_edge_range_p for ");
 288                   print_generic_expr (dump_file, name, TDF_SLIM);
 289                   fprintf (dump_file, " on edge %d->%d ",
 290                            e->src->index, e->dest->index);
 291                   fprintf (dump_file, "is ");
 292                   r.dump (dump_file);
 293                   fprintf (dump_file, "\n");
 294                 }
 295             }
 296         }
 297     }
 298 }
 299
 300 // Precompute the ranges for IMPORTS along PATH.
 301 //
 302 // IMPORTS are the set of SSA names, any of which could potentially
 303 // change the value of the final conditional in PATH.
 304
 305 void
 306 path_range_query::precompute_ranges (const vec<basic_block> &path,
 307                                      const bitmap_head *imports)
 308 {
 309   set_path (path);
 310   m_imports = imports;
 311
 312   if (DEBUG_SOLVER)
 313     fprintf (dump_file, "path_range_query: precompute_ranges\n");
 314
 315   while (1)
 316     {
 317       basic_block bb = curr_bb ();
 318
 319       precompute_ranges_in_block (bb);
 320
 321       if (at_exit ())
 322         break;
 323
 324       move_next ();
 325     }
 326
 327   if (DEBUG_SOLVER)
 328     dump (dump_file);
 329 }