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