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