blob: 0a6de62d7638e6652841be2d4739c34e9a3dcc46 [file]
/* Support routines for value queries.
Copyright (C) 2020-2026 Free Software Foundation, Inc.
Contributed by Aldy Hernandez <aldyh@redhat.com> and
Andrew MacLeod <amacleod@redhat.com>.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "ssa.h"
#include "tree-ssanames.h"
#include "fold-const.h"
#include "value-query.h"
#include "alloc-pool.h"
#include "gimple-range.h"
#include "value-range-storage.h"
#include "target.h"
// Attempt to make Q the current range query for FUN. If it is already the
// current range query, return NULL.
// If the specified query is not compatible with being the current query,
// instead push the global query for safety. This is most common when
// the requested query is a path ranger, and it can be unstable to make
// arbitrary queries which may be in the middle or after a path.
range_query *
set_range_query (struct function *fun, range_query *q)
{
// Set the global query if it hasn't been set.
if (!fun->x_range_query)
fun->x_range_query = get_global_range_query ();
// If this is not a compatible range query, revert to the global query.
if (!q->active_query_compatible_p ())
q = get_global_range_query ();
if (q == fun->x_range_query)
return NULL;
range_query *orig = fun->x_range_query;
fun->x_range_query = q;
return orig;
}
// range_query default methods.
bool
range_query::range_on_edge (vrange &r, edge, tree expr)
{
return range_of_expr (r, expr);
}
bool
range_query::range_on_entry (vrange &r, basic_block, tree expr)
{
return range_of_expr (r, expr);
}
bool
range_query::range_on_exit (vrange &r, basic_block, tree expr)
{
return range_of_expr (r, expr);
}
bool
range_query::range_of_stmt (vrange &r, gimple *stmt, tree name)
{
if (!name)
name = gimple_get_lhs (stmt);
gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
if (name)
return range_of_expr (r, name);
return false;
}
// Default for updating range info is to do nothing.
void
range_query::update_range_info (tree)
{
}
// Default for updating range info is to do nothing.
void
range_query::update_range_info (tree, const vrange &)
{
}
// Default for resetting range info for NAME is to clear the oracles.
void
range_query::reset_range_info (tree name)
{
relation ().clear (name);
if (gori_ssa ())
gori_ssa ()->clear (name);
infer_oracle ().clear (name);
}
// If the range of expr EXPR at STMT is a single value, return it.
// Otherwise return NULL_TREE.
tree
range_query::value_of_expr (tree expr, gimple *stmt)
{
tree t;
if (!value_range::supports_type_p (TREE_TYPE (expr)))
return NULL_TREE;
value_range r (TREE_TYPE (expr));
if (range_of_expr (r, expr, stmt))
{
// A constant used in an unreachable block often returns as UNDEFINED.
// If the result is undefined, check the global value for a constant.
if (r.undefined_p ())
range_of_expr (r, expr);
if (r.singleton_p (&t))
return t;
}
return NULL_TREE;
}
// If the range on edge E for EXPR is a single value, return it.
// Otherwise return NULL_TREE.
tree
range_query::value_on_edge (edge e, tree expr)
{
tree t;
if (!value_range::supports_type_p (TREE_TYPE (expr)))
return NULL_TREE;
value_range r (TREE_TYPE (expr));
if (range_on_edge (r, e, expr))
{
// A constant used in an unreachable block often returns as UNDEFINED.
// If the result is undefined, check the global value for a constant.
if (r.undefined_p ())
range_of_expr (r, expr);
if (r.singleton_p (&t))
return t;
}
return NULL_TREE;
}
// If the range of STMT for NAME is a single value, return it.
// Otherwise return NULL_TREE.
tree
range_query::value_of_stmt (gimple *stmt, tree name)
{
tree t;
if (!name)
name = gimple_get_lhs (stmt);
gcc_checking_assert (!name || name == gimple_get_lhs (stmt));
if (!name || !value_range::supports_type_p (TREE_TYPE (name)))
return NULL_TREE;
value_range r (TREE_TYPE (name));
if (range_of_stmt (r, stmt, name) && r.singleton_p (&t))
return t;
return NULL_TREE;
}
// If the range on entry to BB for EXPR is a single value, return it.
// Otherwise return NULL_TREE.
tree
range_query::value_on_entry (basic_block bb, tree expr)
{
tree t;
gcc_checking_assert (bb);
if (!value_range::supports_type_p (TREE_TYPE (expr)))
return NULL_TREE;
value_range r (TREE_TYPE (expr));
if (range_on_entry (r, bb, expr) && r.singleton_p (&t))
return t;
return NULL_TREE;
}
// If the range on exit to BB for EXPR is a single value, return it.
// Otherwise return NULL_TREE.
tree
range_query::value_on_exit (basic_block bb, tree expr)
{
tree t;
gcc_checking_assert (bb);
if (!value_range::supports_type_p (TREE_TYPE (expr)))
return NULL_TREE;
value_range r (TREE_TYPE (expr));
if (range_on_exit (r, bb, expr) && r.singleton_p (&t))
return t;
return NULL_TREE;
}
void
range_query::dump (FILE *)
{
}
// Default oracle for all range queries. This contains no storage and thus
// can be used anywhere.
relation_oracle default_relation_oracle;
infer_range_oracle default_infer_oracle;
gimple_outgoing_range default_gori;
void
range_query::create_gori (int not_executable_flag, int sw_max_edges)
{
gcc_checking_assert (m_gori == &default_gori);
gcc_checking_assert (m_map == NULL);
m_map = new gori_map ();
gcc_checking_assert (m_map);
m_gori = new gori_compute (*m_map, not_executable_flag, sw_max_edges);
gcc_checking_assert (m_gori);
}
void
range_query::destroy_gori ()
{
if (m_gori && m_gori != &default_gori)
delete m_gori;
if (m_map)
delete m_map;
m_map = NULL;
m_gori= &default_gori;
}
// Create an infer oracle using Q as the default range query if needed.
// if DO_SEARCH is true, use immediate uses to scan alluses of a NAME the first
// time it is queried. This is primarily for passes which operate in the
// on-demand model where earlier uses may not have been seen.
// VRP and DOM walk passes set this to FALSE as they will walk all statements
// in order.
void
range_query::create_infer_oracle (range_query *q, bool do_search)
{
gcc_checking_assert (m_infer == &default_infer_oracle);
m_infer = new infer_range_manager (do_search, q);
gcc_checking_assert (m_infer);
}
void
range_query::destroy_infer_oracle ()
{
if (m_infer && m_infer != &default_infer_oracle)
delete m_infer;
m_infer = &default_infer_oracle;
}
// Create dominance based range oracle for the current query if dom info is
// available.
void
range_query::create_relation_oracle ()
{
gcc_checking_assert (this != &global_ranges);
gcc_checking_assert (m_relation == &default_relation_oracle);
if (!dom_info_available_p (CDI_DOMINATORS))
return;
m_relation = new dom_oracle ();
gcc_checking_assert (m_relation);
}
// Destroy any relation oracle that was created.
void
range_query::destroy_relation_oracle ()
{
// m_relation can be NULL if a derived range_query class took care of
// disposing its own oracle.
if (m_relation && m_relation != &default_relation_oracle)
{
delete m_relation;
m_relation = &default_relation_oracle;
}
}
void
range_query::share_query (range_query &q)
{
m_relation = q.m_relation;
m_infer = q.m_infer;
m_gori = q.m_gori;
m_map = q.m_map;
m_shared_copy_p = true;
}
range_query::range_query ()
{
m_relation = &default_relation_oracle;
m_infer = &default_infer_oracle;
m_gori = &default_gori;
m_map = NULL;
m_shared_copy_p = false;
}
range_query::~range_query ()
{
// Do not destroy anything if this is a shared copy.
if (m_shared_copy_p)
return;
destroy_gori ();
destroy_infer_oracle ();
destroy_relation_oracle ();
}
// This routine will invoke the equivalent of range_of_expr on
// either a gimple statement STMT, on entry to block BBENTRY, or on
// exit from block BBEXIT. Only one of these 3 fields may be set.
// It is valid for none of them to be set, in wqhich case there is no context.
bool
range_query::invoke_range_of_expr (vrange &r, tree expr, gimple *stmt,
basic_block bbentry, basic_block bbexit,
edge e)
{
if (bbentry)
{
gcc_checking_assert (!stmt && !bbexit && !e);
return range_on_entry (r, bbentry, expr);
}
if (bbexit)
{
gcc_checking_assert (!stmt && !e);
return range_on_exit (r, bbexit, expr);
}
if (e)
{
gcc_checking_assert (!stmt);
return range_on_edge (r, e, expr);
}
return range_of_expr (r, expr, stmt);
}
// Return a range in R for the tree EXPR. The context can be either a STMT,
// or on entry to block BBENTRY or exit from block BBEXIT.
// Return true if a range is representable, and UNDEFINED/false if not.
bool
range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
basic_block bbentry, basic_block bbexit, edge e)
{
tree type;
if (TYPE_P (expr))
type = expr;
else
type = TREE_TYPE (expr);
if (!r.supports_type_p (type))
{
r.set_undefined ();
return false;
}
if (expr == type)
{
r.set_varying (type);
return true;
}
switch (TREE_CODE (expr))
{
case INTEGER_CST:
{
if (TREE_OVERFLOW_P (expr))
expr = drop_tree_overflow (expr);
r.set (expr, expr);
return true;
}
case REAL_CST:
{
frange &f = as_a <frange> (r);
REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (expr);
if (real_isnan (rv))
{
bool sign = real_isneg (rv);
f.set_nan (TREE_TYPE (expr), sign);
}
else
{
nan_state nan (false);
f.set (TREE_TYPE (expr), *rv, *rv, nan);
}
return true;
}
case SSA_NAME:
// If this is not an abnormal or virtual ssa, invoke range_of_expr.
if (gimple_range_ssa_p (expr))
return invoke_range_of_expr (r, expr, stmt, bbentry, bbexit, e);
gimple_range_global (r, expr);
return true;
case ADDR_EXPR:
{
// Handle &expr, and set points to.
if (tree_single_nonzero_p (expr))
r.set_nonzero (type);
else
r.set_varying (type);
// Set points to field.
gcc_checking_assert (is_a <prange> (r));
prange &ptr = as_a <prange> (r);
ptr.set_addr (expr, true);
return true;
}
default:
if (POLY_INT_CST_P (expr))
{
unsigned int precision = TYPE_PRECISION (type);
signop sign = TYPE_SIGN (type);
bool have_poly_bound = targetm.poly_int_indeterminate_bound;
poly_uint64 indeterminate_bound;
if (have_poly_bound)
indeterminate_bound = targetm.poly_int_indeterminate_bound ();
auto val = wi::to_poly_wide (expr);
auto type_min = wi::to_wide (TYPE_MIN_VALUE (type));
auto type_max = wi::to_wide (TYPE_MAX_VALUE (type));
/* Start with the invariant part of the poly-int, then account
for each coefficient below.
The target hook gives a per-coefficient upper bound for the
indeterminate. Since those indeterminates are unsigned and
nonnegative, a positive coefficient can only increase the upper
bound and a negative coefficient can only decrease the lower
bound. The opposite bound is unaffected by that coefficient:
[A, +C] with C >= 0 => max += C * bound
[A, -C] with C >= 0 => min -= C * bound. */
wide_int bounds[2] = { val.coeffs[0], val.coeffs[0] };
bool ovf[2] = { false, false };
for (unsigned int i = 1; i < NUM_POLY_INT_COEFFS; ++i)
{
const auto &coeff = val.coeffs[i];
if (wi::eq_p (coeff, 0))
continue;
/* Select the only bound affected by this coefficient. A
negative coefficient contributes to the minimum and a positive
coefficient contributes to the maximum. */
bool coeff_neg = wi::neg_p (coeff, sign);
wide_int &bound = bounds[coeff_neg ? 0 : 1];
bool &bound_ovf = ovf[coeff_neg ? 0 : 1];
if (bound_ovf)
continue;
/* A missing hook, or a -1 bound for this coefficient, means the
indeterminate has no finite target-specific limit. Treat that
like an overflow of the affected bound. */
if (!have_poly_bound
|| indeterminate_bound.coeffs[i] == HOST_WIDE_INT_M1U)
bound_ovf = true;
else
{
auto indeterminate
= wi::uhwi (indeterminate_bound.coeffs[i], precision);
wi::overflow_type mul_ovf = wi::OVF_NONE;
auto term = wi::mul (coeff, indeterminate, sign, &mul_ovf);
wi::overflow_type add_ovf = wi::OVF_NONE;
bound = wi::add (bound, term, sign, &add_ovf);
bound_ovf = (mul_ovf != wi::OVF_NONE
|| add_ovf != wi::OVF_NONE);
}
if (TYPE_OVERFLOW_WRAPS (type) && bound_ovf)
{
r.set_varying (type);
r.update_bitmask (irange_bitmask (wi::zero (precision),
get_nonzero_bits (expr)));
return true;
}
if (bound_ovf)
{
if (coeff_neg)
bounds[0] = type_min;
else
bounds[1] = type_max;
}
}
/* Check that the target filled in sensible bounds information. */
gcc_assert (wi::le_p (bounds[0], bounds[1], sign));
irange &ir = as_a <irange> (r);
ir.set (type, bounds[0], bounds[1]);
/* Preserve alignment/step information that is not visible in the
intervals. For example, a poly-int like [8, 8] can
only produce multiples of 8, but the interval range might be
[8, 136], which also contains values with low bits set. */
ir.update_bitmask (irange_bitmask (wi::zero (precision),
get_nonzero_bits (expr)));
return true;
}
break;
}
if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
{
tree op0 = TREE_OPERAND (expr, 0);
tree op1 = TREE_OPERAND (expr, 1);
if (COMPARISON_CLASS_P (expr)
&& !value_range::supports_type_p (TREE_TYPE (op0)))
return false;
range_op_handler op (TREE_CODE (expr));
if (op)
{
value_range r0 (TREE_TYPE (op0));
value_range r1 (TREE_TYPE (op1));
invoke_range_of_expr (r0, op0, stmt, bbentry, bbexit, e);
invoke_range_of_expr (r1, op1, stmt, bbentry, bbexit, e);
if (!op.fold_range (r, type, r0, r1))
r.set_varying (type);
}
else
r.set_varying (type);
return true;
}
if (UNARY_CLASS_P (expr))
{
range_op_handler op (TREE_CODE (expr));
tree op0_type = TREE_TYPE (TREE_OPERAND (expr, 0));
if (op && value_range::supports_type_p (op0_type))
{
value_range r0 (TREE_TYPE (TREE_OPERAND (expr, 0)));
value_range r1 (type);
r1.set_varying (type);
invoke_range_of_expr (r0, TREE_OPERAND (expr, 0), stmt, bbentry,
bbexit, e);
if (!op.fold_range (r, type, r0, r1))
r.set_varying (type);
}
else
r.set_varying (type);
return true;
}
r.set_varying (type);
return true;
}
// Return the range for NAME from SSA_NAME_RANGE_INFO.
static inline void
get_ssa_name_range_info (vrange &r, const_tree name)
{
tree type = TREE_TYPE (name);
gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
vrange_storage *ri = SSA_NAME_RANGE_INFO (name);
if (ri)
ri->get_vrange (r, TREE_TYPE (name));
else
r.set_varying (type);
}
// Update the global range for NAME into the SSA_RANGE_NAME_INFO and
// Return the legacy global range for NAME if it has one, otherwise
// return VARYING.
// See discussion here regarding why there use to be a wrapper function:
// https://gcc.gnu.org/pipermail/gcc-patches/2021-June/571709.html
// Legacy EVRP has been removed, leaving just this function.
void
gimple_range_global (vrange &r, tree name, struct function *fun)
{
tree type = TREE_TYPE (name);
gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
if (SSA_NAME_IS_DEFAULT_DEF (name))
{
tree sym = SSA_NAME_VAR (name);
// Adapted from vr_values::get_lattice_entry().
// Use a range from an SSA_NAME's available range.
if (TREE_CODE (sym) == PARM_DECL)
{
get_ssa_name_range_info (r, name);
if (r.undefined_p ())
r.set_varying (type);
// Try to use the "nonnull" attribute to refine a pointer to
// ~[0, 0]. Note that this is only valid with default definitions
// of PARM_DECLs
if (POINTER_TYPE_P (type)
&& ((cfun && fun == cfun && nonnull_arg_p (sym))))
{
prange nz (type);
nz.set_nonzero (type);
r.intersect (nz);
}
}
// If this is a local automatic with no definition, use undefined.
else if (TREE_CODE (sym) != RESULT_DECL)
r.set_undefined ();
else
r.set_varying (type);
}
else if (SSA_NAME_RANGE_INFO (name))
{
get_ssa_name_range_info (r, name);
if (r.undefined_p ())
r.set_varying (type);
}
else
r.set_varying (type);
}
// ----------------------------------------------
// global_range_query implementation.
global_range_query global_ranges;
bool
global_range_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
{
if (!gimple_range_ssa_p (expr))
return get_tree_range (r, expr, stmt);
gimple_range_global (r, expr);
return true;
}