gcc/gimple-range.cc

   1 /* Code for GIMPLE range related routines.
   2    Copyright (C) 2019-2021 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>
   4    and Aldy Hernandez <aldyh@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "backend.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "ssa.h"
  29 #include "gimple-pretty-print.h"
  30 #include "gimple-iterator.h"
  31 #include "tree-cfg.h"
  32 #include "fold-const.h"
  33 #include "tree-cfg.h"
  34 #include "cfgloop.h"
  35 #include "tree-scalar-evolution.h"
  36 #include "gimple-range.h"
  37
  38 gimple_ranger::gimple_ranger () :
  39         non_executable_edge_flag (cfun),
  40         m_cache (non_executable_edge_flag),
  41         tracer ("")
  42 {
  43   // If the cache has a relation oracle, use it.
  44   m_oracle = m_cache.oracle ();
  45   if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
  46     tracer.enable_trace ();
  47
  48   // Ensure the not_executable flag is clear everywhere.
  49   if (flag_checking)
  50     {
  51       basic_block bb;
  52       FOR_ALL_BB_FN (bb, cfun)
  53         {
  54           edge_iterator ei;
  55           edge e;
  56           FOR_EACH_EDGE (e, ei, bb->succs)
  57             gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
  58         }
  59     }
  60 }
  61
  62 bool
  63 gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
  64 {
  65   unsigned idx;
  66   if (!gimple_range_ssa_p (expr))
  67     return get_tree_range (r, expr, stmt);
  68
  69   if ((idx = tracer.header ("range_of_expr(")))
  70     {
  71       print_generic_expr (dump_file, expr, TDF_SLIM);
  72       fputs (")", dump_file);
  73       if (stmt)
  74         {
  75           fputs (" at stmt ", dump_file);
  76           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
  77         }
  78       else
  79         fputs ("\n", dump_file);
  80     }
  81
  82   // If there is no statement, just get the global value.
  83   if (!stmt)
  84     {
  85       if (!m_cache.get_global_range (r, expr))
  86         r = gimple_range_global (expr);
  87     }
  88   // For a debug stmt, pick the best value currently available, do not
  89   // trigger new value calculations.  PR 100781.
  90   else if (is_gimple_debug (stmt))
  91     m_cache.range_of_expr (r, expr, stmt);
  92   else
  93     {
  94       basic_block bb = gimple_bb (stmt);
  95       gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
  96
  97       // If name is defined in this block, try to get an range from S.
  98       if (def_stmt && gimple_bb (def_stmt) == bb)
  99         {
 100           range_of_stmt (r, def_stmt, expr);
 101           m_cache.m_non_null.adjust_range (r, expr, bb, true);
 102         }
 103       // Otherwise OP comes from outside this block, use range on entry.
 104       else
 105         range_on_entry (r, bb, expr);
 106     }
 107   if (idx)
 108     tracer.trailer (idx, "range_of_expr", true, expr, r);
 109   return true;
 110 }
 111
 112 // Return the range of NAME on entry to block BB in R.
 113
 114 void
 115 gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
 116 {
 117   int_range_max entry_range;
 118   gcc_checking_assert (gimple_range_ssa_p (name));
 119
 120   unsigned idx;
 121   if ((idx = tracer.header ("range_on_entry (")))
 122     {
 123       print_generic_expr (dump_file, name, TDF_SLIM);
 124       fprintf (dump_file, ") to BB %d\n", bb->index);
 125     }
 126
 127   // Start with any known range
 128   range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
 129
 130   // Now see if there is any on_entry value which may refine it.
 131   if (m_cache.block_range (entry_range, bb, name))
 132     r.intersect (entry_range);
 133
 134   m_cache.m_non_null.adjust_range (r, name, bb, true);
 135
 136   if (idx)
 137     tracer.trailer (idx, "range_on_entry", true, name, r);
 138 }
 139
 140 // Calculate the range for NAME at the end of block BB and return it in R.
 141 // Return false if no range can be calculated.
 142
 143 void
 144 gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name)
 145 {
 146   // on-exit from the exit block?
 147   gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
 148   gcc_checking_assert (gimple_range_ssa_p (name));
 149
 150   unsigned idx;
 151   if ((idx = tracer.header ("range_on_exit (")))
 152     {
 153       print_generic_expr (dump_file, name, TDF_SLIM);
 154       fprintf (dump_file, ") from BB %d\n", bb->index);
 155     }
 156
 157   gimple *s = SSA_NAME_DEF_STMT (name);
 158   basic_block def_bb = gimple_bb (s);
 159   // If this is not the definition block, get the range on the last stmt in
 160   // the block... if there is one.
 161   if (def_bb != bb)
 162     s = last_stmt (bb);
 163   // If there is no statement provided, get the range_on_entry for this block.
 164   if (s)
 165     range_of_expr (r, name, s);
 166   else
 167     range_on_entry (r, bb, name);
 168   gcc_checking_assert (r.undefined_p ()
 169                        || range_compatible_p (r.type (), TREE_TYPE (name)));
 170
 171   if (idx)
 172     tracer.trailer (idx, "range_on_exit", true, name, r);
 173 }
 174
 175 // Calculate a range for NAME on edge E and return it in R.
 176
 177 bool
 178 gimple_ranger::range_on_edge (irange &r, edge e, tree name)
 179 {
 180   int_range_max edge_range;
 181   gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));
 182
 183   // Do not process values along abnormal edges.
 184   if (e->flags & EDGE_ABNORMAL)
 185     return get_tree_range (r, name, NULL);
 186
 187   unsigned idx;
 188   if ((idx = tracer.header ("range_on_edge (")))
 189     {
 190       print_generic_expr (dump_file, name, TDF_SLIM);
 191       fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
 192     }
 193
 194   // Check to see if the edge is executable.
 195   if ((e->flags & non_executable_edge_flag))
 196     {
 197       r.set_undefined ();
 198       if (idx)
 199         tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
 200                         name, r);
 201       return true;
 202     }
 203
 204   bool res = true;
 205   if (!gimple_range_ssa_p (name))
 206     return get_tree_range (r, name, NULL);
 207   else
 208     {
 209       range_on_exit (r, e->src, name);
 210       gcc_checking_assert  (r.undefined_p ()
 211                             || range_compatible_p (r.type(), TREE_TYPE (name)));
 212
 213       // Check to see if NAME is defined on edge e.
 214       if (m_cache.range_on_edge (edge_range, e, name))
 215         r.intersect (edge_range);
 216     }
 217
 218   if (idx)
 219     tracer.trailer (idx, "range_on_edge", res, name, r);
 220   return true;
 221 }
 222
 223 // fold_range wrapper for range_of_stmt to use as an internal client.
 224
 225 bool
 226 gimple_ranger::fold_range_internal (irange &r, gimple *s, tree name)
 227 {
 228   fold_using_range f;
 229   fur_depend src (s, &(gori ()), this);
 230   return f.fold_stmt (r, s, src, name);
 231 }
 232
 233 // Calculate a range for statement S and return it in R.  If NAME is
 234 // provided it represents the SSA_NAME on the LHS of the statement.
 235 // It is only required if there is more than one lhs/output.  Check
 236 // the global cache for NAME first to see if the evaluation can be
 237 // avoided.  If a range cannot be calculated, return false and UNDEFINED.
 238
 239 bool
 240 gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
 241 {
 242   bool res;
 243   r.set_undefined ();
 244
 245   unsigned idx;
 246   if ((idx = tracer.header ("range_of_stmt (")))
 247     {
 248       if (name)
 249         print_generic_expr (dump_file, name, TDF_SLIM);
 250       fputs (") at stmt ", dump_file);
 251       print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
 252     }
 253
 254   if (!name)
 255     name = gimple_get_lhs (s);
 256
 257   // If no name, simply call the base routine.
 258   if (!name)
 259     res = fold_range_internal (r, s, NULL_TREE);
 260   else if (!gimple_range_ssa_p (name))
 261     res = get_tree_range (r, name, NULL);
 262   // Check if the stmt has already been processed, and is not stale.
 263   else if (m_cache.get_non_stale_global_range (r, name))
 264     {
 265       if (idx)
 266         tracer.trailer (idx, " cached", true, name, r);
 267       return true;
 268     }
 269   else
 270     {
 271       // Otherwise calculate a new value.
 272       int_range_max tmp;
 273       fold_range_internal (tmp, s, name);
 274
 275       // Combine the new value with the old value.  This is required because
 276       // the way value propagation works, when the IL changes on the fly we
 277       // can sometimes get different results.  See PR 97741.
 278       r.intersect (tmp);
 279       m_cache.set_global_range (name, r);
 280       res = true;
 281     }
 282
 283   if (idx)
 284     tracer.trailer (idx, "range_of_stmt", res, name, r);
 285   return res;
 286 }
 287
 288 // This routine will export whatever global ranges are known to GCC
 289 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 290
 291 void
 292 gimple_ranger::export_global_ranges ()
 293 {
 294   /* Cleared after the table header has been printed.  */
 295   bool print_header = true;
 296   for (unsigned x = 1; x < num_ssa_names; x++)
 297     {
 298       int_range_max r;
 299       tree name = ssa_name (x);
 300       if (name && !SSA_NAME_IN_FREE_LIST (name)
 301           && gimple_range_ssa_p (name)
 302           && m_cache.get_global_range (r, name)
 303           && !r.varying_p())
 304         {
 305           bool updated = update_global_range (r, name);
 306           if (!updated || !dump_file || !(dump_flags & TDF_DETAILS))
 307             continue;
 308
 309           if (print_header)
 310             {
 311               /* Print the header only when there's something else
 312                  to print below.  */
 313               fprintf (dump_file, "Exported global range table:\n");
 314               fprintf (dump_file, "============================\n");
 315               print_header = false;
 316             }
 317
 318           value_range vr = r;
 319           print_generic_expr (dump_file, name , TDF_SLIM);
 320           fprintf (dump_file, "  : ");
 321           vr.dump (dump_file);
 322           fprintf (dump_file, "\n");
 323           int_range_max same = vr;
 324           if (same != r)
 325             {
 326               fprintf (dump_file, "         irange : ");
 327               r.dump (dump_file);
 328               fprintf (dump_file, "\n");
 329             }
 330         }
 331     }
 332 }
 333
 334 // Print the known table values to file F.
 335
 336 void
 337 gimple_ranger::dump_bb (FILE *f, basic_block bb)
 338 {
 339   unsigned x;
 340   edge_iterator ei;
 341   edge e;
 342   int_range_max range, tmp_range;
 343   fprintf (f, "\n=========== BB %d ============\n", bb->index);
 344   m_cache.dump_bb (f, bb);
 345
 346   ::dump_bb (f, bb, 4, TDF_NONE);
 347
 348   // Now find any globals defined in this block.
 349   for (x = 1; x < num_ssa_names; x++)
 350     {
 351       tree name = ssa_name (x);
 352       if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) &&
 353           gimple_bb (SSA_NAME_DEF_STMT (name)) == bb &&
 354           m_cache.get_global_range (range, name))
 355         {
 356           if (!range.varying_p ())
 357             {
 358               print_generic_expr (f, name, TDF_SLIM);
 359               fprintf (f, " : ");
 360               range.dump (f);
 361               fprintf (f, "\n");
 362             }
 363
 364         }
 365     }
 366
 367   // And now outgoing edges, if they define anything.
 368   FOR_EACH_EDGE (e, ei, bb->succs)
 369     {
 370       for (x = 1; x < num_ssa_names; x++)
 371         {
 372           tree name = gimple_range_ssa_p (ssa_name (x));
 373           if (name && gori ().has_edge_range_p (name, e)
 374               && m_cache.range_on_edge (range, e, name))
 375             {
 376               gimple *s = SSA_NAME_DEF_STMT (name);
 377               // Only print the range if this is the def block, or
 378               // the on entry cache for either end of the edge is
 379               // set.
 380               if ((s && bb == gimple_bb (s)) ||
 381                   m_cache.block_range (tmp_range, bb, name, false) ||
 382                   m_cache.block_range (tmp_range, e->dest, name, false))
 383                 {
 384                   if (!range.varying_p ())
 385                     {
 386                       fprintf (f, "%d->%d ", e->src->index,
 387                                e->dest->index);
 388                       char c = ' ';
 389                       if (e->flags & EDGE_TRUE_VALUE)
 390                         fprintf (f, " (T)%c", c);
 391                       else if (e->flags & EDGE_FALSE_VALUE)
 392                         fprintf (f, " (F)%c", c);
 393                       else
 394                         fprintf (f, "     ");
 395                       print_generic_expr (f, name, TDF_SLIM);
 396                       fprintf(f, " : \t");
 397                       range.dump(f);
 398                       fprintf (f, "\n");
 399                     }
 400                 }
 401             }
 402         }
 403     }
 404 }
 405
 406 // Print the known table values to file F.
 407
 408 void
 409 gimple_ranger::dump (FILE *f)
 410 {
 411   basic_block bb;
 412
 413   FOR_EACH_BB_FN (bb, cfun)
 414     dump_bb (f, bb);
 415
 416   m_cache.dump (f);
 417 }
 418
 419 void
 420 gimple_ranger::debug ()
 421 {
 422   dump (stderr);
 423 }
 424
 425 /* Create a new ranger instance and associate it with function FUN.
 426    Each call must be paired with a call to disable_ranger to release
 427    resources.  */
 428
 429 gimple_ranger *
 430 enable_ranger (struct function *fun)
 431 {
 432   gimple_ranger *r;
 433
 434   r = new gimple_ranger;
 435   fun->x_range_query = r;
 436
 437   return r;
 438 }
 439
 440 /* Destroy and release the ranger instance associated with function FUN
 441    and replace it the global ranger.  */
 442
 443 void
 444 disable_ranger (struct function *fun)
 445 {
 446   delete fun->x_range_query;
 447
 448   fun->x_range_query = &global_ranges;
 449 }