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