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