gcc/value-query.cc

   1 /* Support routines for value queries.
   2    Copyright (C) 2020-2024 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_on_entry (vrange &r, basic_block, tree expr)
  46 {
  47   return range_of_expr (r, expr);
  48 }
  49
  50 bool
  51 range_query::range_on_exit (vrange &r, basic_block, tree expr)
  52 {
  53   return range_of_expr (r, expr);
  54 }
  55
  56 bool
  57 range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
  58 {
  59   if (!name)
  60     name = gimple_get_lhs (stmt);
  61
  62   gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
  63
  64   if (name)
  65     return range_of_expr (r, name);
  66   return false;
  67 }
  68
  69 // If the range of expr EXPR at STMT is a single value, return it.
  70 // Otherwise return NULL_TREE.
  71
  72 tree
  73 range_query::value_of_expr (tree expr, gimple *stmt)
  74 {
  75   tree t;
  76
  77   if (!Value_Range::supports_type_p (TREE_TYPE (expr)))
  78     return NULL_TREE;
  79
  80   Value_Range r (TREE_TYPE (expr));
  81
  82   if (range_of_expr (r, expr, stmt))
  83     {
  84       // A constant used in an unreachable block often returns as UNDEFINED.
  85       // If the result is undefined, check the global value for a constant.
  86       if (r.undefined_p ())
  87         range_of_expr (r, expr);
  88       if (r.singleton_p (&t))
  89         return t;
  90     }
  91   return NULL_TREE;
  92 }
  93
  94 // If the range on edge E for EXPR is a single value, return it.
  95 // Otherwise return NULL_TREE.
  96
  97 tree
  98 range_query::value_on_edge (edge e, tree expr)
  99 {
 100   tree t;
 101
 102   if (!Value_Range::supports_type_p (TREE_TYPE (expr)))
 103     return NULL_TREE;
 104   Value_Range r (TREE_TYPE (expr));
 105   if (range_on_edge (r, e, expr))
 106     {
 107       // A constant used in an unreachable block often returns as UNDEFINED.
 108       // If the result is undefined, check the global value for a constant.
 109       if (r.undefined_p ())
 110         range_of_expr (r, expr);
 111       if (r.singleton_p (&t))
 112         return t;
 113     }
 114   return NULL_TREE;
 115 }
 116
 117 // If the range of STMT for NAME is a single value, return it.
 118 // Otherwise return NULL_TREE.
 119
 120 tree
 121 range_query::value_of_stmt (gimple *stmt, tree name)
 122 {
 123   tree t;
 124
 125   if (!name)
 126     name = gimple_get_lhs (stmt);
 127
 128   gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
 129
 130   if (!name || !Value_Range::supports_type_p (TREE_TYPE (name)))
 131     return NULL_TREE;
 132   Value_Range r (TREE_TYPE (name));
 133   if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
 134     return t;
 135   return NULL_TREE;
 136 }
 137
 138 // If the range on entry to BB for EXPR is a single value, return it.
 139 // Otherwise return NULL_TREE.
 140
 141 tree
 142 range_query::value_on_entry (basic_block bb, tree expr)
 143 {
 144   tree t;
 145
 146   gcc_checking_assert (bb);
 147   if (!Value_Range::supports_type_p (TREE_TYPE (expr)))
 148     return NULL_TREE;
 149
 150   Value_Range r (TREE_TYPE (expr));
 151
 152   if (range_on_entry (r, bb, expr) && r.singleton_p (&t))
 153     return t;
 154   return NULL_TREE;
 155 }
 156
 157 // If the range on exit to BB for EXPR is a single value, return it.
 158 // Otherwise return NULL_TREE.
 159
 160 tree
 161 range_query::value_on_exit (basic_block bb, tree expr)
 162 {
 163   tree t;
 164
 165   gcc_checking_assert (bb);
 166   if (!Value_Range::supports_type_p (TREE_TYPE (expr)))
 167     return NULL_TREE;
 168
 169   Value_Range r (TREE_TYPE (expr));
 170
 171   if (range_on_exit (r, bb, expr) && r.singleton_p (&t))
 172     return t;
 173   return NULL_TREE;
 174 }
 175
 176 void
 177 range_query::dump (FILE *)
 178 {
 179 }
 180
 181 range_query::range_query ()
 182 {
 183   m_oracle = NULL;
 184 }
 185
 186 range_query::~range_query ()
 187 {
 188 }
 189
 190 // This routine will invoke the equivalent of range_of_expr on
 191 // either a gimple statement STMT, on entry to block BBENTRY, or on
 192 // exit from block BBEXIT.   Only one of these 3 fields may be set.
 193 // It is valid for none of them to be set, in wqhich case there is no context.
 194
 195 bool
 196 range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
 197                                    basic_block bbentry, basic_block bbexit)
 198 {
 199   if (bbentry)
 200     {
 201       gcc_checking_assert (!stmt && !bbexit);
 202       return range_on_entry (r, bbentry, expr);
 203     }
 204   if (bbexit)
 205     {
 206       gcc_checking_assert (!stmt);
 207       return range_on_exit (r, bbexit, expr);
 208     }
 209
 210   return range_of_expr (r, expr, stmt);
 211 }
 212
 213 // Return a range in R for the tree EXPR.  The context can be either a STMT,
 214 // or on entry to block BBENTRY or exit from block BBEXIT.
 215 // Return true if a range is representable, and UNDEFINED/false if not.
 216
 217 bool
 218 range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
 219                              basic_block bbentry, basic_block bbexit)
 220 {
 221   tree type;
 222   if (TYPE_P (expr))
 223     type = expr;
 224   else
 225     type = TREE_TYPE (expr);
 226
 227   if (!Value_Range::supports_type_p (type))
 228     {
 229       r.set_undefined ();
 230       return false;
 231     }
 232   if (expr == type)
 233     {
 234       r.set_varying (type);
 235       return true;
 236     }
 237   switch (TREE_CODE (expr))
 238     {
 239     case INTEGER_CST:
 240       {
 241         if (TREE_OVERFLOW_P (expr))
 242           expr = drop_tree_overflow (expr);
 243         r.set (expr, expr);
 244         return true;
 245       }
 246
 247     case REAL_CST:
 248       {
 249         frange &f = as_a <frange> (r);
 250         REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
 251         if (real_isnan (rv))
 252           {
 253             bool sign = real_isneg (rv);
 254             f.set_nan (TREE_TYPE (expr), sign);
 255           }
 256         else
 257           {
 258             nan_state nan (false);
 259             f.set (TREE_TYPE (expr), *rv, *rv, nan);
 260           }
 261         return true;
 262       }
 263
 264     case SSA_NAME:
 265       // If this is not an abnormal or virtual ssa, invoke range_of_expr.
 266       if (gimple_range_ssa_p (expr))
 267         return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit);
 268       gimple_range_global (r, expr);
 269       return true;
 270
 271     case ADDR_EXPR:
 272       {
 273         // Handle &var which can show up in phi arguments.
 274         bool ov;
 275         if (tree_single_nonzero_warnv_p (expr, &ov))
 276           {
 277             r.set_nonzero (type);
 278             return true;
 279           }
 280         break;
 281       }
 282
 283     default:
 284       break;
 285     }
 286   if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
 287     {
 288       tree op0 = TREE_OPERAND (expr, 0);
 289       tree op1 = TREE_OPERAND (expr, 1);
 290       if (COMPARISON_CLASS_P (expr)
 291           && !Value_Range::supports_type_p (TREE_TYPE (op0)))
 292         return false;
 293       range_op_handler op (TREE_CODE (expr));
 294       if (op)
 295         {
 296           Value_Range r0 (TREE_TYPE (op0));
 297           Value_Range r1 (TREE_TYPE (op1));
 298           invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit);
 299           invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit);
 300           if (!op.fold_range (r, type, r0, r1))
 301             r.set_varying (type);
 302         }
 303       else
 304         r.set_varying (type);
 305       return true;
 306     }
 307   if (UNARY_CLASS_P (expr))
 308     {
 309       range_op_handler op (TREE_CODE (expr));
 310       tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
 311       if (op && Value_Range::supports_type_p (op0_type))
 312         {
 313           Value_Range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
 314           Value_Range r1 (type);
 315           r1.set_varying (type);
 316           invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
 317                                 bbexit);
 318           if (!op.fold_range (r, type, r0, r1))
 319             r.set_varying (type);
 320         }
 321       else
 322         r.set_varying (type);
 323       return true;
 324     }
 325   r.set_varying (type);
 326   return true;
 327 }
 328
 329 // Return the range for NAME from SSA_NAME_RANGE_INFO.
 330
 331 static inline void
 332 get_ssa_name_range_info (vrange &r, const_tree name)
 333 {
 334   tree type = TREE_TYPE (name);
 335   gcc_checking_assert (!POINTER_TYPE_P (type));
 336   gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
 337
 338   vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
 339
 340   if (ri)
 341     ri->get_vrange (r, TREE_TYPE (name));
 342   else
 343     r.set_varying (type);
 344 }
 345
 346 // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO.
 347
 348 static inline bool
 349 get_ssa_name_ptr_info_nonnull (const_tree name)
 350 {
 351   gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
 352   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
 353   if (pi == NULL)
 354     return false;
 355   /* TODO Now pt->null is conservatively set to true in PTA
 356      analysis. vrp is the only pass (including ipa-vrp)
 357      that clears pt.null via set_ptr_nonnull when it knows
 358      for sure. PTA will preserves the pt.null value set by VRP.
 359
 360      When PTA analysis is improved, pt.anything, pt.nonlocal
 361      and pt.escaped may also has to be considered before
 362      deciding that pointer cannot point to NULL.  */
 363   return !pi->pt.null;
 364 }
 365
 366 // Update the global range for NAME into the SSA_RANGE_NAME_INFO and
 367 // Return the legacy global range for NAME if it has one, otherwise
 368 // return VARYING.
 369 // See discussion here regarding why there use to be a wrapper function:
 370 // https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
 371 // Legacy EVRP has been removed, leaving just this function.
 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))
 380     {
 381       tree sym = SSA_NAME_VAR (name);
 382       // Adapted from vr_values::get_lattice_entry().
 383       // Use a range from an SSA_NAME's available range.
 384       if (TREE_CODE (sym) == PARM_DECL)
 385         {
 386           // Try to use the "nonnull" attribute to create ~[0, 0]
 387           // anti-ranges for pointers.  Note that this is only valid with
 388           // default definitions of PARM_DECLs.
 389           if (POINTER_TYPE_P (type)
 390               && ((cfun && fun == cfun && nonnull_arg_p (sym))
 391                   || get_ssa_name_ptr_info_nonnull (name)))
 392             r.set_nonzero (type);
 393           else if (!POINTER_TYPE_P (type))
 394             {
 395               get_ssa_name_range_info (r, name);
 396               if (r.undefined_p ())
 397                 r.set_varying (type);
 398             }
 399           else
 400             r.set_varying (type);
 401         }
 402       // If this is a local automatic with no definition, use undefined.
 403       else if (TREE_CODE (sym) != RESULT_DECL)
 404         r.set_undefined ();
 405       else
 406         r.set_varying (type);
 407    }
 408   else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name))
 409     {
 410       get_ssa_name_range_info (r, name);
 411       if (r.undefined_p ())
 412         r.set_varying (type);
 413     }
 414   else if (POINTER_TYPE_P (type) && SSA_NAME_PTR_INFO (name))
 415     {
 416       if (get_ssa_name_ptr_info_nonnull (name))
 417         r.set_nonzero (type);
 418       else
 419         r.set_varying (type);
 420     }
 421   else
 422     r.set_varying (type);
 423 }
 424
 425 // ----------------------------------------------
 426 // global_range_query implementation.
 427
 428 global_range_query global_ranges;
 429
 430 bool
 431 global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
 432 {
 433   if (!gimple_range_ssa_p (expr))
 434     return get_tree_range (r, expr, stmt);
 435
 436   gimple_range_global (r, expr);
 437
 438   return true;
 439 }
 440
 441 // Return any known relation between SSA1 and SSA2 before stmt S is executed.
 442 // If GET_RANGE is true, query the range of both operands first to ensure
 443 // the definitions have been processed and any relations have be created.
 444
 445 relation_kind
 446 range_query::query_relation (gimple *s, tree ssa1, tree ssa2, bool get_range)
 447 {
 448   if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
 449     return VREL_VARYING;
 450
 451   // Ensure ssa1 and ssa2 have both been evaluated.
 452   if (get_range)
 453     {
 454       Value_Range tmp1 (TREE_TYPE (ssa1));
 455       Value_Range tmp2 (TREE_TYPE (ssa2));
 456       range_of_expr (tmp1, ssa1, s);
 457       range_of_expr (tmp2, ssa2, s);
 458     }
 459   return m_oracle->query_relation (gimple_bb (s), ssa1, ssa2);
 460 }
 461
 462 // Return any known relation between SSA1 and SSA2 on edge E.
 463 // If GET_RANGE is true, query the range of both operands first to ensure
 464 // the definitions have been processed and any relations have be created.
 465
 466 relation_kind
 467 range_query::query_relation (edge e, tree ssa1, tree ssa2, bool get_range)
 468 {
 469   basic_block bb;
 470   if (!m_oracle || TREE_CODE (ssa1) != SSA_NAME || TREE_CODE (ssa2) != SSA_NAME)
 471     return VREL_VARYING;
 472
 473   // Use destination block if it has a single predecessor, and this picks
 474   // up any relation on the edge.
 475   // Otherwise choose the src edge and the result is the same as on-exit.
 476   if (!single_pred_p (e->dest))
 477     bb = e->src;
 478   else
 479     bb = e->dest;
 480
 481   // Ensure ssa1 and ssa2 have both been evaluated.
 482   if (get_range)
 483     {
 484       Value_Range tmp (TREE_TYPE (ssa1));
 485       range_on_edge (tmp, e, ssa1);
 486       range_on_edge (tmp, e, ssa2);
 487     }
 488   return m_oracle->query_relation (bb, ssa1, ssa2);
 489 }