gcc/gimple-range.cc

   1 /* Code for GIMPLE range related routines.
   2    Copyright (C) 2019-2023 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 (bool use_imm_uses) :
  41         non_executable_edge_flag (cfun),
  42         m_cache (non_executable_edge_flag, use_imm_uses),
  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 (vrange &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       Value_Range tmp (TREE_TYPE (expr));
  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           // Declared in this block, if it has a global set, check for an
 122           // override from a block walk, otherwise calculate it.
 123           if (m_cache.get_global_range (r, expr))
 124             m_cache.block_range (r, bb, expr, false);
 125           else
 126             range_of_stmt (r, def_stmt, expr);
 127         }
 128       // Otherwise OP comes from outside this block, use range on entry.
 129       else
 130         range_on_entry (r, bb, expr);
 131     }
 132   if (idx)
 133     tracer.trailer (idx, "range_of_expr", true, expr, r);
 134   return true;
 135 }
 136
 137 // Return the range of NAME on entry to block BB in R.
 138
 139 void
 140 gimple_ranger::range_on_entry (vrange &r, basic_block bb, tree name)
 141 {
 142   Value_Range entry_range (TREE_TYPE (name));
 143   gcc_checking_assert (gimple_range_ssa_p (name));
 144
 145   unsigned idx;
 146   if ((idx = tracer.header ("range_on_entry (")))
 147     {
 148       print_generic_expr (dump_file, name, TDF_SLIM);
 149       fprintf (dump_file, ") to BB %d\n", bb->index);
 150     }
 151
 152   // Start with any known range
 153   range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
 154
 155   // Now see if there is any on_entry value which may refine it.
 156   if (m_cache.block_range (entry_range, bb, name))
 157     r.intersect (entry_range);
 158
 159   if (idx)
 160     tracer.trailer (idx, "range_on_entry", true, name, r);
 161 }
 162
 163 // Calculate the range for NAME at the end of block BB and return it in R.
 164 // Return false if no range can be calculated.
 165
 166 void
 167 gimple_ranger::range_on_exit (vrange &r, basic_block bb, tree name)
 168 {
 169   // on-exit from the exit block?
 170   gcc_checking_assert (gimple_range_ssa_p (name));
 171
 172   unsigned idx;
 173   if ((idx = tracer.header ("range_on_exit (")))
 174     {
 175       print_generic_expr (dump_file, name, TDF_SLIM);
 176       fprintf (dump_file, ") from BB %d\n", bb->index);
 177     }
 178
 179   gimple *s = SSA_NAME_DEF_STMT (name);
 180   basic_block def_bb = gimple_bb (s);
 181   // If this is not the definition block, get the range on the last stmt in
 182   // the block... if there is one.
 183   if (def_bb != bb)
 184     s = last_stmt (bb);
 185   // If there is no statement provided, get the range_on_entry for this block.
 186   if (s)
 187     range_of_expr (r, name, s);
 188   else
 189     range_on_entry (r, bb, name);
 190   gcc_checking_assert (r.undefined_p ()
 191                        || range_compatible_p (r.type (), TREE_TYPE (name)));
 192
 193   if (idx)
 194     tracer.trailer (idx, "range_on_exit", true, name, r);
 195 }
 196
 197 // Calculate a range for NAME on edge E and return it in R.
 198
 199 bool
 200 gimple_ranger::range_on_edge (vrange &r, edge e, tree name)
 201 {
 202   Value_Range edge_range (TREE_TYPE (name));
 203
 204   if (!r.supports_type_p (TREE_TYPE (name)))
 205     return false;
 206
 207   // Do not process values along abnormal edges.
 208   if (e->flags & EDGE_ABNORMAL)
 209     return get_tree_range (r, name, NULL);
 210
 211   unsigned idx;
 212   if ((idx = tracer.header ("range_on_edge (")))
 213     {
 214       print_generic_expr (dump_file, name, TDF_SLIM);
 215       fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
 216     }
 217
 218   // Check to see if the edge is executable.
 219   if ((e->flags & non_executable_edge_flag))
 220     {
 221       r.set_undefined ();
 222       if (idx)
 223         tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
 224                         name, r);
 225       return true;
 226     }
 227
 228   bool res = true;
 229   if (!gimple_range_ssa_p (name))
 230     res = get_tree_range (r, name, NULL);
 231   else
 232     {
 233       range_on_exit (r, e->src, name);
 234       // If this is not an abnormal edge, check for a non-null exit .
 235       if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
 236         m_cache.m_exit.maybe_adjust_range (r, name, e->src);
 237       gcc_checking_assert  (r.undefined_p ()
 238                             || range_compatible_p (r.type(), TREE_TYPE (name)));
 239
 240       // Check to see if NAME is defined on edge e.
 241       if (m_cache.range_on_edge (edge_range, e, name))
 242         r.intersect (edge_range);
 243     }
 244
 245   if (idx)
 246     tracer.trailer (idx, "range_on_edge", res, name, r);
 247   return res;
 248 }
 249
 250 // fold_range wrapper for range_of_stmt to use as an internal client.
 251
 252 bool
 253 gimple_ranger::fold_range_internal (vrange &r, gimple *s, tree name)
 254 {
 255   fold_using_range f;
 256   fur_depend src (s, &(gori ()), this);
 257   return f.fold_stmt (r, s, src, name);
 258 }
 259
 260 // Calculate a range for statement S and return it in R.  If NAME is
 261 // provided it represents the SSA_NAME on the LHS of the statement.
 262 // It is only required if there is more than one lhs/output.  Check
 263 // the global cache for NAME first to see if the evaluation can be
 264 // avoided.  If a range cannot be calculated, return false and UNDEFINED.
 265
 266 bool
 267 gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
 268 {
 269   bool res;
 270   r.set_undefined ();
 271
 272   unsigned idx;
 273   if ((idx = tracer.header ("range_of_stmt (")))
 274     {
 275       if (name)
 276         print_generic_expr (dump_file, name, TDF_SLIM);
 277       fputs (") at stmt ", dump_file);
 278       print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
 279     }
 280
 281   if (!name)
 282     name = gimple_get_lhs (s);
 283
 284   // If no name, simply call the base routine.
 285   if (!name)
 286     {
 287       res = fold_range_internal (r, s, NULL_TREE);
 288       if (res && is_a <gcond *> (s))
 289         {
 290           // Update any exports in the cache if this is a gimple cond statement.
 291           tree exp;
 292           basic_block bb = gimple_bb (s);
 293           FOR_EACH_GORI_EXPORT_NAME (m_cache.m_gori, bb, exp)
 294             m_cache.propagate_updated_value (exp, bb);
 295         }
 296     }
 297   else if (!gimple_range_ssa_p (name))
 298     res = get_tree_range (r, name, NULL);
 299   else
 300     {
 301       bool current;
 302       // Check if the stmt has already been processed.
 303       if (m_cache.get_global_range (r, name, current))
 304         {
 305           // If it isn't stale, use this cached value.
 306           if (current)
 307             {
 308               if (idx)
 309                 tracer.trailer (idx, " cached", true, name, r);
 310               return true;
 311             }
 312         }
 313       else
 314         prefill_stmt_dependencies (name);
 315
 316       // Calculate a new value.
 317       Value_Range tmp (TREE_TYPE (name));
 318       fold_range_internal (tmp, s, name);
 319
 320       // Combine the new value with the old value.  This is required because
 321       // the way value propagation works, when the IL changes on the fly we
 322       // can sometimes get different results.  See PR 97741.
 323       r.intersect (tmp);
 324       m_cache.set_global_range (name, r);
 325       res = true;
 326     }
 327
 328   if (idx)
 329     tracer.trailer (idx, "range_of_stmt", res, name, r);
 330   return res;
 331 }
 332
 333
 334 // Check if NAME is a dependency that needs resolving, and push it on the
 335 // stack if so.  R is a scratch range.
 336
 337 inline void
 338 gimple_ranger::prefill_name (vrange &r, tree name)
 339 {
 340   if (!gimple_range_ssa_p (name))
 341     return;
 342   gimple *stmt = SSA_NAME_DEF_STMT (name);
 343   if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
 344     return;
 345
 346   bool current;
 347   // If this op has not been processed yet, then push it on the stack
 348   if (!m_cache.get_global_range (r, name, current))
 349     m_stmt_list.safe_push (name);
 350 }
 351
 352 // This routine will seed the global cache with most of the dependencies of
 353 // NAME.  This prevents excessive call depth through the normal API.
 354
 355 void
 356 gimple_ranger::prefill_stmt_dependencies (tree ssa)
 357 {
 358   if (SSA_NAME_IS_DEFAULT_DEF (ssa))
 359     return;
 360
 361   unsigned idx;
 362   gimple *stmt = SSA_NAME_DEF_STMT (ssa);
 363   gcc_checking_assert (stmt && gimple_bb (stmt));
 364
 365   // Only pre-process range-ops and phis.
 366   if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
 367     return;
 368
 369   // Mark where on the stack we are starting.
 370   unsigned start = m_stmt_list.length ();
 371   m_stmt_list.safe_push (ssa);
 372
 373   idx = tracer.header ("ROS dependence fill\n");
 374
 375   // Loop until back at the start point.
 376   while (m_stmt_list.length () > start)
 377     {
 378       tree name = m_stmt_list.last ();
 379       // NULL is a marker which indicates the next name in the stack has now
 380       // been fully resolved, so we can fold it.
 381       if (!name)
 382         {
 383           // Pop the NULL, then pop the name.
 384           m_stmt_list.pop ();
 385           name = m_stmt_list.pop ();
 386           // Don't fold initial request, it will be calculated upon return.
 387           if (m_stmt_list.length () > start)
 388             {
 389               // Fold and save the value for NAME.
 390               stmt = SSA_NAME_DEF_STMT (name);
 391               Value_Range r (TREE_TYPE (name));
 392               fold_range_internal (r, stmt, name);
 393               // Make sure we don't lose any current global info.
 394               Value_Range tmp (TREE_TYPE (name));
 395               m_cache.get_global_range (tmp, name);
 396               r.intersect (tmp);
 397               m_cache.set_global_range (name, r);
 398             }
 399           continue;
 400         }
 401
 402       // Add marker indicating previous NAME in list should be folded
 403       // when we get to this NULL.
 404       m_stmt_list.safe_push (NULL_TREE);
 405       stmt = SSA_NAME_DEF_STMT (name);
 406
 407       if (idx)
 408         {
 409           tracer.print (idx, "ROS dep fill (");
 410           print_generic_expr (dump_file, name, TDF_SLIM);
 411           fputs (") at stmt ", dump_file);
 412           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 413         }
 414
 415       gphi *phi = dyn_cast <gphi *> (stmt);
 416       if (phi)
 417         {
 418           Value_Range r (TREE_TYPE (gimple_phi_result (phi)));
 419           for (unsigned x = 0; x < gimple_phi_num_args (phi); x++)
 420             prefill_name (r, gimple_phi_arg_def (phi, x));
 421         }
 422       else
 423         {
 424           gimple_range_op_handler handler (stmt);
 425           if (handler)
 426             {
 427               tree op = handler.operand2 ();
 428               if (op)
 429                 {
 430                   Value_Range r (TREE_TYPE (op));
 431                   prefill_name (r, op);
 432                 }
 433               op = handler.operand1 ();
 434               if (op)
 435                 {
 436                   Value_Range r (TREE_TYPE (op));
 437                   prefill_name (r, op);
 438                 }
 439             }
 440         }
 441     }
 442   if (idx)
 443     {
 444       unsupported_range r;
 445       tracer.trailer (idx, "ROS ", false, ssa, r);
 446     }
 447 }
 448
 449
 450 // This routine will invoke the gimple fold_stmt routine, providing context to
 451 // range_of_expr calls via an private internal API.
 452
 453 bool
 454 gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
 455 {
 456   gimple *stmt = gsi_stmt (*gsi);
 457   current_bb = gimple_bb (stmt);
 458   bool ret = ::fold_stmt (gsi, valueize);
 459   current_bb = NULL;
 460   return ret;
 461 }
 462
 463 // Called during dominator walks to register any inferred ranges that take
 464 // effect from this point forward.
 465
 466 void
 467 gimple_ranger::register_inferred_ranges (gimple *s)
 468 {
 469   // First, export the LHS if it is a new global range.
 470   tree lhs = gimple_get_lhs (s);
 471   if (lhs)
 472     {
 473       Value_Range tmp (TREE_TYPE (lhs));
 474       if (range_of_stmt (tmp, s, lhs) && !tmp.varying_p ()
 475           && set_range_info (lhs, tmp) && dump_file)
 476         {
 477           fprintf (dump_file, "Global Exported: ");
 478           print_generic_expr (dump_file, lhs, TDF_SLIM);
 479           fprintf (dump_file, " = ");
 480           tmp.dump (dump_file);
 481           fputc ('\n', dump_file);
 482         }
 483     }
 484   m_cache.apply_inferred_ranges (s);
 485 }
 486
 487 // This function will walk the statements in BB to determine if any
 488 // discovered inferred ranges in the block have any transitive effects,
 489 // and if so, register those effects in BB.
 490
 491 void
 492 gimple_ranger::register_transitive_inferred_ranges (basic_block bb)
 493 {
 494   // Return if there are no inferred ranges in BB.
 495   infer_range_manager &infer = m_cache.m_exit;
 496   if (!infer.has_range_p (bb))
 497     return;
 498
 499   if (dump_file && (dump_flags & TDF_DETAILS))
 500     fprintf (dump_file, "Checking for transitive inferred ranges in BB %d\n",
 501              bb->index);
 502
 503   for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
 504        gsi_next (&si))
 505     {
 506       gimple *s = gsi_stmt (si);
 507       tree lhs = gimple_get_lhs (s);
 508       // If the LHS already has an inferred effect, leave it be.
 509       if (!gimple_range_ssa_p (lhs) || infer.has_range_p (lhs, bb))
 510         continue;
 511       // Pick up global value.
 512       Value_Range g (TREE_TYPE (lhs));
 513       range_of_expr (g, lhs);
 514
 515       // If either dependency has an inferred range, check if recalculating
 516       // the LHS is different than the global value. If so, register it as
 517       // an inferred range as well.
 518       Value_Range r (TREE_TYPE (lhs));
 519       r.set_undefined ();
 520       tree name1 = gori ().depend1 (lhs);
 521       tree name2 = gori ().depend2 (lhs);
 522       if ((name1 && infer.has_range_p (name1, bb))
 523           || (name2 && infer.has_range_p (name2, bb)))
 524         {
 525           // Check if folding S produces a different result.
 526           if (fold_range (r, s, this) && g != r)
 527             {
 528               infer.add_range (lhs, bb, r);
 529               m_cache.register_inferred_value (r, lhs, bb);
 530             }
 531         }
 532     }
 533 }
 534
 535 // When a statement S has changed since the result was cached, re-evaluate
 536 // and update the global cache.
 537
 538 void
 539 gimple_ranger::update_stmt (gimple *s)
 540 {
 541   tree lhs = gimple_get_lhs (s);
 542   if (!lhs || !gimple_range_ssa_p (lhs))
 543     return;
 544   Value_Range r (TREE_TYPE (lhs));
 545   // Only update if it already had a value.
 546   if (m_cache.get_global_range (r, lhs))
 547     {
 548       // Re-calculate a new value using just cache values.
 549       Value_Range tmp (TREE_TYPE (lhs));
 550       fold_using_range f;
 551       fur_stmt src (s, &m_cache);
 552       f.fold_stmt (tmp, s, src, lhs);
 553
 554       // Combine the new value with the old value to check for a change.
 555       if (r.intersect (tmp))
 556         {
 557           if (dump_file && (dump_flags & TDF_DETAILS))
 558             {
 559               print_generic_expr (dump_file, lhs, TDF_SLIM);
 560               fprintf (dump_file, " : global value re-evaluated to ");
 561               r.dump (dump_file);
 562               fputc ('\n', dump_file);
 563             }
 564           m_cache.set_global_range (lhs, r);
 565         }
 566     }
 567 }
 568
 569 // This routine will export whatever global ranges are known to GCC
 570 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 571
 572 void
 573 gimple_ranger::export_global_ranges ()
 574 {
 575   /* Cleared after the table header has been printed.  */
 576   bool print_header = true;
 577   for (unsigned x = 1; x < num_ssa_names; x++)
 578     {
 579       tree name = ssa_name (x);
 580       if (!name)
 581         continue;
 582       Value_Range r (TREE_TYPE (name));
 583       if (name && !SSA_NAME_IN_FREE_LIST (name)
 584           && gimple_range_ssa_p (name)
 585           && m_cache.get_global_range (r, name)
 586           && !r.varying_p())
 587         {
 588           bool updated = set_range_info (name, r);
 589           if (!updated || !dump_file)
 590             continue;
 591
 592           if (print_header)
 593             {
 594               /* Print the header only when there's something else
 595                  to print below.  */
 596               fprintf (dump_file, "Exported global range table:\n");
 597               fprintf (dump_file, "============================\n");
 598               print_header = false;
 599             }
 600
 601           print_generic_expr (dump_file, name , TDF_SLIM);
 602           fprintf (dump_file, "  : ");
 603           r.dump (dump_file);
 604           fprintf (dump_file, "\n");
 605         }
 606     }
 607 }
 608
 609 // Print the known table values to file F.
 610
 611 void
 612 gimple_ranger::dump_bb (FILE *f, basic_block bb)
 613 {
 614   unsigned x;
 615   edge_iterator ei;
 616   edge e;
 617   fprintf (f, "\n=========== BB %d ============\n", bb->index);
 618   m_cache.dump_bb (f, bb);
 619
 620   ::dump_bb (f, bb, 4, TDF_NONE);
 621
 622   // Now find any globals defined in this block.
 623   for (x = 1; x < num_ssa_names; x++)
 624     {
 625       tree name = ssa_name (x);
 626       if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
 627         continue;
 628       Value_Range range (TREE_TYPE (name));
 629       if (gimple_bb (SSA_NAME_DEF_STMT (name)) == bb
 630           && m_cache.get_global_range (range, name))
 631         {
 632           if (!range.varying_p ())
 633             {
 634               print_generic_expr (f, name, TDF_SLIM);
 635               fprintf (f, " : ");
 636               range.dump (f);
 637               fprintf (f, "\n");
 638             }
 639
 640         }
 641     }
 642
 643   // And now outgoing edges, if they define anything.
 644   FOR_EACH_EDGE (e, ei, bb->succs)
 645     {
 646       for (x = 1; x < num_ssa_names; x++)
 647         {
 648           tree name = gimple_range_ssa_p (ssa_name (x));
 649           if (!name || !gori ().has_edge_range_p (name, e))
 650             continue;
 651
 652           Value_Range range (TREE_TYPE (name));
 653           if (m_cache.range_on_edge (range, e, name))
 654             {
 655               gimple *s = SSA_NAME_DEF_STMT (name);
 656               Value_Range tmp_range (TREE_TYPE (name));
 657               // Only print the range if this is the def block, or
 658               // the on entry cache for either end of the edge is
 659               // set.
 660               if ((s && bb == gimple_bb (s)) ||
 661                   m_cache.block_range (tmp_range, bb, name, false) ||
 662                   m_cache.block_range (tmp_range, e->dest, name, false))
 663                 {
 664                   if (!range.varying_p ())
 665                     {
 666                       fprintf (f, "%d->%d ", e->src->index,
 667                                e->dest->index);
 668                       char c = ' ';
 669                       if (e->flags & EDGE_TRUE_VALUE)
 670                         fprintf (f, " (T)%c", c);
 671                       else if (e->flags & EDGE_FALSE_VALUE)
 672                         fprintf (f, " (F)%c", c);
 673                       else
 674                         fprintf (f, "     ");
 675                       print_generic_expr (f, name, TDF_SLIM);
 676                       fprintf(f, " : \t");
 677                       range.dump(f);
 678                       fprintf (f, "\n");
 679                     }
 680                 }
 681             }
 682         }
 683     }
 684 }
 685
 686 // Print the known table values to file F.
 687
 688 void
 689 gimple_ranger::dump (FILE *f)
 690 {
 691   basic_block bb;
 692
 693   FOR_EACH_BB_FN (bb, cfun)
 694     dump_bb (f, bb);
 695
 696   m_cache.dump (f);
 697 }
 698
 699 void
 700 gimple_ranger::debug ()
 701 {
 702   dump (stderr);
 703 }
 704
 705 /* Create a new ranger instance and associate it with function FUN.
 706    Each call must be paired with a call to disable_ranger to release
 707    resources.  */
 708
 709 gimple_ranger *
 710 enable_ranger (struct function *fun, bool use_imm_uses)
 711 {
 712   gimple_ranger *r;
 713
 714   gcc_checking_assert (!fun->x_range_query);
 715   r = new gimple_ranger (use_imm_uses);
 716   fun->x_range_query = r;
 717
 718   return r;
 719 }
 720
 721 /* Destroy and release the ranger instance associated with function FUN
 722    and replace it the global ranger.  */
 723
 724 void
 725 disable_ranger (struct function *fun)
 726 {
 727   gcc_checking_assert (fun->x_range_query);
 728   delete fun->x_range_query;
 729   fun->x_range_query = NULL;
 730 }
 731
 732 // ------------------------------------------------------------------------
 733
 734 // If there is a non-varying value associated with NAME, return true and the
 735 // range in R.
 736
 737 bool
 738 assume_query::assume_range_p (vrange &r, tree name)
 739 {
 740   if (global.get_global_range (r, name))
 741     return !r.varying_p ();
 742   return false;
 743 }
 744
 745 // Query used by GORI to pick up any known value on entry to a block.
 746
 747 bool
 748 assume_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
 749 {
 750   if (!gimple_range_ssa_p (expr))
 751     return get_tree_range (r, expr, stmt);
 752
 753   if (!global.get_global_range (r, expr))
 754     r.set_varying (TREE_TYPE (expr));
 755   return true;
 756 }
 757
 758 // If the current function returns an integral value, and has a single return
 759 // statement, it will calculate any SSA_NAMES it can determine ranges for
 760 // assuming the function returns 1.
 761
 762 assume_query::assume_query ()
 763 {
 764   basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
 765   if (single_pred_p (exit_bb))
 766     {
 767       basic_block bb = single_pred (exit_bb);
 768       gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
 769       if (gsi_end_p (gsi))
 770         return;
 771       gimple *s = gsi_stmt (gsi);
 772       if (!is_a<greturn *> (s))
 773         return;
 774       greturn *gret = as_a<greturn *> (s);
 775       tree op = gimple_return_retval (gret);
 776       if (!gimple_range_ssa_p (op))
 777         return;
 778       tree lhs_type = TREE_TYPE (op);
 779       if (!irange::supports_p (lhs_type))
 780         return;
 781
 782       unsigned prec = TYPE_PRECISION (lhs_type);
 783       int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec));
 784       global.set_global_range (op, lhs_range);
 785
 786       gimple *def = SSA_NAME_DEF_STMT (op);
 787       if (!def || gimple_get_lhs (def) != op)
 788         return;
 789       fur_stmt src (gret, this);
 790       calculate_stmt (def, lhs_range, src);
 791     }
 792 }
 793
 794 // Evaluate operand OP on statement S, using the provided LHS range.
 795 // If successful, set the range in the global table, then visit OP's def stmt.
 796
 797 void
 798 assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src)
 799 {
 800   Value_Range op_range (TREE_TYPE (op));
 801   if (m_gori.compute_operand_range (op_range, s, lhs, op, src)
 802       && !op_range.varying_p ())
 803     {
 804       Value_Range range (TREE_TYPE (op));
 805       if (global.get_global_range (range, op))
 806         op_range.intersect (range);
 807       global.set_global_range (op, op_range);
 808       gimple *def_stmt = SSA_NAME_DEF_STMT (op);
 809       if (def_stmt && gimple_get_lhs (def_stmt) == op)
 810         calculate_stmt (def_stmt, op_range, src);
 811     }
 812 }
 813
 814 // Evaluate PHI statement, using the provided LHS range.
 815 // Check each constant argument predecessor if it can be taken
 816 // provide LHS to any symbolic arguments, and process their def statements.
 817
 818 void
 819 assume_query::calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src)
 820 {
 821   for (unsigned x= 0; x < gimple_phi_num_args (phi); x++)
 822     {
 823       tree arg = gimple_phi_arg_def (phi, x);
 824       Value_Range arg_range (TREE_TYPE (arg));
 825       if (gimple_range_ssa_p (arg))
 826         {
 827           // A symbol arg will be the LHS value.
 828           arg_range = lhs_range;
 829           range_cast (arg_range, TREE_TYPE (arg));
 830           if (!global.get_global_range (arg_range, arg))
 831             {
 832               global.set_global_range (arg, arg_range);
 833               gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
 834               if (def_stmt && gimple_get_lhs (def_stmt) == arg)
 835                 calculate_stmt (def_stmt, arg_range, src);
 836             }
 837         }
 838       else if (get_tree_range (arg_range, arg, NULL))
 839         {
 840           // If this is a constant value that differs from LHS, this
 841           // edge cannot be taken.
 842           arg_range.intersect (lhs_range);
 843           if (arg_range.undefined_p ())
 844             continue;
 845           // Otherwise check the condition feeding this edge.
 846           edge e = gimple_phi_arg_edge (phi, x);
 847           check_taken_edge (e, src);
 848         }
 849     }
 850 }
 851
 852 // If an edge is known to be taken, examine the outgoing edge to see
 853 // if it carries any range information that can also be evaluated.
 854
 855 void
 856 assume_query::check_taken_edge (edge e, fur_source &src)
 857 {
 858   gimple *stmt = gimple_outgoing_range_stmt_p (e->src);
 859   if (stmt && is_a<gcond *> (stmt))
 860     {
 861       int_range<2> cond;
 862       gcond_edge_range (cond, e);
 863       calculate_stmt (stmt, cond, src);
 864     }
 865 }
 866
 867 // Evaluate statement S which produces range LHS_RANGE.
 868
 869 void
 870 assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src)
 871 {
 872   gimple_range_op_handler handler (s);
 873   if (handler)
 874     {
 875       tree op = gimple_range_ssa_p (handler.operand1 ());
 876       if (op)
 877         calculate_op (op, s, lhs_range, src);
 878       op = gimple_range_ssa_p (handler.operand2 ());
 879       if (op)
 880         calculate_op (op, s, lhs_range, src);
 881     }
 882   else if (is_a<gphi *> (s))
 883     {
 884       calculate_phi (as_a<gphi *> (s), lhs_range, src);
 885       // Don't further check predecessors of blocks with PHIs.
 886       return;
 887     }
 888
 889   // Even if the walk back terminates before the top, if this is a single
 890   // predecessor block, see if the predecessor provided any ranges to get here.
 891   if (single_pred_p (gimple_bb (s)))
 892     check_taken_edge (single_pred_edge (gimple_bb (s)), src);
 893 }
 894
 895 // Show everything that was calculated.
 896
 897 void
 898 assume_query::dump (FILE *f)
 899 {
 900   fprintf (f, "Assumption details calculated:\n");
 901   for (unsigned i = 0; i < num_ssa_names; i++)
 902     {
 903       tree name = ssa_name (i);
 904       if (!name || !gimple_range_ssa_p (name))
 905         continue;
 906       tree type = TREE_TYPE (name);
 907       if (!Value_Range::supports_type_p (type))
 908         continue;
 909
 910       Value_Range assume_range (type);
 911       if (assume_range_p (assume_range, name))
 912         {
 913           print_generic_expr (f, name, TDF_SLIM);
 914           fprintf (f, " -> ");
 915           assume_range.dump (f);
 916           fputc ('\n', f);
 917         }
 918     }
 919   fprintf (f, "------------------------------\n");
 920 }