gcc/value-query.cc

   1 /* Support routines for value queries.
   2    Copyright (C) 2020-2023 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-query.h"
  32 #include "alloc-pool.h"
  33 #include "gimple-range.h"
  34 #include "value-range-storage.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 often 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 often 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's.
 146
 147 class equiv_allocator : public object_allocator<value_range>
 148 {
 149 public:
 150   equiv_allocator ()
 151     : object_allocator<value_range> ("equiv_allocator pool") { }
 152 };
 153
 154 const value_range *
 155 range_query::get_value_range (const_tree expr, gimple *stmt)
 156 {
 157   int_range_max r;
 158   if (range_of_expr (r, const_cast<tree> (expr), stmt))
 159     return new (equiv_alloc->allocate ()) value_range (r);
 160   return new (equiv_alloc->allocate ()) value_range (TREE_TYPE (expr));
 161 }
 162
 163 range_query::range_query ()
 164 {
 165   equiv_alloc = new equiv_allocator;
 166   m_oracle = NULL;
 167 }
 168
 169 range_query::~range_query ()
 170 {
 171   equiv_alloc->release ();
 172   delete equiv_alloc;
 173 }
 174
 175 // Return a range in R for the tree EXPR.  Return true if a range is
 176 // representable, and UNDEFINED/false if not.
 177
 178 bool
 179 range_query::get_tree_range (vrange &r, tree expr, gimple *stmt)
 180 {
 181   tree type;
 182   if (TYPE_P (expr))
 183     type = expr;
 184   else
 185     type = TREE_TYPE (expr);
 186
 187   if (!Value_Range::supports_type_p (type))
 188     {
 189       r.set_undefined ();
 190       return false;
 191     }
 192   if (expr == type)
 193     {
 194       r.set_varying (type);
 195       return true;
 196     }
 197   switch (TREE_CODE (expr))
 198     {
 199     case INTEGER_CST:
 200       if (TREE_OVERFLOW_P (expr))
 201         expr = drop_tree_overflow (expr);
 202       r.set (expr, expr);
 203       return true;
 204
 205     case REAL_CST:
 206       {
 207         frange &f = as_a <frange> (r);
 208         f.set (expr, expr);
 209         if (!real_isnan (TREE_REAL_CST_PTR (expr)))
 210           f.clear_nan ();
 211         return true;
 212       }
 213
 214     case SSA_NAME:
 215       gimple_range_global (r, expr);
 216       return true;
 217
 218     case ADDR_EXPR:
 219       {
 220         // Handle &var which can show up in phi arguments.
 221         bool ov;
 222         if (tree_single_nonzero_warnv_p (expr, &ov))
 223           {
 224             r.set_nonzero (type);
 225             return true;
 226           }
 227         break;
 228       }
 229
 230     default:
 231       break;
 232     }
 233   if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
 234     {
 235       tree op0 = TREE_OPERAND (expr, 0);
 236       tree op1 = TREE_OPERAND (expr, 1);
 237       if (COMPARISON_CLASS_P (expr)
 238           && !Value_Range::supports_type_p (TREE_TYPE (op0)))
 239         return false;
 240       range_op_handler op (TREE_CODE (expr),
 241                            BINARY_CLASS_P (expr) ? type : TREE_TYPE (op0));
 242       if (op)
 243         {
 244           Value_Range r0 (TREE_TYPE (op0));
 245           Value_Range r1 (TREE_TYPE (op1));
 246           range_of_expr (r0, op0, stmt);
 247           range_of_expr (r1, op1, stmt);
 248           if (!op.fold_range (r, type, r0, r1))
 249             r.set_varying (type);
 250         }
 251       else
 252         r.set_varying (type);
 253       return true;
 254     }
 255   if (UNARY_CLASS_P (expr))
 256     {
 257       range_op_handler op (TREE_CODE (expr), type);
 258       tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
 259       if (op && Value_Range::supports_type_p (op0_type))
 260         {
 261           Value_Range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
 262           Value_Range r1 (type);
 263           r1.set_varying (type);
 264           range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
 265           if (!op.fold_range (r, type, r0, r1))
 266             r.set_varying (type);
 267         }
 268       else
 269         r.set_varying (type);
 270       return true;
 271     }
 272   r.set_varying (type);
 273   return true;
 274 }
 275
 276 // Return the range for NAME from SSA_NAME_RANGE_INFO.
 277
 278 static inline void
 279 get_ssa_name_range_info (vrange &r, const_tree name)
 280 {
 281   tree type = TREE_TYPE (name);
 282   gcc_checking_assert (!POINTER_TYPE_P (type));
 283   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
 284
 285   void *ri = SSA_NAME_RANGE_INFO (name);
 286
 287   if (ri)
 288     {
 289       vrange_storage vstore (NULL);
 290       vstore.get_vrange (ri, r, TREE_TYPE (name));
 291     }
 292   else
 293     r.set_varying (type);
 294 }
 295
 296 // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
 297
 298 static inline bool
 299 get_ssa_name_ptr_info_nonnull (const_tree name)
 300 {
 301   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 302   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
 303   if (pi == NULL)
 304     return false;
 305   /* TODO Now pt->null is conservatively set to true in PTA
 306      analysis. vrp is the only pass (including ipa-vrp)
 307      that clears pt.null via set_ptr_nonnull when it knows
 308      for sure. PTA will preserves the pt.null value set by VRP.
 309
 310      When PTA analysis is improved, pt.anything, pt.nonlocal
 311      and pt.escaped may also has to be considered before
 312      deciding that pointer cannot point to NULL.  */
 313   return !pi->pt.null;
 314 }
 315
 316 // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
 317 // Return the legacy global range for NAME if it has one, otherwise
 318 // return VARYING.
 319
 320 static void
 321 get_range_global (vrange &r, tree name, struct function *fun = cfun)
 322 {
 323   tree type = TREE_TYPE (name);
 324
 325   if (SSA_NAME_IS_DEFAULT_DEF (name))
 326     {
 327       tree sym = SSA_NAME_VAR (name);
 328       // Adapted from vr_values::get_lattice_entry().
 329       // Use a range from an SSA_NAME's available range.
 330       if (TREE_CODE (sym) == PARM_DECL)
 331         {
 332           // Try to use the "nonnull" attribute to create ~[0, 0]
 333           // anti-ranges for pointers.  Note that this is only valid with
 334           // default definitions of PARM_DECLs.
 335           if (POINTER_TYPE_P (type)
 336               && ((cfun && fun == cfun && nonnull_arg_p (sym))
 337                   || get_ssa_name_ptr_info_nonnull (name)))
 338             r.set_nonzero (type);
 339           else if (!POINTER_TYPE_P (type))
 340             {
 341               get_ssa_name_range_info (r, name);
 342               if (r.undefined_p ())
 343                 r.set_varying (type);
 344             }
 345           else
 346             r.set_varying (type);
 347         }
 348       // If this is a local automatic with no definition, use undefined.
 349       else if (TREE_CODE (sym) != RESULT_DECL)
 350         r.set_undefined ();
 351       else
 352         r.set_varying (type);
 353    }
 354   else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
 355     {
 356       get_ssa_name_range_info (r, name);
 357       if (r.undefined_p ())
 358         r.set_varying (type);
 359     }
 360   else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
 361     {
 362       if (get_ssa_name_ptr_info_nonnull (name))
 363         r.set_nonzero (type);
 364       else
 365         r.set_varying (type);
 366     }
 367   else
 368     r.set_varying (type);
 369 }
 370
 371 // This is where the ranger picks up global info to seed initial
 372 // requests.  It is a slightly restricted version of
 373 // get_range_global() above.
 374 //
 375 // The reason for the difference is that we can always pick the
 376 // default definition of an SSA with no adverse effects, but for other
 377 // SSAs, if we pick things up to early, we may prematurely eliminate
 378 // builtin_unreachables.
 379 //
 380 // Without this restriction, the test in g++.dg/tree-ssa/pr61034.C has
 381 // all of its unreachable calls removed too early.
 382 //
 383 // See discussion here:
 384 // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
 385
 386 void
 387 gimple_range_global (vrange &r, tree name, struct function *fun)
 388 {
 389   tree type = TREE_TYPE (name);
 390   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
 391
 392   if (SSA_NAME_IS_DEFAULT_DEF (name) || (fun && fun->after_inlining)
 393       || is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
 394     {
 395       get_range_global (r, name, fun);
 396       return;
 397     }
 398   r.set_varying (type);
 399 }
 400
 401 // ----------------------------------------------
 402 // global_range_query implementation.
 403
 404 global_range_query global_ranges;
 405
 406 bool
 407 global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
 408 {
 409   if (!gimple_range_ssa_p (expr))
 410     return get_tree_range (r, expr, stmt);
 411
 412   get_range_global (r, expr);
 413
 414   return true;
 415 }
 416
 417 // Return any known relation between SSA1 and SSA2 before stmt S is executed.
 418 // If GET_RANGE is true, query the range of both operands first to ensure
 419 // the definitions have been processed and any relations have be created.
 420
 421 relation_kind
 422 range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range)
 423 {
 424   if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
 425     return VREL_VARYING;
 426
 427   // Ensure ssa1 and ssa2 have both been evaluated.
 428   if (get_range)
 429     {
 430       Value_Range tmp1 (TREE_TYPE (ssa1));
 431       Value_Range tmp2 (TREE_TYPE (ssa2));
 432       range_of_expr (tmp1, ssa1, s);
 433       range_of_expr (tmp2, ssa2, s);
 434     }
 435   return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2);
 436 }
 437
 438 // Return any known relation between SSA1 and SSA2 on edge E.
 439 // If GET_RANGE is true, query the range of both operands first to ensure
 440 // the definitions have been processed and any relations have be created.
 441
 442 relation_kind
 443 range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
 444 {
 445   basic_block bb;
 446   if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
 447     return VREL_VARYING;
 448
 449   // Use destination block if it has a single predecessor, and this picks
 450   // up any relation on the edge.
 451   // Otherwise choose the src edge and the result is the same as on-exit.
 452   if (!single_pred_p (e->dest))
 453     bb = e->src;
 454   else
 455     bb = e->dest;
 456
 457   // Ensure ssa1 and ssa2 have both been evaluated.
 458   if (get_range)
 459     {
 460       Value_Range tmp (TREE_TYPE (ssa1));
 461       range_on_edge (tmp, e, ssa1);
 462       range_on_edge (tmp, e, ssa2);
 463     }
 464   return m_oracle->query_relation (bb, ssa1, ssa2);
 465 }