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       if (op)
 233         {
 234           Value_Range r0 (TREE_TYPE (op0));
 235           Value_Range r1 (TREE_TYPE (op1));
 236           range_of_expr (r0, op0, stmt);
 237           range_of_expr (r1, op1, stmt);
 238           if (!op.fold_range (r, type, r0, r1))
 239             r.set_varying (type);
 240         }
 241       else
 242         r.set_varying (type);
 243       return true;
 244     }
 245   if (UNARY_CLASS_P (expr))
 246     {
 247       range_op_handler op (TREE_CODE (expr));
 248       tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
 249       if (op && Value_Range::supports_type_p (op0_type))
 250         {
 251           Value_Range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
 252           Value_Range r1 (type);
 253           r1.set_varying (type);
 254           range_of_expr (r0, TREE_OPERAND (expr, 0), stmt);
 255           if (!op.fold_range (r, type, r0, r1))
 256             r.set_varying (type);
 257         }
 258       else
 259         r.set_varying (type);
 260       return true;
 261     }
 262   r.set_varying (type);
 263   return true;
 264 }
 265
 266 // Return the range for NAME from SSA_NAME_RANGE_INFO.
 267
 268 static inline void
 269 get_ssa_name_range_info (vrange &r, const_tree name)
 270 {
 271   tree type = TREE_TYPE (name);
 272   gcc_checking_assert (!POINTER_TYPE_P (type));
 273   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
 274
 275   vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
 276
 277   if (ri)
 278     ri->get_vrange (r, TREE_TYPE (name));
 279   else
 280     r.set_varying (type);
 281 }
 282
 283 // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
 284
 285 static inline bool
 286 get_ssa_name_ptr_info_nonnull (const_tree name)
 287 {
 288   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 289   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
 290   if (pi == NULL)
 291     return false;
 292   /* TODO Now pt->null is conservatively set to true in PTA
 293      analysis. vrp is the only pass (including ipa-vrp)
 294      that clears pt.null via set_ptr_nonnull when it knows
 295      for sure. PTA will preserves the pt.null value set by VRP.
 296
 297      When PTA analysis is improved, pt.anything, pt.nonlocal
 298      and pt.escaped may also has to be considered before
 299      deciding that pointer cannot point to NULL.  */
 300   return !pi->pt.null;
 301 }
 302
 303 // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
 304 // Return the legacy global range for NAME if it has one, otherwise
 305 // return VARYING.
 306
 307 static void
 308 get_range_global (vrange &r, tree name, struct function *fun = cfun)
 309 {
 310   tree type = TREE_TYPE (name);
 311
 312   if (SSA_NAME_IS_DEFAULT_DEF (name))
 313     {
 314       tree sym = SSA_NAME_VAR (name);
 315       // Adapted from vr_values::get_lattice_entry().
 316       // Use a range from an SSA_NAME's available range.
 317       if (TREE_CODE (sym) == PARM_DECL)
 318         {
 319           // Try to use the "nonnull" attribute to create ~[0, 0]
 320           // anti-ranges for pointers.  Note that this is only valid with
 321           // default definitions of PARM_DECLs.
 322           if (POINTER_TYPE_P (type)
 323               && ((cfun && fun == cfun && nonnull_arg_p (sym))
 324                   || get_ssa_name_ptr_info_nonnull (name)))
 325             r.set_nonzero (type);
 326           else if (!POINTER_TYPE_P (type))
 327             {
 328               get_ssa_name_range_info (r, name);
 329               if (r.undefined_p ())
 330                 r.set_varying (type);
 331             }
 332           else
 333             r.set_varying (type);
 334         }
 335       // If this is a local automatic with no definition, use undefined.
 336       else if (TREE_CODE (sym) != RESULT_DECL)
 337         r.set_undefined ();
 338       else
 339         r.set_varying (type);
 340    }
 341   else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
 342     {
 343       get_ssa_name_range_info (r, name);
 344       if (r.undefined_p ())
 345         r.set_varying (type);
 346     }
 347   else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
 348     {
 349       if (get_ssa_name_ptr_info_nonnull (name))
 350         r.set_nonzero (type);
 351       else
 352         r.set_varying (type);
 353     }
 354   else
 355     r.set_varying (type);
 356 }
 357
 358 // This is where the ranger picks up global info to seed initial
 359 // requests.  It is a slightly restricted version of
 360 // get_range_global() above.
 361 //
 362 // The reason for the difference is that we can always pick the
 363 // default definition of an SSA with no adverse effects, but for other
 364 // SSAs, if we pick things up to early, we may prematurely eliminate
 365 // builtin_unreachables.
 366 //
 367 // Without this restriction, the test in g++.dg/tree-ssa/pr61034.C has
 368 // all of its unreachable calls removed too early.
 369 //
 370 // See discussion here:
 371 // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
 372
 373 void
 374 gimple_range_global (vrange &r, tree name, struct function *fun)
 375 {
 376   tree type = TREE_TYPE (name);
 377   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
 378
 379   if (SSA_NAME_IS_DEFAULT_DEF (name) || (fun && fun->after_inlining)
 380       || is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
 381     {
 382       get_range_global (r, name, fun);
 383       return;
 384     }
 385   r.set_varying (type);
 386 }
 387
 388 // ----------------------------------------------
 389 // global_range_query implementation.
 390
 391 global_range_query global_ranges;
 392
 393 bool
 394 global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
 395 {
 396   if (!gimple_range_ssa_p (expr))
 397     return get_tree_range (r, expr, stmt);
 398
 399   get_range_global (r, expr);
 400
 401   return true;
 402 }
 403
 404 // Return any known relation between SSA1 and SSA2 before stmt S is executed.
 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 (gimple *s, tree ssa1, tree ssa2, bool get_range)
 410 {
 411   if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
 412     return VREL_VARYING;
 413
 414   // Ensure ssa1 and ssa2 have both been evaluated.
 415   if (get_range)
 416     {
 417       Value_Range tmp1 (TREE_TYPE (ssa1));
 418       Value_Range tmp2 (TREE_TYPE (ssa2));
 419       range_of_expr (tmp1, ssa1, s);
 420       range_of_expr (tmp2, ssa2, s);
 421     }
 422   return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2);
 423 }
 424
 425 // Return any known relation between SSA1 and SSA2 on edge E.
 426 // If GET_RANGE is true, query the range of both operands first to ensure
 427 // the definitions have been processed and any relations have be created.
 428
 429 relation_kind
 430 range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
 431 {
 432   basic_block bb;
 433   if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
 434     return VREL_VARYING;
 435
 436   // Use destination block if it has a single predecessor, and this picks
 437   // up any relation on the edge.
 438   // Otherwise choose the src edge and the result is the same as on-exit.
 439   if (!single_pred_p (e->dest))
 440     bb = e->src;
 441   else
 442     bb = e->dest;
 443
 444   // Ensure ssa1 and ssa2 have both been evaluated.
 445   if (get_range)
 446     {
 447       Value_Range tmp (TREE_TYPE (ssa1));
 448       range_on_edge (tmp, e, ssa1);
 449       range_on_edge (tmp, e, ssa2);
 450     }
 451   return m_oracle->query_relation (bb, ssa1, ssa2);
 452 }