gcc/value-query.cc

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