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 {
  40   // If the cache has a relation oracle, use it.
  41   m_oracle = m_cache.oracle ();
  42 }
  43
  44 bool
  45 gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
  46 {
  47   if (!gimple_range_ssa_p (expr))
  48     return get_tree_range (r, expr, stmt);
  49
  50   // If there is no statement, just get the global value.
  51   if (!stmt)
  52     {
  53       if (!m_cache.get_global_range (r, expr))
  54         r = gimple_range_global (expr);
  55       return true;
  56     }
  57
  58   // For a debug stmt, pick the best value currently available, do not
  59   // trigger new value calculations.  PR 100781.
  60   if (is_gimple_debug (stmt))
  61     {
  62       m_cache.range_of_expr (r, expr, stmt);
  63       return true;
  64     }
  65   basic_block bb = gimple_bb (stmt);
  66   gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
  67
  68   // If name is defined in this block, try to get an range from S.
  69   if (def_stmt && gimple_bb (def_stmt) == bb)
  70     {
  71       range_of_stmt (r, def_stmt, expr);
  72       if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
  73           m_cache.m_non_null.non_null_deref_p (expr, bb))
  74         r = range_nonzero (TREE_TYPE (expr));
  75     }
  76   else
  77     // Otherwise OP comes from outside this block, use range on entry.
  78     range_on_entry (r, bb, expr);
  79
  80   return true;
  81 }
  82
  83 // Return the range of NAME on entry to block BB in R.
  84
  85 void
  86 gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
  87 {
  88   int_range_max entry_range;
  89   gcc_checking_assert (gimple_range_ssa_p (name));
  90
  91   // Start with any known range
  92   range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
  93
  94   // Now see if there is any on_entry value which may refine it.
  95   if (m_cache.block_range (entry_range, bb, name))
  96     r.intersect (entry_range);
  97
  98   if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
  99       m_cache.m_non_null.non_null_deref_p (name, bb))
 100     r = range_nonzero (TREE_TYPE (name));
 101 }
 102
 103 // Calculate the range for NAME at the end of block BB and return it in R.
 104 // Return false if no range can be calculated.
 105
 106 void
 107 gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name)
 108 {
 109   // on-exit from the exit block?
 110   gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
 111   gcc_checking_assert (gimple_range_ssa_p (name));
 112
 113   gimple *s = SSA_NAME_DEF_STMT (name);
 114   basic_block def_bb = gimple_bb (s);
 115   // If this is not the definition block, get the range on the last stmt in
 116   // the block... if there is one.
 117   if (def_bb != bb)
 118     s = last_stmt (bb);
 119   // If there is no statement provided, get the range_on_entry for this block.
 120   if (s)
 121     range_of_expr (r, name, s);
 122   else
 123     range_on_entry (r, bb, name);
 124   gcc_checking_assert (r.undefined_p ()
 125                        || range_compatible_p (r.type (), TREE_TYPE (name)));
 126 }
 127
 128 // Calculate a range for NAME on edge E and return it in R.
 129
 130 bool
 131 gimple_ranger::range_on_edge (irange &r, edge e, tree name)
 132 {
 133   int_range_max edge_range;
 134   gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));
 135
 136   // PHI arguments can be constants, catch these here.
 137   if (!gimple_range_ssa_p (name))
 138     return range_of_expr (r, name);
 139
 140   range_on_exit (r, e->src, name);
 141   gcc_checking_assert  (r.undefined_p ()
 142                         || range_compatible_p (r.type(), TREE_TYPE (name)));
 143
 144   // Check to see if NAME is defined on edge e.
 145   if (m_cache.range_on_edge (edge_range, e, name))
 146     r.intersect (edge_range);
 147
 148   return true;
 149 }
 150
 151 // fold_range wrapper for range_of_stmt to use as an internal client.
 152
 153 bool
 154 gimple_ranger::fold_range_internal (irange &r, gimple *s, tree name)
 155 {
 156   fold_using_range f;
 157   fur_depend src (s, &(gori ()), this);
 158   return f.fold_stmt (r, s, src, name);
 159 }
 160
 161 // Calculate a range for statement S and return it in R.  If NAME is
 162 // provided it represents the SSA_NAME on the LHS of the statement.
 163 // It is only required if there is more than one lhs/output.  Check
 164 // the global cache for NAME first to see if the evaluation can be
 165 // avoided.  If a range cannot be calculated, return false and UNDEFINED.
 166
 167 bool
 168 gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
 169 {
 170   r.set_undefined ();
 171
 172   if (!name)
 173     name = gimple_get_lhs (s);
 174
 175   // If no name, simply call the base routine.
 176   if (!name)
 177     return fold_range_internal (r, s, NULL_TREE);
 178
 179   if (!gimple_range_ssa_p (name))
 180     return false;
 181
 182   // Check if the stmt has already been processed, and is not stale.
 183   if (m_cache.get_non_stale_global_range (r, name))
 184     return true;
 185
 186   // Otherwise calculate a new value.
 187   int_range_max tmp;
 188   fold_range_internal (tmp, s, name);
 189
 190   // Combine the new value with the old value.  This is required because
 191   // the way value propagation works, when the IL changes on the fly we
 192   // can sometimes get different results.  See PR 97741.
 193   r.intersect (tmp);
 194   m_cache.set_global_range (name, r);
 195
 196   return true;
 197 }
 198
 199 // This routine will export whatever global ranges are known to GCC
 200 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 201
 202 void
 203 gimple_ranger::export_global_ranges ()
 204 {
 205   unsigned x;
 206   int_range_max r;
 207   if (dump_file)
 208     {
 209       fprintf (dump_file, "Exported global range table\n");
 210       fprintf (dump_file, "===========================\n");
 211     }
 212
 213   for ( x = 1; x < num_ssa_names; x++)
 214     {
 215       tree name = ssa_name (x);
 216       if (name && !SSA_NAME_IN_FREE_LIST (name)
 217           && gimple_range_ssa_p (name)
 218           && m_cache.get_global_range (r, name)
 219           && !r.varying_p())
 220         {
 221           bool updated = update_global_range (r, name);
 222
 223           if (updated && dump_file)
 224             {
 225               value_range vr = r;
 226               print_generic_expr (dump_file, name , TDF_SLIM);
 227               fprintf (dump_file, " --> ");
 228               vr.dump (dump_file);
 229               fprintf (dump_file, "\n");
 230               int_range_max same = vr;
 231               if (same != r)
 232                 {
 233                   fprintf (dump_file, "         irange : ");
 234                   r.dump (dump_file);
 235                   fprintf (dump_file, "\n");
 236                 }
 237             }
 238         }
 239     }
 240 }
 241
 242 // Print the known table values to file F.
 243
 244 void
 245 gimple_ranger::dump_bb (FILE *f, basic_block bb)
 246 {
 247   unsigned x;
 248   edge_iterator ei;
 249   edge e;
 250   int_range_max range;
 251   fprintf (f, "\n=========== BB %d ============\n", bb->index);
 252   m_cache.dump_bb (f, bb);
 253
 254   ::dump_bb (f, bb, 4, TDF_NONE);
 255
 256   // Now find any globals defined in this block.
 257   for (x = 1; x < num_ssa_names; x++)
 258     {
 259       tree name = ssa_name (x);
 260       if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) &&
 261           gimple_bb (SSA_NAME_DEF_STMT (name)) == bb &&
 262           m_cache.get_global_range (range, name))
 263         {
 264           if (!range.varying_p ())
 265             {
 266               print_generic_expr (f, name, TDF_SLIM);
 267               fprintf (f, " : ");
 268               range.dump (f);
 269               fprintf (f, "\n");
 270             }
 271
 272         }
 273     }
 274
 275   // And now outgoing edges, if they define anything.
 276   FOR_EACH_EDGE (e, ei, bb->succs)
 277     {
 278       for (x = 1; x < num_ssa_names; x++)
 279         {
 280           tree name = gimple_range_ssa_p (ssa_name (x));
 281           if (name && gori ().has_edge_range_p (name, e)
 282               && m_cache.range_on_edge (range, e, name))
 283             {
 284               gimple *s = SSA_NAME_DEF_STMT (name);
 285               // Only print the range if this is the def block, or
 286               // the on entry cache for either end of the edge is
 287               // set.
 288               if ((s && bb == gimple_bb (s)) ||
 289                   m_cache.block_range (range, bb, name, false) ||
 290                   m_cache.block_range (range, e->dest, name, false))
 291                 {
 292                   m_cache.range_on_edge (range, e, name);
 293                   if (!range.varying_p ())
 294                     {
 295                       fprintf (f, "%d->%d ", e->src->index,
 296                                e->dest->index);
 297                       char c = ' ';
 298                       if (e->flags & EDGE_TRUE_VALUE)
 299                         fprintf (f, " (T)%c", c);
 300                       else if (e->flags & EDGE_FALSE_VALUE)
 301                         fprintf (f, " (F)%c", c);
 302                       else
 303                         fprintf (f, "     ");
 304                       print_generic_expr (f, name, TDF_SLIM);
 305                       fprintf(f, " : \t");
 306                       range.dump(f);
 307                       fprintf (f, "\n");
 308                     }
 309                 }
 310             }
 311         }
 312     }
 313 }
 314
 315 // Print the known table values to file F.
 316
 317 void
 318 gimple_ranger::dump (FILE *f)
 319 {
 320   basic_block bb;
 321
 322   FOR_EACH_BB_FN (bb, cfun)
 323     dump_bb (f, bb);
 324
 325   m_cache.dump (f);
 326 }
 327
 328 // trace_ranger implementation.
 329
 330
 331 trace_ranger::trace_ranger ()
 332 {
 333   indent = 0;
 334   trace_count = 0;
 335 }
 336
 337 // If dumping, return true and print the prefix for the next output line.
 338
 339 bool
 340 trace_ranger::dumping (unsigned counter, bool trailing)
 341 {
 342   if (dump_file && (dump_flags & TDF_DETAILS))
 343     {
 344       // Print counter index as well as INDENT spaces.
 345       if (!trailing)
 346         fprintf (dump_file, " %-7u ", counter);
 347       else
 348         fprintf (dump_file, "         ");
 349       unsigned x;
 350       for (x = 0; x< indent; x++)
 351         fputc (' ', dump_file);
 352       return true;
 353     }
 354   return false;
 355 }
 356
 357 // After calling a routine, if dumping, print the CALLER, NAME, and RESULT,
 358 // returning RESULT.
 359
 360 bool
 361 trace_ranger::trailer (unsigned counter, const char *caller, bool result,
 362                        tree name, const irange &r)
 363 {
 364   if (dumping (counter, true))
 365     {
 366       indent -= bump;
 367       fputs(result ? "TRUE : " : "FALSE : ", dump_file);
 368       fprintf (dump_file, "(%u) ", counter);
 369       fputs (caller, dump_file);
 370       fputs (" (",dump_file);
 371       if (name)
 372         print_generic_expr (dump_file, name, TDF_SLIM);
 373       fputs (") ",dump_file);
 374       if (result)
 375         {
 376           r.dump (dump_file);
 377           fputc('\n', dump_file);
 378         }
 379       else
 380         fputc('\n', dump_file);
 381       // Marks the end of a request.
 382       if (indent == 0)
 383         fputc('\n', dump_file);
 384     }
 385   return result;
 386 }
 387
 388 // Tracing version of range_on_edge.  Call it with printing wrappers.
 389
 390 bool
 391 trace_ranger::range_on_edge (irange &r, edge e, tree name)
 392 {
 393   unsigned idx = ++trace_count;
 394   if (dumping (idx))
 395     {
 396       fprintf (dump_file, "range_on_edge (");
 397       print_generic_expr (dump_file, name, TDF_SLIM);
 398       fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
 399       indent += bump;
 400     }
 401
 402   bool res = gimple_ranger::range_on_edge (r, e, name);
 403   trailer (idx, "range_on_edge", true, name, r);
 404   return res;
 405 }
 406
 407 // Tracing version of range_on_entry.  Call it with printing wrappers.
 408
 409 void
 410 trace_ranger::range_on_entry (irange &r, basic_block bb, tree name)
 411 {
 412   unsigned idx = ++trace_count;
 413   if (dumping (idx))
 414     {
 415       fprintf (dump_file, "range_on_entry (");
 416       print_generic_expr (dump_file, name, TDF_SLIM);
 417       fprintf (dump_file, ") to BB %d\n", bb->index);
 418       indent += bump;
 419     }
 420
 421   gimple_ranger::range_on_entry (r, bb, name);
 422
 423   trailer (idx, "range_on_entry", true, name, r);
 424 }
 425
 426 // Tracing version of range_on_exit.  Call it with printing wrappers.
 427
 428 void
 429 trace_ranger::range_on_exit (irange &r, basic_block bb, tree name)
 430 {
 431   unsigned idx = ++trace_count;
 432   if (dumping (idx))
 433     {
 434       fprintf (dump_file, "range_on_exit (");
 435       print_generic_expr (dump_file, name, TDF_SLIM);
 436       fprintf (dump_file, ") from BB %d\n", bb->index);
 437       indent += bump;
 438     }
 439
 440   gimple_ranger::range_on_exit (r, bb, name);
 441
 442   trailer (idx, "range_on_exit", true, name, r);
 443 }
 444
 445 // Tracing version of range_of_stmt.  Call it with printing wrappers.
 446
 447 bool
 448 trace_ranger::range_of_stmt (irange &r, gimple *s, tree name)
 449 {
 450   bool res;
 451   unsigned idx = ++trace_count;
 452   if (dumping (idx))
 453     {
 454       fprintf (dump_file, "range_of_stmt (");
 455       if (name)
 456         print_generic_expr (dump_file, name, TDF_SLIM);
 457       fputs (") at stmt ", dump_file);
 458       print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
 459       indent += bump;
 460     }
 461
 462   res = gimple_ranger::range_of_stmt (r, s, name);
 463
 464   return trailer (idx, "range_of_stmt", res, name, r);
 465 }
 466
 467 // Tracing version of range_of_expr.  Call it with printing wrappers.
 468
 469 bool
 470 trace_ranger::range_of_expr (irange &r, tree name, gimple *s)
 471 {
 472   bool res;
 473   unsigned idx = ++trace_count;
 474   if (dumping (idx))
 475     {
 476       fprintf (dump_file, "range_of_expr(");
 477       print_generic_expr (dump_file, name, TDF_SLIM);
 478       fputs (")", dump_file);
 479       if (s)
 480         {
 481           fputs (" at stmt ", dump_file);
 482           print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
 483         }
 484       else
 485         fputs ("\n", dump_file);
 486       indent += bump;
 487     }
 488
 489   res = gimple_ranger::range_of_expr (r, name, s);
 490
 491   return trailer (idx, "range_of_expr", res, name, r);
 492 }
 493
 494 gimple_ranger *
 495 enable_ranger (struct function *fun)
 496 {
 497   gimple_ranger *r;
 498
 499   if (param_evrp_mode & EVRP_MODE_TRACE)
 500     r = new trace_ranger;
 501   else
 502     r = new gimple_ranger;
 503
 504   fun->x_range_query = r;
 505
 506   return r;
 507 }
 508
 509 void
 510 disable_ranger (struct function *fun)
 511 {
 512   delete fun->x_range_query;
 513
 514   fun->x_range_query = &global_ranges;
 515 }
 516
 517 // =========================================
 518 // Debugging helpers.
 519 // =========================================
 520
 521 // Query all statements in the IL to precalculate computable ranges in RANGER.
 522
 523 static DEBUG_FUNCTION void
 524 debug_seed_ranger (gimple_ranger &ranger)
 525 {
 526   // Recalculate SCEV to make sure the dump lists everything.
 527   if (scev_initialized_p ())
 528     {
 529       scev_finalize ();
 530       scev_initialize ();
 531     }
 532
 533   basic_block bb;
 534   int_range_max r;
 535   gimple_stmt_iterator gsi;
 536   FOR_EACH_BB_FN (bb, cfun)
 537     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 538       {
 539         gimple *stmt = gsi_stmt (gsi);
 540
 541         if (is_gimple_debug (stmt))
 542           continue;
 543
 544         ranger.range_of_stmt (r, stmt);
 545       }
 546 }
 547
 548 // Dump all that ranger knows for the current function.
 549
 550 DEBUG_FUNCTION void
 551 dump_ranger (FILE *out)
 552 {
 553   gimple_ranger ranger;
 554   debug_seed_ranger (ranger);
 555   ranger.dump (out);
 556 }
 557
 558 DEBUG_FUNCTION void
 559 debug_ranger ()
 560 {
 561   dump_ranger (stderr);
 562 }
 563
 564 // Dump all that ranger knows on a path of BBs.
 565 //
 566 // Note that the blocks are in reverse order, thus the exit block is
 567 // path[0].
 568
 569 DEBUG_FUNCTION void
 570 dump_ranger (FILE *dump_file, const vec<basic_block> &path)
 571 {
 572   if (path.length () == 0)
 573     {
 574       fprintf (dump_file, "empty\n");
 575       return;
 576     }
 577
 578   gimple_ranger ranger;
 579   debug_seed_ranger (ranger);
 580
 581   unsigned i = path.length ();
 582   do
 583     {
 584       i--;
 585       ranger.dump_bb (dump_file, path[i]);
 586     }
 587   while (i > 0);
 588 }
 589
 590 DEBUG_FUNCTION void
 591 debug_ranger (const vec<basic_block> &path)
 592 {
 593   dump_ranger (stderr, path);
 594 }
 595
 596 #include "gimple-range-tests.cc"