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