gcc/value-query.cc

   1 /* Support routines for value queries.
   2    Copyright (C) 2020-2021 Free Software Foundation, Inc.
   3    Contributed by Aldy Hernandez <aldyh@redhat.com> and
   4    Andrew MacLeod <amacleod@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 "tree-pretty-print.h"
  30 #include "fold-const.h"
  31 #include "value-range-equiv.h"
  32 #include "value-query.h"
  33 #include "alloc-pool.h"
  34 #include "gimple-range.h"
  35
  36 // value_query default methods.
  37
  38 tree
  39 value_query::value_on_edge (edge, tree expr)
  40 {
  41   return value_of_expr (expr);
  42 }
  43
  44 tree
  45 value_query::value_of_stmt (gimple *stmt, tree name)
  46 {
  47   if (!name)
  48     name = gimple_get_lhs (stmt);
  49
  50   gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
  51
  52   if (name)
  53     return value_of_expr (name);
  54   return NULL_TREE;
  55 }
  56
  57 // range_query default methods.
  58
  59 bool
  60 range_query::range_on_edge (irange &r, edge, tree expr)
  61 {
  62   return range_of_expr (r, expr);
  63 }
  64
  65 bool
  66 range_query::range_of_stmt (irange &r, gimple *stmt, tree name)
  67 {
  68   if (!name)
  69     name = gimple_get_lhs (stmt);
  70
  71   gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
  72
  73   if (name)
  74     return range_of_expr (r, name);
  75   return false;
  76 }
  77
  78 tree
  79 range_query::value_of_expr (tree expr, gimple *stmt)
  80 {
  81   tree t;
  82   int_range_max r;
  83
  84   if (!irange::supports_type_p (TREE_TYPE (expr)))
  85     return NULL_TREE;
  86
  87   if (range_of_expr (r, expr, stmt))
  88     {
  89       // A constant used in an unreachable block oftens returns as UNDEFINED.
  90       // If the result is undefined, check the global value for a constant.
  91       if (r.undefined_p ())
  92         range_of_expr (r, expr);
  93       if (r.singleton_p (&t))
  94         return t;
  95     }
  96   return NULL_TREE;
  97 }
  98
  99 tree
 100 range_query::value_on_edge (edge e, tree expr)
 101 {
 102   tree t;
 103   int_range_max r;
 104
 105   if (!irange::supports_type_p (TREE_TYPE (expr)))
 106     return NULL_TREE;
 107   if (range_on_edge (r, e, expr))
 108     {
 109       // A constant used in an unreachable block oftens returns as UNDEFINED.
 110       // If the result is undefined, check the global value for a constant.
 111       if (r.undefined_p ())
 112         range_of_expr (r, expr);
 113       if (r.singleton_p (&t))
 114         return t;
 115     }
 116   return NULL_TREE;
 117
 118 }
 119
 120 tree
 121 range_query::value_of_stmt (gimple *stmt, tree name)
 122 {
 123   tree t;
 124   int_range_max r;
 125
 126   if (!name)
 127     name = gimple_get_lhs (stmt);
 128
 129   gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
 130
 131   if (!name || !irange::supports_type_p (TREE_TYPE (name)))
 132     return NULL_TREE;
 133   if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
 134     return t;
 135   return NULL_TREE;
 136
 137 }
 138
 139 void
 140 range_query::dump (FILE *)
 141 {
 142 }
 143
 144 // valuation_query support routines for value_range_equiv's.
 145
 146 class equiv_allocator : public object_allocator<value_range_equiv>
 147 {
 148 public:
 149   equiv_allocator ()
 150     : object_allocator<value_range_equiv> ("equiv_allocator pool") { }
 151 };
 152
 153 value_range_equiv *
 154 range_query::allocate_value_range_equiv ()
 155 {
 156   return new (equiv_alloc->allocate ()) value_range_equiv;
 157 }
 158
 159 void
 160 range_query::free_value_range_equiv (value_range_equiv *v)
 161 {
 162   equiv_alloc->remove (v);
 163 }
 164
 165 const class value_range_equiv *
 166 range_query::get_value_range (const_tree expr, gimple *stmt)
 167 {
 168   int_range_max r;
 169   if (range_of_expr (r, const_cast<tree> (expr), stmt))
 170     return new (equiv_alloc->allocate ()) value_range_equiv (r);
 171   return new (equiv_alloc->allocate ()) value_range_equiv (TREE_TYPE (expr));
 172 }
 173
 174 range_query::range_query ()
 175 {
 176   equiv_alloc = new equiv_allocator;
 177   m_oracle = NULL;
 178 }
 179
 180 range_query::~range_query ()
 181 {
 182   equiv_alloc->release ();
 183   delete equiv_alloc;
 184 }
 185
 186 // Return a range in R for the tree EXPR.  Return true if a range is
 187 // representable, and UNDEFINED/false if not.
 188
 189 bool
 190 range_query::get_tree_range (irange &r, tree expr, gimple *stmt)
 191 {
 192   tree type;
 193   if (TYPE_P (expr))
 194     type = expr;
 195   else
 196     type = TREE_TYPE (expr);
 197
 198   if (!irange::supports_type_p (type))
 199     {
 200       r.set_undefined ();
 201       return false;
 202     }
 203   if (expr == type)
 204     {
 205       r.set_varying (type);
 206       return true;
 207     }
 208   switch (TREE_CODE (expr))
 209     {
 210     case INTEGER_CST:
 211       if (TREE_OVERFLOW_P (expr))
 212         expr = drop_tree_overflow (expr);
 213       r.set (expr, expr);
 214       return true;
 215
 216     case SSA_NAME:
 217       r = gimple_range_global (expr);
 218       return true;
 219
 220     case ADDR_EXPR:
 221       {
 222         // Handle &var which can show up in phi arguments.
 223         bool ov;
 224         if (tree_single_nonzero_warnv_p (expr, &ov))
 225           {
 226             r = range_nonzero (type);
 227             return true;
 228           }
 229         break;
 230       }
 231
 232     default:
 233       break;
 234     }
 235   if (BINARY_CLASS_P (expr))
 236     {
 237       range_operator *op = range_op_handler (TREE_CODE (expr), type);
 238       if (op)
 239         {
 240           int_range_max r0, r1;
 241           range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
 242           range_of_expr (r1, TREE_OPERAND (expr, 1), stmt);
 243           op->fold_range (r, type, r0, r1);
 244         }
 245       else
 246         r.set_varying (type);
 247       return true;
 248     }
 249   if (UNARY_CLASS_P (expr))
 250     {
 251       range_operator *op = range_op_handler (TREE_CODE (expr), type);
 252       if (op)
 253         {
 254           int_range_max r0;
 255           range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
 256           op->fold_range (r, type, r0, int_range<1> (type));
 257         }
 258       else
 259         r.set_varying (type);
 260       return true;
 261     }
 262   r.set_varying (type);
 263   return true;
 264 }
 265
 266 // Return the range for NAME from SSA_NAME_RANGE_INFO.
 267
 268 static inline void
 269 get_ssa_name_range_info (irange &r, const_tree name)
 270 {
 271   tree type = TREE_TYPE (name);
 272   gcc_checking_assert (!POINTER_TYPE_P (type));
 273   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
 274
 275   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 276
 277   // Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs
 278   // with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision.
 279   if (!ri || (GET_MODE_PRECISION (SCALAR_INT_TYPE_MODE (TREE_TYPE (name)))
 280               > 2 * HOST_BITS_PER_WIDE_INT))
 281     r.set_varying (type);
 282   else
 283     r.set (wide_int_to_tree (type, ri->get_min ()),
 284            wide_int_to_tree (type, ri->get_max ()),
 285            SSA_NAME_RANGE_TYPE (name));
 286 }
 287
 288 // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
 289
 290 static inline bool
 291 get_ssa_name_ptr_info_nonnull (const_tree name)
 292 {
 293   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 294   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
 295   if (pi == NULL)
 296     return false;
 297   /* TODO Now pt->null is conservatively set to true in PTA
 298      analysis. vrp is the only pass (including ipa-vrp)
 299      that clears pt.null via set_ptr_nonnull when it knows
 300      for sure. PTA will preserves the pt.null value set by VRP.
 301
 302      When PTA analysis is improved, pt.anything, pt.nonlocal
 303      and pt.escaped may also has to be considered before
 304      deciding that pointer cannot point to NULL.  */
 305   return !pi->pt.null;
 306 }
 307
 308 // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
 309 // SSA_NAME_PTR_INFO fields.  Return TRUE if the range for NAME was
 310 // updated.
 311
 312 bool
 313 update_global_range (irange &r, tree name)
 314 {
 315   tree type = TREE_TYPE (name);
 316
 317   if (r.undefined_p () || r.varying_p ())
 318     return false;
 319
 320   if (INTEGRAL_TYPE_P (type))
 321     {
 322       // If a global range already exists, incorporate it.
 323       if (SSA_NAME_RANGE_INFO (name))
 324         {
 325           value_range glob;
 326           get_ssa_name_range_info (glob, name);
 327           r.intersect (glob);
 328         }
 329       if (r.undefined_p ())
 330         return false;
 331
 332       value_range vr = r;
 333       set_range_info (name, vr);
 334       return true;
 335     }
 336   else if (POINTER_TYPE_P (type))
 337     {
 338       if (r.nonzero_p ())
 339         {
 340           set_ptr_nonnull (name);
 341           return true;
 342         }
 343     }
 344   return false;
 345 }
 346
 347 // Return the legacy global range for NAME if it has one, otherwise
 348 // return VARYING.
 349
 350 static void
 351 get_range_global (irange &r, tree name)
 352 {
 353   tree type = TREE_TYPE (name);
 354
 355   if (SSA_NAME_IS_DEFAULT_DEF (name))
 356     {
 357       tree sym = SSA_NAME_VAR (name);
 358       // Adapted from vr_values::get_lattice_entry().
 359       // Use a range from an SSA_NAME's available range.
 360       if (TREE_CODE (sym) == PARM_DECL)
 361         {
 362           // Try to use the "nonnull" attribute to create ~[0, 0]
 363           // anti-ranges for pointers.  Note that this is only valid with
 364           // default definitions of PARM_DECLs.
 365           if (POINTER_TYPE_P (type)
 366               && ((cfun && nonnull_arg_p (sym))
 367                   || get_ssa_name_ptr_info_nonnull (name)))
 368             r.set_nonzero (type);
 369           else if (INTEGRAL_TYPE_P (type))
 370             {
 371               get_ssa_name_range_info (r, name);
 372               if (r.undefined_p ())
 373                 r.set_varying (type);
 374             }
 375           else
 376             r.set_varying (type);
 377         }
 378       // If this is a local automatic with no definition, use undefined.
 379       else if (TREE_CODE (sym) != RESULT_DECL)
 380         r.set_undefined ();
 381       else
 382         r.set_varying (type);
 383    }
 384   else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
 385     {
 386       get_ssa_name_range_info (r, name);
 387       if (r.undefined_p ())
 388         r.set_varying (type);
 389     }
 390   else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
 391     {
 392       if (get_ssa_name_ptr_info_nonnull (name))
 393         r.set_nonzero (type);
 394       else
 395         r.set_varying (type);
 396     }
 397   else
 398     r.set_varying (type);
 399 }
 400
 401 // This is where the ranger picks up global info to seed initial
 402 // requests.  It is a slightly restricted version of
 403 // get_range_global() above.
 404 //
 405 // The reason for the difference is that we can always pick the
 406 // default definition of an SSA with no adverse effects, but for other
 407 // SSAs, if we pick things up to early, we may prematurely eliminate
 408 // builtin_unreachables.
 409 //
 410 // Without this restriction, the test in g++.dg/tree-ssa/pr61034.C has
 411 // all of its unreachable calls removed too early.
 412 //
 413 // See discussion here:
 414 // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
 415
 416 value_range
 417 gimple_range_global (tree name)
 418 {
 419   tree type = TREE_TYPE (name);
 420   gcc_checking_assert (TREE_CODE (name) == SSA_NAME
 421                        && irange::supports_type_p (type));
 422
 423   if (SSA_NAME_IS_DEFAULT_DEF (name) || (cfun && cfun->after_inlining)
 424       || is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
 425     {
 426       value_range vr;
 427       get_range_global (vr, name);
 428       return vr;
 429     }
 430   return value_range (type);
 431 }
 432
 433 // ----------------------------------------------
 434 // global_range_query implementation.
 435
 436 global_range_query global_ranges;
 437
 438 // Like get_range_query, but for accessing global ranges.
 439
 440 range_query *
 441 get_global_range_query ()
 442 {
 443   return &global_ranges;
 444 }
 445
 446 bool
 447 global_range_query::range_of_expr (irange &r, tree expr, gimple *stmt)
 448 {
 449   tree type = TREE_TYPE (expr);
 450
 451   if (!irange::supports_type_p (type) || !gimple_range_ssa_p (expr))
 452     return get_tree_range (r, expr, stmt);
 453
 454   get_range_global (r, expr);
 455
 456   return true;
 457 }
 458
 459 // Return any known relation between SSA1 and SSA2 before stmt S is executed.
 460 // If GET_RANGE is true, query the range of both operands first to ensure
 461 // the defintions have been processed and any relations have be created.
 462
 463 relation_kind
 464 range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range)
 465 {
 466   int_range_max tmp;
 467   if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
 468     return VREL_NONE;
 469
 470   // Ensure ssa1 and ssa2 have both been evaluated.
 471   if (get_range)
 472     {
 473       range_of_expr (tmp, ssa1, s);
 474       range_of_expr (tmp, ssa2, s);
 475     }
 476   return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2);
 477 }
 478
 479 // Return any known relation between SSA1 and SSA2 on edge E.
 480 // If GET_RANGE is true, query the range of both operands first to ensure
 481 // the defintions have been processed and any relations have be created.
 482
 483 relation_kind
 484 range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
 485 {
 486   basic_block bb;
 487   int_range_max tmp;
 488   if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
 489     return VREL_NONE;
 490
 491   // Use destination block if it has a single predecessor, and this picks
 492   // up any relation on the edge.
 493   // Otherwise choose the src edge and the result is the same as on-exit.
 494   if (!single_pred_p (e->dest))
 495     bb = e->src;
 496   else
 497     bb = e->dest;
 498
 499   // Ensure ssa1 and ssa2 have both been evaluated.
 500   if (get_range)
 501     {
 502       range_on_edge (tmp, e, ssa1);
 503       range_on_edge (tmp, e, ssa2);
 504     }
 505   return m_oracle->query_relation (bb, ssa1, ssa2);
 506 }