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