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