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