gcc/gimple-range.cc

   1 /* Code for GIMPLE range related routines.
   2    Copyright (C) 2019-2022 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 #include "gimple-walk.h"
  39
  40 gimple_ranger::gimple_ranger () :
  41         non_executable_edge_flag (cfun),
  42         m_cache (non_executable_edge_flag),
  43         tracer (""),
  44         current_bb (NULL)
  45 {
  46   // If the cache has a relation oracle, use it.
  47   m_oracle = m_cache.oracle ();
  48   if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
  49     tracer.enable_trace ();
  50   m_stmt_list.create (0);
  51   m_stmt_list.safe_grow (num_ssa_names);
  52   m_stmt_list.truncate (0);
  53
  54   // Ensure the not_executable flag is clear everywhere.
  55   if (flag_checking)
  56     {
  57       basic_block bb;
  58       FOR_ALL_BB_FN (bb, cfun)
  59         {
  60           edge_iterator ei;
  61           edge e;
  62           FOR_EACH_EDGE (e, ei, bb->succs)
  63             gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
  64         }
  65     }
  66 }
  67
  68 gimple_ranger::~gimple_ranger ()
  69 {
  70   m_stmt_list.release ();
  71 }
  72
  73 bool
  74 gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
  75 {
  76   unsigned idx;
  77   if (!gimple_range_ssa_p (expr))
  78     return get_tree_range (r, expr, stmt);
  79
  80   if ((idx = tracer.header ("range_of_expr(")))
  81     {
  82       print_generic_expr (dump_file, expr, TDF_SLIM);
  83       fputs (")", dump_file);
  84       if (stmt)
  85         {
  86           fputs (" at stmt ", dump_file);
  87           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
  88         }
  89       else
  90         fputs ("\n", dump_file);
  91     }
  92
  93   // If there is no statement, just get the global value.
  94   if (!stmt)
  95     {
  96       int_range_max tmp;
  97       m_cache.get_global_range (r, expr);
  98       // Pick up implied context information from the on-entry cache
  99       // if current_bb is set.  Do not attempt any new calculations.
 100       if (current_bb && m_cache.block_range (tmp, current_bb, expr, false))
 101         {
 102           r.intersect (tmp);
 103           char str[80];
 104           sprintf (str, "picked up range from bb %d\n",current_bb->index);
 105           if (idx)
 106             tracer.print (idx, str);
 107         }
 108     }
 109   // For a debug stmt, pick the best value currently available, do not
 110   // trigger new value calculations.  PR 100781.
 111   else if (is_gimple_debug (stmt))
 112     m_cache.range_of_expr (r, expr, stmt);
 113   else
 114     {
 115       basic_block bb = gimple_bb (stmt);
 116       gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
 117
 118       // If name is defined in this block, try to get an range from S.
 119       if (def_stmt && gimple_bb (def_stmt) == bb)
 120         {
 121           // Check for a definition override from a block walk.
 122           if (!POINTER_TYPE_P (TREE_TYPE (expr))
 123               || !m_cache.block_range (r, bb, expr, false))
 124             range_of_stmt (r, def_stmt, expr);
 125         }
 126       // Otherwise OP comes from outside this block, use range on entry.
 127       else
 128         range_on_entry (r, bb, expr);
 129     }
 130   if (idx)
 131     tracer.trailer (idx, "range_of_expr", true, expr, r);
 132   return true;
 133 }
 134
 135 // Return the range of NAME on entry to block BB in R.
 136
 137 void
 138 gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
 139 {
 140   int_range_max entry_range;
 141   gcc_checking_assert (gimple_range_ssa_p (name));
 142
 143   unsigned idx;
 144   if ((idx = tracer.header ("range_on_entry (")))
 145     {
 146       print_generic_expr (dump_file, name, TDF_SLIM);
 147       fprintf (dump_file, ") to BB %d\n", bb->index);
 148     }
 149
 150   // Start with any known range
 151   range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
 152
 153   // Now see if there is any on_entry value which may refine it.
 154   if (m_cache.block_range (entry_range, bb, name))
 155     r.intersect (entry_range);
 156
 157   if (dom_info_available_p (CDI_DOMINATORS))
 158     {
 159       basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
 160       if (dom_bb)
 161         m_cache.m_non_null.adjust_range (r, name, dom_bb, true);
 162     }
 163
 164   if (idx)
 165     tracer.trailer (idx, "range_on_entry", true, name, r);
 166 }
 167
 168 // Calculate the range for NAME at the end of block BB and return it in R.
 169 // Return false if no range can be calculated.
 170
 171 void
 172 gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name)
 173 {
 174   // on-exit from the exit block?
 175   gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
 176   gcc_checking_assert (gimple_range_ssa_p (name));
 177
 178   unsigned idx;
 179   if ((idx = tracer.header ("range_on_exit (")))
 180     {
 181       print_generic_expr (dump_file, name, TDF_SLIM);
 182       fprintf (dump_file, ") from BB %d\n", bb->index);
 183     }
 184
 185   gimple *s = SSA_NAME_DEF_STMT (name);
 186   basic_block def_bb = gimple_bb (s);
 187   // If this is not the definition block, get the range on the last stmt in
 188   // the block... if there is one.
 189   if (def_bb != bb)
 190     s = last_stmt (bb);
 191   // If there is no statement provided, get the range_on_entry for this block.
 192   if (s)
 193     range_of_expr (r, name, s);
 194   else
 195     range_on_entry (r, bb, name);
 196   gcc_checking_assert (r.undefined_p ()
 197                        || range_compatible_p (r.type (), TREE_TYPE (name)));
 198
 199   if (idx)
 200     tracer.trailer (idx, "range_on_exit", true, name, r);
 201 }
 202
 203 // Calculate a range for NAME on edge E and return it in R.
 204
 205 bool
 206 gimple_ranger::range_on_edge (irange &r, edge e, tree name)
 207 {
 208   int_range_max edge_range;
 209   gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));
 210
 211   // Do not process values along abnormal edges.
 212   if (e->flags & EDGE_ABNORMAL)
 213     return get_tree_range (r, name, NULL);
 214
 215   unsigned idx;
 216   if ((idx = tracer.header ("range_on_edge (")))
 217     {
 218       print_generic_expr (dump_file, name, TDF_SLIM);
 219       fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
 220     }
 221
 222   // Check to see if the edge is executable.
 223   if ((e->flags & non_executable_edge_flag))
 224     {
 225       r.set_undefined ();
 226       if (idx)
 227         tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
 228                         name, r);
 229       return true;
 230     }
 231
 232   bool res = true;
 233   if (!gimple_range_ssa_p (name))
 234     res = get_tree_range (r, name, NULL);
 235   else
 236     {
 237       range_on_exit (r, e->src, name);
 238       // If this is not an abnormal edge, check for a non-null exit .
 239       if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
 240         m_cache.m_non_null.adjust_range (r, name, e->src, false);
 241       gcc_checking_assert  (r.undefined_p ()
 242                             || range_compatible_p (r.type(), TREE_TYPE (name)));
 243
 244       // Check to see if NAME is defined on edge e.
 245       if (m_cache.range_on_edge (edge_range, e, name))
 246         r.intersect (edge_range);
 247     }
 248
 249   if (idx)
 250     tracer.trailer (idx, "range_on_edge", res, name, r);
 251   return res;
 252 }
 253
 254 // fold_range wrapper for range_of_stmt to use as an internal client.
 255
 256 bool
 257 gimple_ranger::fold_range_internal (irange &r, gimple *s, tree name)
 258 {
 259   fold_using_range f;
 260   fur_depend src (s, &(gori ()), this);
 261   return f.fold_stmt (r, s, src, name);
 262 }
 263
 264 // Calculate a range for statement S and return it in R.  If NAME is
 265 // provided it represents the SSA_NAME on the LHS of the statement.
 266 // It is only required if there is more than one lhs/output.  Check
 267 // the global cache for NAME first to see if the evaluation can be
 268 // avoided.  If a range cannot be calculated, return false and UNDEFINED.
 269
 270 bool
 271 gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
 272 {
 273   bool res;
 274   r.set_undefined ();
 275
 276   unsigned idx;
 277   if ((idx = tracer.header ("range_of_stmt (")))
 278     {
 279       if (name)
 280         print_generic_expr (dump_file, name, TDF_SLIM);
 281       fputs (") at stmt ", dump_file);
 282       print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
 283     }
 284
 285   if (!name)
 286     name = gimple_get_lhs (s);
 287
 288   // If no name, simply call the base routine.
 289   if (!name)
 290     {
 291       res = fold_range_internal (r, s, NULL_TREE);
 292       if (res && is_a <gcond *> (s))
 293         {
 294           // Update any exports in the cache if this is a gimple cond statement.
 295           tree exp;
 296           basic_block bb = gimple_bb (s);
 297           FOR_EACH_GORI_EXPORT_NAME (m_cache.m_gori, bb, exp)
 298             m_cache.propagate_updated_value (exp, bb);
 299         }
 300     }
 301   else if (!gimple_range_ssa_p (name))
 302     res = get_tree_range (r, name, NULL);
 303   else
 304     {
 305       bool current;
 306       // Check if the stmt has already been processed.
 307       if (m_cache.get_global_range (r, name, current))
 308         {
 309           // If it isn't stale, use this cached value.
 310           if (current)
 311             {
 312               if (idx)
 313                 tracer.trailer (idx, " cached", true, name, r);
 314               return true;
 315             }
 316         }
 317       else
 318         prefill_stmt_dependencies (name);
 319
 320       // Calculate a new value.
 321       int_range_max tmp;
 322       fold_range_internal (tmp, s, name);
 323
 324       // Combine the new value with the old value.  This is required because
 325       // the way value propagation works, when the IL changes on the fly we
 326       // can sometimes get different results.  See PR 97741.
 327       r.intersect (tmp);
 328       m_cache.set_global_range (name, r);
 329       res = true;
 330     }
 331
 332   if (idx)
 333     tracer.trailer (idx, "range_of_stmt", res, name, r);
 334   return res;
 335 }
 336
 337
 338 // Check if NAME is a dependency that needs resolving, and push it on the
 339 // stack if so.  R is a scratch range.
 340
 341 inline void
 342 gimple_ranger::prefill_name (irange &r, tree name)
 343 {
 344   if (!gimple_range_ssa_p (name))
 345     return;
 346   gimple *stmt = SSA_NAME_DEF_STMT (name);
 347   if (!gimple_range_handler (stmt) && !is_a<gphi *> (stmt))
 348     return;
 349
 350   bool current;
 351   // If this op has not been processed yet, then push it on the stack
 352   if (!m_cache.get_global_range (r, name, current))
 353     m_stmt_list.safe_push (name);
 354 }
 355
 356 // This routine will seed the global cache with most of the depnedencies of
 357 // NAME.  This prevents excessive call depth through the normal API.
 358
 359 void
 360 gimple_ranger::prefill_stmt_dependencies (tree ssa)
 361 {
 362   if (SSA_NAME_IS_DEFAULT_DEF (ssa))
 363     return;
 364
 365   int_range_max r;
 366   unsigned idx;
 367   gimple *stmt = SSA_NAME_DEF_STMT (ssa);
 368   gcc_checking_assert (stmt && gimple_bb (stmt));
 369
 370   // Only pre-process range-ops and phis.
 371   if (!gimple_range_handler (stmt) && !is_a<gphi *> (stmt))
 372     return;
 373
 374   // Mark where on the stack we are starting.
 375   unsigned start = m_stmt_list.length ();
 376   m_stmt_list.safe_push (ssa);
 377
 378   idx = tracer.header ("ROS dependence fill\n");
 379
 380   // Loop until back at the start point.
 381   while (m_stmt_list.length () > start)
 382     {
 383       tree name = m_stmt_list.last ();
 384       // NULL is a marker which indicates the next name in the stack has now
 385       // been fully resolved, so we can fold it.
 386       if (!name)
 387         {
 388           // Pop the NULL, then pop the name.
 389           m_stmt_list.pop ();
 390           name = m_stmt_list.pop ();
 391           // Don't fold initial request, it will be calculated upon return.
 392           if (m_stmt_list.length () > start)
 393             {
 394               // Fold and save the value for NAME.
 395               stmt = SSA_NAME_DEF_STMT (name);
 396               fold_range_internal (r, stmt, name);
 397               // Make sure we don't lose any current global info.
 398               int_range_max tmp;
 399               m_cache.get_global_range (tmp, name);
 400               r.intersect (tmp);
 401               m_cache.set_global_range (name, r);
 402             }
 403           continue;
 404         }
 405
 406       // Add marker indicating previous NAME in list should be folded
 407       // when we get to this NULL.
 408       m_stmt_list.safe_push (NULL_TREE);
 409       stmt = SSA_NAME_DEF_STMT (name);
 410
 411       if (idx)
 412         {
 413           tracer.print (idx, "ROS dep fill (");
 414           print_generic_expr (dump_file, name, TDF_SLIM);
 415           fputs (") at stmt ", dump_file);
 416           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 417         }
 418
 419       gphi *phi = dyn_cast <gphi *> (stmt);
 420       if (phi)
 421         {
 422           for (unsigned x = 0; x < gimple_phi_num_args (phi); x++)
 423             prefill_name (r, gimple_phi_arg_def (phi, x));
 424         }
 425       else
 426         {
 427           gcc_checking_assert (gimple_range_handler (stmt));
 428           tree op = gimple_range_operand2 (stmt);
 429           if (op)
 430             prefill_name (r, op);
 431           op = gimple_range_operand1 (stmt);
 432           if (op)
 433             prefill_name (r, op);
 434         }
 435     }
 436   if (idx)
 437     tracer.trailer (idx, "ROS ", false, ssa, r);
 438 }
 439
 440
 441 // This routine will invoke the gimple fold_stmt routine, providing context to
 442 // range_of_expr calls via an private interal API.
 443
 444 bool
 445 gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
 446 {
 447   gimple *stmt = gsi_stmt (*gsi);
 448   current_bb = gimple_bb (stmt);
 449   bool ret = ::fold_stmt (gsi, valueize);
 450   current_bb = NULL;
 451   return ret;
 452 }
 453
 454 // Called during dominator walks to register any side effects that take effect
 455 // from this point forward.  Current release is only for tracking non-null
 456 // within a block.
 457
 458 void
 459 gimple_ranger::register_side_effects (gimple *s)
 460 {
 461   m_cache.block_apply_nonnull (s);
 462 }
 463
 464 // This routine will export whatever global ranges are known to GCC
 465 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 466
 467 void
 468 gimple_ranger::export_global_ranges ()
 469 {
 470   /* Cleared after the table header has been printed.  */
 471   bool print_header = true;
 472   for (unsigned x = 1; x < num_ssa_names; x++)
 473     {
 474       int_range_max r;
 475       tree name = ssa_name (x);
 476       if (name && !SSA_NAME_IN_FREE_LIST (name)
 477           && gimple_range_ssa_p (name)
 478           && m_cache.get_global_range (r, name)
 479           && !r.varying_p())
 480         {
 481           bool updated = update_global_range (r, name);
 482           if (!updated || !dump_file)
 483             continue;
 484
 485           if (print_header)
 486             {
 487               /* Print the header only when there's something else
 488                  to print below.  */
 489               fprintf (dump_file, "Exported global range table:\n");
 490               fprintf (dump_file, "============================\n");
 491               print_header = false;
 492             }
 493
 494           value_range vr = r;
 495           print_generic_expr (dump_file, name , TDF_SLIM);
 496           fprintf (dump_file, "  : ");
 497           vr.dump (dump_file);
 498           fprintf (dump_file, "\n");
 499           int_range_max same = vr;
 500           if (same != r)
 501             {
 502               fprintf (dump_file, "         irange : ");
 503               r.dump (dump_file);
 504               fprintf (dump_file, "\n");
 505             }
 506         }
 507     }
 508 }
 509
 510 // Print the known table values to file F.
 511
 512 void
 513 gimple_ranger::dump_bb (FILE *f, basic_block bb)
 514 {
 515   unsigned x;
 516   edge_iterator ei;
 517   edge e;
 518   int_range_max range, tmp_range;
 519   fprintf (f, "\n=========== BB %d ============\n", bb->index);
 520   m_cache.dump_bb (f, bb);
 521
 522   ::dump_bb (f, bb, 4, TDF_NONE);
 523
 524   // Now find any globals defined in this block.
 525   for (x = 1; x < num_ssa_names; x++)
 526     {
 527       tree name = ssa_name (x);
 528       if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) &&
 529           gimple_bb (SSA_NAME_DEF_STMT (name)) == bb &&
 530           m_cache.get_global_range (range, name))
 531         {
 532           if (!range.varying_p ())
 533             {
 534               print_generic_expr (f, name, TDF_SLIM);
 535               fprintf (f, " : ");
 536               range.dump (f);
 537               fprintf (f, "\n");
 538             }
 539
 540         }
 541     }
 542
 543   // And now outgoing edges, if they define anything.
 544   FOR_EACH_EDGE (e, ei, bb->succs)
 545     {
 546       for (x = 1; x < num_ssa_names; x++)
 547         {
 548           tree name = gimple_range_ssa_p (ssa_name (x));
 549           if (name && gori ().has_edge_range_p (name, e)
 550               && m_cache.range_on_edge (range, e, name))
 551             {
 552               gimple *s = SSA_NAME_DEF_STMT (name);
 553               // Only print the range if this is the def block, or
 554               // the on entry cache for either end of the edge is
 555               // set.
 556               if ((s && bb == gimple_bb (s)) ||
 557                   m_cache.block_range (tmp_range, bb, name, false) ||
 558                   m_cache.block_range (tmp_range, e->dest, name, false))
 559                 {
 560                   if (!range.varying_p ())
 561                     {
 562                       fprintf (f, "%d->%d ", e->src->index,
 563                                e->dest->index);
 564                       char c = ' ';
 565                       if (e->flags & EDGE_TRUE_VALUE)
 566                         fprintf (f, " (T)%c", c);
 567                       else if (e->flags & EDGE_FALSE_VALUE)
 568                         fprintf (f, " (F)%c", c);
 569                       else
 570                         fprintf (f, "     ");
 571                       print_generic_expr (f, name, TDF_SLIM);
 572                       fprintf(f, " : \t");
 573                       range.dump(f);
 574                       fprintf (f, "\n");
 575                     }
 576                 }
 577             }
 578         }
 579     }
 580 }
 581
 582 // Print the known table values to file F.
 583
 584 void
 585 gimple_ranger::dump (FILE *f)
 586 {
 587   basic_block bb;
 588
 589   FOR_EACH_BB_FN (bb, cfun)
 590     dump_bb (f, bb);
 591
 592   m_cache.dump (f);
 593 }
 594
 595 void
 596 gimple_ranger::debug ()
 597 {
 598   dump (stderr);
 599 }
 600
 601 /* Create a new ranger instance and associate it with function FUN.
 602    Each call must be paired with a call to disable_ranger to release
 603    resources.  */
 604
 605 gimple_ranger *
 606 enable_ranger (struct function *fun)
 607 {
 608   gimple_ranger *r;
 609
 610   gcc_checking_assert (!fun->x_range_query);
 611   r = new gimple_ranger;
 612   fun->x_range_query = r;
 613
 614   return r;
 615 }
 616
 617 /* Destroy and release the ranger instance associated with function FUN
 618    and replace it the global ranger.  */
 619
 620 void
 621 disable_ranger (struct function *fun)
 622 {
 623   gcc_checking_assert (fun->x_range_query);
 624   delete fun->x_range_query;
 625   fun->x_range_query = NULL;
 626 }