/* 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;
}