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