diff options
Diffstat (limited to 'gcc/gimple-range.cc')
| -rw-r--r-- | gcc/gimple-range.cc | 1425 |
1 files changed, 218 insertions, 1207 deletions
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index 6158a75..d74cea3 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -23,957 +23,73 @@ along with GCC; see the file COPYING3. If not see #include "system.h" #include "coretypes.h" #include "backend.h" -#include "insn-codes.h" -#include "rtl.h" #include "tree.h" #include "gimple.h" #include "ssa.h" #include "gimple-pretty-print.h" #include "gimple-iterator.h" -#include "optabs-tree.h" -#include "gimple-fold.h" #include "tree-cfg.h" #include "fold-const.h" #include "tree-cfg.h" -#include "wide-int.h" -#include "fold-const.h" -#include "case-cfn-macros.h" -#include "omp-general.h" #include "cfgloop.h" -#include "tree-ssa-loop.h" #include "tree-scalar-evolution.h" -#include "dbgcnt.h" -#include "alloc-pool.h" -#include "vr-values.h" #include "gimple-range.h" - -// Adjust the range for a pointer difference where the operands came -// from a memchr. -// -// This notices the following sequence: -// -// def = __builtin_memchr (arg, 0, sz) -// n = def - arg -// -// The range for N can be narrowed to [0, PTRDIFF_MAX - 1]. - -static void -adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt) -{ - tree op0 = gimple_assign_rhs1 (diff_stmt); - tree op1 = gimple_assign_rhs2 (diff_stmt); - tree op0_ptype = TREE_TYPE (TREE_TYPE (op0)); - tree op1_ptype = TREE_TYPE (TREE_TYPE (op1)); - gimple *call; - - if (TREE_CODE (op0) == SSA_NAME - && TREE_CODE (op1) == SSA_NAME - && (call = SSA_NAME_DEF_STMT (op0)) - && is_gimple_call (call) - && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) - && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node) - && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node) - && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node) - && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node) - && gimple_call_builtin_p (call, BUILT_IN_MEMCHR) - && vrp_operand_equal_p (op1, gimple_call_arg (call, 0)) - && integer_zerop (gimple_call_arg (call, 1))) - { - tree max = vrp_val_max (ptrdiff_type_node); - wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); - tree expr_type = gimple_expr_type (diff_stmt); - tree range_min = build_zero_cst (expr_type); - tree range_max = wide_int_to_tree (expr_type, wmax - 1); - int_range<2> r (range_min, range_max); - res.intersect (r); - } -} - -// This function looks for situations when walking the use/def chains -// may provide additonal contextual range information not exposed on -// this statement. Like knowing the IMAGPART return value from a -// builtin function is a boolean result. - -// We should rework how we're called, as we have an op_unknown entry -// for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this -// function gets called. - -static void -gimple_range_adjustment (irange &res, const gimple *stmt) -{ - switch (gimple_expr_code (stmt)) - { - case POINTER_DIFF_EXPR: - adjust_pointer_diff_expr (res, stmt); - return; - - case IMAGPART_EXPR: - { - tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); - if (TREE_CODE (name) == SSA_NAME) - { - gimple *def_stmt = SSA_NAME_DEF_STMT (name); - if (def_stmt && is_gimple_call (def_stmt) - && gimple_call_internal_p (def_stmt)) - { - switch (gimple_call_internal_fn (def_stmt)) - { - case IFN_ADD_OVERFLOW: - case IFN_SUB_OVERFLOW: - case IFN_MUL_OVERFLOW: - case IFN_ATOMIC_COMPARE_EXCHANGE: - { - int_range<2> r; - r.set_varying (boolean_type_node); - tree type = TREE_TYPE (gimple_assign_lhs (stmt)); - range_cast (r, type); - res.intersect (r); - } - default: - break; - } - } - } - break; - } - - default: - break; - } -} - -// Return a range in R for the tree EXPR. Return true if a range is -// representable, and UNDEFINED/false if not. - -bool -get_tree_range (irange &r, tree expr) -{ - tree type; - if (TYPE_P (expr)) - type = expr; - else - type = TREE_TYPE (expr); - - // Return false if the type isn't suported. - if (!irange::supports_type_p (type)) - { - r.set_undefined (); - return false; - } - - switch (TREE_CODE (expr)) - { - case INTEGER_CST: - if (TREE_OVERFLOW_P (expr)) - expr = drop_tree_overflow (expr); - r.set (expr, expr); - return true; - - case SSA_NAME: - r = gimple_range_global (expr); - return true; - - case ADDR_EXPR: - { - // Handle &var which can show up in phi arguments. - bool ov; - if (tree_single_nonzero_warnv_p (expr, &ov)) - { - r = range_nonzero (type); - return true; - } - break; - } - - default: - break; - } - r.set_varying (type); - return true; -} - -// Fold this unary statement using R1 as operand1's range, returning -// the result in RES. Return false if the operation fails. - -bool -gimple_range_fold (irange &res, const gimple *stmt, const irange &r1) -{ - gcc_checking_assert (gimple_range_handler (stmt)); - - tree type = gimple_expr_type (stmt); - // Unary SSA operations require the LHS type as the second range. - int_range<2> r2 (type); - - return gimple_range_fold (res, stmt, r1, r2); -} - -// Fold this binary statement using R1 and R2 as the operands ranges, -// returning the result in RES. Return false if the operation fails. - -bool -gimple_range_fold (irange &res, const gimple *stmt, - const irange &r1, const irange &r2) -{ - gcc_checking_assert (gimple_range_handler (stmt)); - - gimple_range_handler (stmt)->fold_range (res, gimple_expr_type (stmt), - r1, r2); - - // If there are any gimple lookups, do those now. - gimple_range_adjustment (res, stmt); - return true; -} - -// Return the base of the RHS of an assignment. - -tree -gimple_range_base_of_assignment (const gimple *stmt) -{ - gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); - tree op1 = gimple_assign_rhs1 (stmt); - if (gimple_assign_rhs_code (stmt) == ADDR_EXPR) - return get_base_address (TREE_OPERAND (op1, 0)); - return op1; -} - -// Return the first operand of this statement if it is a valid operand -// supported by ranges, otherwise return NULL_TREE. Special case is -// &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr. - -tree -gimple_range_operand1 (const gimple *stmt) -{ - gcc_checking_assert (gimple_range_handler (stmt)); - - switch (gimple_code (stmt)) - { - case GIMPLE_COND: - return gimple_cond_lhs (stmt); - case GIMPLE_ASSIGN: - { - tree base = gimple_range_base_of_assignment (stmt); - if (base && TREE_CODE (base) == MEM_REF) - { - // If the base address is an SSA_NAME, we return it - // here. This allows processing of the range of that - // name, while the rest of the expression is simply - // ignored. The code in range_ops will see the - // ADDR_EXPR and do the right thing. - tree ssa = TREE_OPERAND (base, 0); - if (TREE_CODE (ssa) == SSA_NAME) - return ssa; - } - return base; - } - default: - break; - } - return NULL; -} - -// Return the second operand of statement STMT, otherwise return NULL_TREE. - -tree -gimple_range_operand2 (const gimple *stmt) -{ - gcc_checking_assert (gimple_range_handler (stmt)); - - switch (gimple_code (stmt)) - { - case GIMPLE_COND: - return gimple_cond_rhs (stmt); - case GIMPLE_ASSIGN: - if (gimple_num_ops (stmt) >= 3) - return gimple_assign_rhs2 (stmt); - default: - break; - } - return NULL_TREE; -} - -// Calculate what we can determine of the range of this unary -// statement's operand if the lhs of the expression has the range -// LHS_RANGE. Return false if nothing can be determined. - -bool -gimple_range_calc_op1 (irange &r, const gimple *stmt, const irange &lhs_range) -{ - gcc_checking_assert (gimple_num_ops (stmt) < 3); - - // An empty range is viral. - tree type = TREE_TYPE (gimple_range_operand1 (stmt)); - if (lhs_range.undefined_p ()) - { - r.set_undefined (); - return true; - } - // Unary operations require the type of the first operand in the - // second range position. - int_range<2> type_range (type); - return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, - type_range); -} - -// Calculate what we can determine of the range of this statement's -// first operand if the lhs of the expression has the range LHS_RANGE -// and the second operand has the range OP2_RANGE. Return false if -// nothing can be determined. - -bool -gimple_range_calc_op1 (irange &r, const gimple *stmt, - const irange &lhs_range, const irange &op2_range) -{ - // Unary operation are allowed to pass a range in for second operand - // as there are often additional restrictions beyond the type which - // can be imposed. See operator_cast::op1_range(). - tree type = TREE_TYPE (gimple_range_operand1 (stmt)); - // An empty range is viral. - if (op2_range.undefined_p () || lhs_range.undefined_p ()) - { - r.set_undefined (); - return true; - } - return gimple_range_handler (stmt)->op1_range (r, type, lhs_range, - op2_range); -} - -// Calculate what we can determine of the range of this statement's -// second operand if the lhs of the expression has the range LHS_RANGE -// and the first operand has the range OP1_RANGE. Return false if -// nothing can be determined. - -bool -gimple_range_calc_op2 (irange &r, const gimple *stmt, - const irange &lhs_range, const irange &op1_range) -{ - tree type = TREE_TYPE (gimple_range_operand2 (stmt)); - // An empty range is viral. - if (op1_range.undefined_p () || lhs_range.undefined_p ()) - { - r.set_undefined (); - return true; - } - return gimple_range_handler (stmt)->op2_range (r, type, lhs_range, - op1_range); -} - -// Calculate a range for statement S and return it in R. If NAME is provided it -// represents the SSA_NAME on the LHS of the statement. It is only required -// if there is more than one lhs/output. If a range cannot -// be calculated, return false. - -bool -gimple_ranger::calc_stmt (irange &r, gimple *s, tree name) -{ - bool res = false; - // If name is specified, make sure it is an LHS of S. - gcc_checking_assert (name ? SSA_NAME_DEF_STMT (name) == s : true); - - if (gimple_range_handler (s)) - res = range_of_range_op (r, s); - else if (is_a<gphi *>(s)) - res = range_of_phi (r, as_a<gphi *> (s)); - else if (is_a<gcall *>(s)) - res = range_of_call (r, as_a<gcall *> (s)); - else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR) - res = range_of_cond_expr (r, as_a<gassign *> (s)); - - if (!res) - { - // If no name is specified, try the expression kind. - if (!name) - { - tree t = gimple_expr_type (s); - if (!irange::supports_type_p (t)) - return false; - r.set_varying (t); - return true; - } - if (!gimple_range_ssa_p (name)) - return false; - // We don't understand the stmt, so return the global range. - r = gimple_range_global (name); - return true; - } - - if (r.undefined_p ()) - return true; - - // We sometimes get compatible types copied from operands, make sure - // the correct type is being returned. - if (name && TREE_TYPE (name) != r.type ()) - { - gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name))); - range_cast (r, TREE_TYPE (name)); - } - return true; -} - -// Calculate a range for range_op statement S and return it in R. If any -// If a range cannot be calculated, return false. - -bool -gimple_ranger::range_of_range_op (irange &r, gimple *s) +gimple_ranger::gimple_ranger () : tracer ("") { - int_range_max range1, range2; - tree lhs = gimple_get_lhs (s); - tree type = gimple_expr_type (s); - gcc_checking_assert (irange::supports_type_p (type)); - - tree op1 = gimple_range_operand1 (s); - tree op2 = gimple_range_operand2 (s); - - if (lhs) - { - // Register potential dependencies for stale value tracking. - m_cache.register_dependency (lhs, op1); - m_cache.register_dependency (lhs, op2); - } - - if (gimple_code (s) == GIMPLE_ASSIGN - && gimple_assign_rhs_code (s) == ADDR_EXPR) - return range_of_address (r, s); - - if (range_of_expr (range1, op1, s)) - { - if (!op2) - return gimple_range_fold (r, s, range1); - - if (range_of_expr (range2, op2, s)) - return gimple_range_fold (r, s, range1, range2); - } - r.set_varying (type); - return true; + // If the cache has a relation oracle, use it. + m_oracle = m_cache.oracle (); + if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) + tracer.enable_trace (); } -// Calculate the range of an assignment containing an ADDR_EXPR. -// Return the range in R. -// If a range cannot be calculated, set it to VARYING and return true. - bool -gimple_ranger::range_of_address (irange &r, gimple *stmt) -{ - gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN); - gcc_checking_assert (gimple_assign_rhs_code (stmt) == ADDR_EXPR); - - bool strict_overflow_p; - tree expr = gimple_assign_rhs1 (stmt); - poly_int64 bitsize, bitpos; - tree offset; - machine_mode mode; - int unsignedp, reversep, volatilep; - tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, - &bitpos, &offset, &mode, &unsignedp, - &reversep, &volatilep); - - - if (base != NULL_TREE - && TREE_CODE (base) == MEM_REF - && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) - { - tree ssa = TREE_OPERAND (base, 0); - gcc_checking_assert (irange::supports_type_p (TREE_TYPE (ssa))); - range_of_expr (r, ssa, stmt); - range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt))); - - poly_offset_int off = 0; - bool off_cst = false; - if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST) - { - off = mem_ref_offset (base); - if (offset) - off += poly_offset_int::from (wi::to_poly_wide (offset), - SIGNED); - off <<= LOG2_BITS_PER_UNIT; - off += bitpos; - off_cst = true; - } - /* If &X->a is equal to X, the range of X is the result. */ - if (off_cst && known_eq (off, 0)) - return true; - else if (flag_delete_null_pointer_checks - && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))) - { - /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't - allow going from non-NULL pointer to NULL. */ - if(!range_includes_zero_p (&r)) - return true; - } - /* If MEM_REF has a "positive" offset, consider it non-NULL - always, for -fdelete-null-pointer-checks also "negative" - ones. Punt for unknown offsets (e.g. variable ones). */ - if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)) - && off_cst - && known_ne (off, 0) - && (flag_delete_null_pointer_checks || known_gt (off, 0))) - { - r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); - return true; - } - r = int_range<2> (TREE_TYPE (gimple_assign_rhs1 (stmt))); - return true; - } - - // Handle "= &a". - if (tree_single_nonzero_warnv_p (expr, &strict_overflow_p)) - { - r = range_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt))); - return true; - } - - // Otherwise return varying. - r = int_range<2> (TREE_TYPE (gimple_assign_rhs1 (stmt))); - return true; -} - -// Calculate a range for phi statement S and return it in R. -// If a range cannot be calculated, return false. - -bool -gimple_ranger::range_of_phi (irange &r, gphi *phi) -{ - tree phi_def = gimple_phi_result (phi); - tree type = TREE_TYPE (phi_def); - int_range_max arg_range; - unsigned x; - - if (!irange::supports_type_p (type)) - return false; - - // Start with an empty range, unioning in each argument's range. - r.set_undefined (); - for (x = 0; x < gimple_phi_num_args (phi); x++) - { - tree arg = gimple_phi_arg_def (phi, x); - edge e = gimple_phi_arg_edge (phi, x); - - // Register potential dependencies for stale value tracking. - m_cache.register_dependency (phi_def, arg); - - range_on_edge (arg_range, e, arg); - r.union_ (arg_range); - // Once the value reaches varying, stop looking. - if (r.varying_p ()) - break; - } - - // If SCEV is available, query if this PHI has any knonwn values. - if (scev_initialized_p () && !POINTER_TYPE_P (TREE_TYPE (phi_def))) - { - value_range loop_range; - class loop *l = loop_containing_stmt (phi); - if (l && loop_outer (l)) - { - range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi); - if (!loop_range.varying_p ()) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, " Loops range found for "); - print_generic_expr (dump_file, phi_def, TDF_SLIM); - fprintf (dump_file, ": "); - loop_range.dump (dump_file); - fprintf (dump_file, " and calculated range :"); - r.dump (dump_file); - fprintf (dump_file, "\n"); - } - r.intersect (loop_range); - } - } - } - - return true; -} - -// Calculate a range for call statement S and return it in R. -// If a range cannot be calculated, return false. - -bool -gimple_ranger::range_of_call (irange &r, gcall *call) -{ - tree type = gimple_call_return_type (call); - tree lhs = gimple_call_lhs (call); - bool strict_overflow_p; - - if (!irange::supports_type_p (type)) - return false; - - if (range_of_builtin_call (r, call)) - ; - else if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p)) - r.set (build_int_cst (type, 0), TYPE_MAX_VALUE (type)); - else if (gimple_call_nonnull_result_p (call) - || gimple_call_nonnull_arg (call)) - r = range_nonzero (type); - else - r.set_varying (type); - - // If there is an LHS, intersect that with what is known. - if (lhs) - { - value_range def; - def = gimple_range_global (lhs); - r.intersect (def); - } - return true; -} - -// Return the range of a __builtin_ubsan* in CALL and set it in R. -// CODE is the type of ubsan call (PLUS_EXPR, MINUS_EXPR or -// MULT_EXPR). - -static void -range_of_builtin_ubsan_call (range_query &query, irange &r, gcall *call, - tree_code code) -{ - gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR - || code == MULT_EXPR); - tree type = gimple_call_return_type (call); - range_operator *op = range_op_handler (code, type); - gcc_checking_assert (op); - int_range_max ir0, ir1; - tree arg0 = gimple_call_arg (call, 0); - tree arg1 = gimple_call_arg (call, 1); - query.range_of_expr (ir0, arg0, call); - query.range_of_expr (ir1, arg1, call); - - bool saved_flag_wrapv = flag_wrapv; - // Pretend the arithmetic is wrapping. If there is any overflow, - // we'll complain, but will actually do wrapping operation. - flag_wrapv = 1; - op->fold_range (r, type, ir0, ir1); - flag_wrapv = saved_flag_wrapv; - - // If for both arguments vrp_valueize returned non-NULL, this should - // have been already folded and if not, it wasn't folded because of - // overflow. Avoid removing the UBSAN_CHECK_* calls in that case. - if (r.singleton_p ()) - r.set_varying (type); -} - -// For a builtin in CALL, return a range in R if known and return -// TRUE. Otherwise return FALSE. - -bool -range_of_builtin_call (range_query &query, irange &r, gcall *call) +gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) { - combined_fn func = gimple_call_combined_fn (call); - if (func == CFN_LAST) - return false; - - tree type = gimple_call_return_type (call); - tree arg; - int mini, maxi, zerov = 0, prec; - scalar_int_mode mode; + unsigned idx; + if (!gimple_range_ssa_p (expr)) + return get_tree_range (r, expr, stmt); - switch (func) + if ((idx = tracer.header ("range_of_expr("))) { - case CFN_BUILT_IN_CONSTANT_P: - if (cfun->after_inlining) - { - r.set_zero (type); - // r.equiv_clear (); - return true; - } - arg = gimple_call_arg (call, 0); - if (query.range_of_expr (r, arg, call) && r.singleton_p ()) - { - r.set (build_one_cst (type), build_one_cst (type)); - return true; - } - break; - - CASE_CFN_FFS: - CASE_CFN_POPCOUNT: - // __builtin_ffs* and __builtin_popcount* return [0, prec]. - arg = gimple_call_arg (call, 0); - prec = TYPE_PRECISION (TREE_TYPE (arg)); - mini = 0; - maxi = prec; - query.range_of_expr (r, arg, call); - // If arg is non-zero, then ffs or popcount are non-zero. - if (!range_includes_zero_p (&r)) - mini = 1; - // If some high bits are known to be zero, decrease the maximum. - if (!r.undefined_p ()) - { - if (TYPE_SIGN (r.type ()) == SIGNED) - range_cast (r, unsigned_type_for (r.type ())); - wide_int max = r.upper_bound (); - maxi = wi::floor_log2 (max) + 1; - } - r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); - return true; - - CASE_CFN_PARITY: - r.set (build_zero_cst (type), build_one_cst (type)); - return true; - - CASE_CFN_CLZ: - // __builtin_c[lt]z* return [0, prec-1], except when the - // argument is 0, but that is undefined behavior. - // - // For __builtin_c[lt]z* consider argument of 0 always undefined - // behavior, for internal fns depending on C?Z_DEFINED_VALUE_AT_ZERO. - arg = gimple_call_arg (call, 0); - prec = TYPE_PRECISION (TREE_TYPE (arg)); - mini = 0; - maxi = prec - 1; - mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); - if (gimple_call_internal_p (call)) - { - if (optab_handler (clz_optab, mode) != CODE_FOR_nothing - && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) - { - // Only handle the single common value. - if (zerov == prec) - maxi = prec; - else - // Magic value to give up, unless we can prove arg is non-zero. - mini = -2; - } - } - - query.range_of_expr (r, arg, call); - // From clz of minimum we can compute result maximum. - if (r.constant_p ()) - { - int newmaxi = prec - 1 - wi::floor_log2 (r.lower_bound ()); - // Argument is unsigned, so do nothing if it is [0, ...] range. - if (newmaxi != prec) - { - mini = 0; - maxi = newmaxi; - } - } - else if (!range_includes_zero_p (&r)) - { - maxi = prec - 1; - mini = 0; - } - if (mini == -2) - break; - // From clz of maximum we can compute result minimum. - if (r.constant_p ()) - { - int newmini = prec - 1 - wi::floor_log2 (r.upper_bound ()); - if (newmini == prec) - { - // Argument range is [0, 0]. If CLZ_DEFINED_VALUE_AT_ZERO - // is 2 with VALUE of prec, return [prec, prec], otherwise - // ignore the range. - if (maxi == prec) - mini = prec; - } - else - mini = newmini; - } - if (mini == -2) - break; - r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); - return true; - - CASE_CFN_CTZ: - // __builtin_ctz* return [0, prec-1], except for when the - // argument is 0, but that is undefined behavior. - // - // For __builtin_ctz* consider argument of 0 always undefined - // behavior, for internal fns depending on CTZ_DEFINED_VALUE_AT_ZERO. - arg = gimple_call_arg (call, 0); - prec = TYPE_PRECISION (TREE_TYPE (arg)); - mini = 0; - maxi = prec - 1; - mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); - if (gimple_call_internal_p (call)) - { - if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing - && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov) == 2) - { - // Handle only the two common values. - if (zerov == -1) - mini = -1; - else if (zerov == prec) - maxi = prec; - else - // Magic value to give up, unless we can prove arg is non-zero. - mini = -2; - } - } - query.range_of_expr (r, arg, call); - if (!r.undefined_p ()) + print_generic_expr (dump_file, expr, TDF_SLIM); + fputs (")", dump_file); + if (stmt) { - if (r.lower_bound () != 0) - { - mini = 0; - maxi = prec - 1; - } - // If some high bits are known to be zero, we can decrease - // the maximum. - wide_int max = r.upper_bound (); - if (max == 0) - { - // Argument is [0, 0]. If CTZ_DEFINED_VALUE_AT_ZERO - // is 2 with value -1 or prec, return [-1, -1] or [prec, prec]. - // Otherwise ignore the range. - if (mini == -1) - maxi = -1; - else if (maxi == prec) - mini = prec; - } - // If value at zero is prec and 0 is in the range, we can't lower - // the upper bound. We could create two separate ranges though, - // [0,floor_log2(max)][prec,prec] though. - else if (maxi != prec) - maxi = wi::floor_log2 (max); + fputs (" at stmt ", dump_file); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } - if (mini == -2) - break; - r.set (build_int_cst (type, mini), build_int_cst (type, maxi)); - return true; - - CASE_CFN_CLRSB: - arg = gimple_call_arg (call, 0); - prec = TYPE_PRECISION (TREE_TYPE (arg)); - r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1)); - return true; - case CFN_UBSAN_CHECK_ADD: - range_of_builtin_ubsan_call (query, r, call, PLUS_EXPR); - return true; - case CFN_UBSAN_CHECK_SUB: - range_of_builtin_ubsan_call (query, r, call, MINUS_EXPR); - return true; - case CFN_UBSAN_CHECK_MUL: - range_of_builtin_ubsan_call (query, r, call, MULT_EXPR); - return true; - - case CFN_GOACC_DIM_SIZE: - case CFN_GOACC_DIM_POS: - // Optimizing these two internal functions helps the loop - // optimizer eliminate outer comparisons. Size is [1,N] - // and pos is [0,N-1]. - { - bool is_pos = func == CFN_GOACC_DIM_POS; - int axis = oacc_get_ifn_dim_arg (call); - int size = oacc_get_fn_dim_size (current_function_decl, axis); - if (!size) - // If it's dynamic, the backend might know a hardware limitation. - size = targetm.goacc.dim_limit (axis); - - r.set (build_int_cst (type, is_pos ? 0 : 1), - size - ? build_int_cst (type, size - is_pos) : vrp_val_max (type)); - return true; - } - - case CFN_BUILT_IN_STRLEN: - if (tree lhs = gimple_call_lhs (call)) - if (ptrdiff_type_node - && (TYPE_PRECISION (ptrdiff_type_node) - == TYPE_PRECISION (TREE_TYPE (lhs)))) - { - tree type = TREE_TYPE (lhs); - tree max = vrp_val_max (ptrdiff_type_node); - wide_int wmax - = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); - tree range_min = build_zero_cst (type); - // To account for the terminating NULL, the maximum length - // is one less than the maximum array size, which in turn - // is one less than PTRDIFF_MAX (or SIZE_MAX where it's - // smaller than the former type). - // FIXME: Use max_object_size() - 1 here. - tree range_max = wide_int_to_tree (type, wmax - 2); - r.set (range_min, range_max); - return true; - } - break; - default: - break; - } - return false; -} - - -bool -gimple_ranger::range_of_builtin_call (irange &r, gcall *call) -{ - return ::range_of_builtin_call (*this, r, call); -} - -// Calculate a range for COND_EXPR statement S and return it in R. -// If a range cannot be calculated, return false. - -bool -gimple_ranger::range_of_cond_expr (irange &r, gassign *s) -{ - int_range_max cond_range, range1, range2; - tree cond = gimple_assign_rhs1 (s); - tree op1 = gimple_assign_rhs2 (s); - tree op2 = gimple_assign_rhs3 (s); - - gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR); - gcc_checking_assert (useless_type_conversion_p (TREE_TYPE (op1), - TREE_TYPE (op2))); - if (!irange::supports_type_p (TREE_TYPE (op1))) - return false; - - range_of_expr (cond_range, cond, s); - range_of_expr (range1, op1, s); - range_of_expr (range2, op2, s); - - // If the condition is known, choose the appropriate expression. - if (cond_range.singleton_p ()) - { - // False, pick second operand. - if (cond_range.zero_p ()) - r = range2; else - r = range1; - } - else - { - r = range1; - r.union_ (range2); + fputs ("\n", dump_file); } - return true; -} - -bool -gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt) -{ - if (!gimple_range_ssa_p (expr)) - return get_tree_range (r, expr); // If there is no statement, just get the global value. if (!stmt) { if (!m_cache.get_global_range (r, expr)) r = gimple_range_global (expr); - return true; } - - basic_block bb = gimple_bb (stmt); - gimple *def_stmt = SSA_NAME_DEF_STMT (expr); - - // If name is defined in this block, try to get an range from S. - if (def_stmt && gimple_bb (def_stmt) == bb) - range_of_stmt (r, def_stmt, expr); + // For a debug stmt, pick the best value currently available, do not + // trigger new value calculations. PR 100781. + else if (is_gimple_debug (stmt)) + m_cache.range_of_expr (r, expr, stmt); else - // Otherwise OP comes from outside this block, use range on entry. - range_on_entry (r, bb, expr); - - // No range yet, see if there is a dereference in the block. - // We don't care if it's between the def and a use within a block - // because the entire block must be executed anyway. - // FIXME:?? For non-call exceptions we could have a statement throw - // which causes an early block exit. - // in which case we may need to walk from S back to the def/top of block - // to make sure the deref happens between S and there before claiming - // there is a deref. Punt for now. - if (!cfun->can_throw_non_call_exceptions && r.varying_p () && - m_cache.m_non_null.non_null_deref_p (expr, bb)) - r = range_nonzero (TREE_TYPE (expr)); + { + basic_block bb = gimple_bb (stmt); + gimple *def_stmt = SSA_NAME_DEF_STMT (expr); + // If name is defined in this block, try to get an range from S. + if (def_stmt && gimple_bb (def_stmt) == bb) + { + range_of_stmt (r, def_stmt, expr); + m_cache.m_non_null.adjust_range (r, expr, bb, true); + } + // Otherwise OP comes from outside this block, use range on entry. + else + range_on_entry (r, bb, expr); + } + if (idx) + tracer.trailer (idx, "range_of_expr", true, expr, r); return true; } @@ -985,12 +101,24 @@ gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name) int_range_max entry_range; gcc_checking_assert (gimple_range_ssa_p (name)); + unsigned idx; + if ((idx = tracer.header ("range_on_entry ("))) + { + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, ") to BB %d\n", bb->index); + } + // Start with any known range range_of_stmt (r, SSA_NAME_DEF_STMT (name), name); // Now see if there is any on_entry value which may refine it. if (m_cache.block_range (entry_range, bb, name)) r.intersect (entry_range); + + m_cache.m_non_null.adjust_range (r, name, bb, true); + + if (idx) + tracer.trailer (idx, "range_on_entry", true, name, r); } // Calculate the range for NAME at the end of block BB and return it in R. @@ -1003,16 +131,29 @@ gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name) gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); gcc_checking_assert (gimple_range_ssa_p (name)); - gimple *s = last_stmt (bb); - // If there is no statement in the block and this isn't the entry - // block, go get the range_on_entry for this block. For the entry - // block, a NULL stmt will return the global value for NAME. - if (!s && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)) - range_on_entry (r, bb, name); - else + unsigned idx; + if ((idx = tracer.header ("range_on_exit ("))) + { + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, ") from BB %d\n", bb->index); + } + + gimple *s = SSA_NAME_DEF_STMT (name); + basic_block def_bb = gimple_bb (s); + // If this is not the definition block, get the range on the last stmt in + // the block... if there is one. + if (def_bb != bb) + s = last_stmt (bb); + // If there is no statement provided, get the range_on_entry for this block. + if (s) range_of_expr (r, name, s); + else + range_on_entry (r, bb, name); gcc_checking_assert (r.undefined_p () || range_compatible_p (r.type (), TREE_TYPE (name))); + + if (idx) + tracer.trailer (idx, "range_on_exit", true, name, r); } // Calculate a range for NAME on edge E and return it in R. @@ -1027,17 +168,36 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name) if (!gimple_range_ssa_p (name)) return range_of_expr (r, name); + unsigned idx; + if ((idx = tracer.header ("range_on_edge ("))) + { + print_generic_expr (dump_file, name, TDF_SLIM); + fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index); + } + range_on_exit (r, e->src, name); gcc_checking_assert (r.undefined_p () || range_compatible_p (r.type(), TREE_TYPE (name))); // Check to see if NAME is defined on edge e. - if (m_cache.outgoing_edge_range_p (edge_range, e, name)) + if (m_cache.range_on_edge (edge_range, e, name)) r.intersect (edge_range); + if (idx) + tracer.trailer (idx, "range_on_edge", true, name, r); return true; } +// fold_range wrapper for range_of_stmt to use as an internal client. + +bool +gimple_ranger::fold_range_internal (irange &r, gimple *s, tree name) +{ + fold_using_range f; + fur_depend src (s, &(gori ()), this); + return f.fold_stmt (r, s, src, name); +} + // Calculate a range for statement S and return it in R. If NAME is // provided it represents the SSA_NAME on the LHS of the statement. // It is only required if there is more than one lhs/output. Check @@ -1047,84 +207,93 @@ gimple_ranger::range_on_edge (irange &r, edge e, tree name) bool gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) { + bool res; r.set_undefined (); + unsigned idx; + if ((idx = tracer.header ("range_of_stmt ("))) + { + if (name) + print_generic_expr (dump_file, name, TDF_SLIM); + fputs (") at stmt ", dump_file); + print_gimple_stmt (dump_file, s, 0, TDF_SLIM); + } + if (!name) name = gimple_get_lhs (s); // If no name, simply call the base routine. if (!name) - return calc_stmt (r, s, NULL_TREE); - - if (!gimple_range_ssa_p (name)) - return false; - + res = fold_range_internal (r, s, NULL_TREE); + else if (!gimple_range_ssa_p (name)) + res = false; // Check if the stmt has already been processed, and is not stale. - if (m_cache.get_non_stale_global_range (r, name)) - return true; - - // Otherwise calculate a new value. - int_range_max tmp; - calc_stmt (tmp, s, name); - - // Combine the new value with the old value. This is required because - // the way value propagation works, when the IL changes on the fly we - // can sometimes get different results. See PR 97741. - r.intersect (tmp); - m_cache.set_global_range (name, r); + else if (m_cache.get_non_stale_global_range (r, name)) + { + if (idx) + tracer.trailer (idx, " cached", true, name, r); + return true; + } + else + { + // Otherwise calculate a new value. + int_range_max tmp; + fold_range_internal (tmp, s, name); - // Pointers which resolve to non-zero at the defintion point do not need - // tracking in the cache as they will never change. See PR 98866. - if (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ()) - m_cache.set_range_invariant (name); + // Combine the new value with the old value. This is required because + // the way value propagation works, when the IL changes on the fly we + // can sometimes get different results. See PR 97741. + r.intersect (tmp); + m_cache.set_global_range (name, r); + res = true; + } - return true; + if (idx) + tracer.trailer (idx, "range_of_stmt", res, name, r); + return res; } // This routine will export whatever global ranges are known to GCC -// SSA_RANGE_NAME_INFO fields. +// SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields. void gimple_ranger::export_global_ranges () { - unsigned x; - int_range_max r; - if (dump_file) - { - fprintf (dump_file, "Exported global range table\n"); - fprintf (dump_file, "===========================\n"); - } - - for ( x = 1; x < num_ssa_names; x++) + /* Cleared after the table header has been printed. */ + bool print_header = true; + for (unsigned x = 1; x < num_ssa_names; x++) { + int_range_max r; tree name = ssa_name (x); if (name && !SSA_NAME_IN_FREE_LIST (name) && gimple_range_ssa_p (name) && m_cache.get_global_range (r, name) && !r.varying_p()) { - // Make sure the new range is a subset of the old range. - int_range_max old_range; - old_range = gimple_range_global (name); - old_range.intersect (r); - /* Disable this while we fix tree-ssa/pr61743-2.c. */ - //gcc_checking_assert (old_range == r); + bool updated = update_global_range (r, name); + if (!updated || !dump_file || !(dump_flags & TDF_DETAILS)) + continue; - // WTF? Can't write non-null pointer ranges?? stupid set_range_info! - if (!POINTER_TYPE_P (TREE_TYPE (name)) && !r.undefined_p ()) + if (print_header) { - value_range vr = r; - set_range_info (name, vr); - if (dump_file) - { - print_generic_expr (dump_file, name , TDF_SLIM); - fprintf (dump_file, " --> "); - vr.dump (dump_file); - fprintf (dump_file, "\n"); - fprintf (dump_file, " irange : "); - r.dump (dump_file); - fprintf (dump_file, "\n"); - } + /* Print the header only when there's something else + to print below. */ + fprintf (dump_file, "Exported global range table:\n"); + fprintf (dump_file, "============================\n"); + print_header = false; + } + + value_range vr = r; + print_generic_expr (dump_file, name , TDF_SLIM); + fprintf (dump_file, " : "); + vr.dump (dump_file); + fprintf (dump_file, "\n"); + int_range_max same = vr; + if (same != r) + { + fprintf (dump_file, " irange : "); + r.dump (dump_file); + fprintf (dump_file, "\n"); } } } @@ -1133,268 +302,110 @@ gimple_ranger::export_global_ranges () // Print the known table values to file F. void -gimple_ranger::dump (FILE *f) +gimple_ranger::dump_bb (FILE *f, basic_block bb) { - basic_block bb; - - FOR_EACH_BB_FN (bb, cfun) - { - unsigned x; - edge_iterator ei; - edge e; - int_range_max range; - fprintf (f, "\n=========== BB %d ============\n", bb->index); - m_cache.dump (f, bb); + unsigned x; + edge_iterator ei; + edge e; + int_range_max range, tmp_range; + fprintf (f, "\n=========== BB %d ============\n", bb->index); + m_cache.dump_bb (f, bb); - dump_bb (f, bb, 4, TDF_NONE); + ::dump_bb (f, bb, 4, TDF_NONE); - // Now find any globals defined in this block. - for (x = 1; x < num_ssa_names; x++) + // Now find any globals defined in this block. + for (x = 1; x < num_ssa_names; x++) + { + tree name = ssa_name (x); + if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) && + gimple_bb (SSA_NAME_DEF_STMT (name)) == bb && + m_cache.get_global_range (range, name)) { - tree name = ssa_name (x); - if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) && - gimple_bb (SSA_NAME_DEF_STMT (name)) == bb && - m_cache.get_global_range (range, name)) + if (!range.varying_p ()) { - if (!range.varying_p ()) - { - print_generic_expr (f, name, TDF_SLIM); - fprintf (f, " : "); - range.dump (f); - fprintf (f, "\n"); - } - + print_generic_expr (f, name, TDF_SLIM); + fprintf (f, " : "); + range.dump (f); + fprintf (f, "\n"); } + } + } - // And now outgoing edges, if they define anything. - FOR_EACH_EDGE (e, ei, bb->succs) + // And now outgoing edges, if they define anything. + FOR_EACH_EDGE (e, ei, bb->succs) + { + for (x = 1; x < num_ssa_names; x++) { - for (x = 1; x < num_ssa_names; x++) + tree name = gimple_range_ssa_p (ssa_name (x)); + if (name && gori ().has_edge_range_p (name, e) + && m_cache.range_on_edge (range, e, name)) { - tree name = gimple_range_ssa_p (ssa_name (x)); - if (name && m_cache.outgoing_edge_range_p (range, e, name)) + gimple *s = SSA_NAME_DEF_STMT (name); + // Only print the range if this is the def block, or + // the on entry cache for either end of the edge is + // set. + if ((s && bb == gimple_bb (s)) || + m_cache.block_range (tmp_range, bb, name, false) || + m_cache.block_range (tmp_range, e->dest, name, false)) { - gimple *s = SSA_NAME_DEF_STMT (name); - // Only print the range if this is the def block, or - // the on entry cache for either end of the edge is - // set. - if ((s && bb == gimple_bb (s)) || - m_cache.block_range (range, bb, name, false) || - m_cache.block_range (range, e->dest, name, false)) + if (!range.varying_p ()) { - range_on_edge (range, e, name); - if (!range.varying_p ()) - { - fprintf (f, "%d->%d ", e->src->index, - e->dest->index); - char c = ' '; - if (e->flags & EDGE_TRUE_VALUE) - fprintf (f, " (T)%c", c); - else if (e->flags & EDGE_FALSE_VALUE) - fprintf (f, " (F)%c", c); - else - fprintf (f, " "); - print_generic_expr (f, name, TDF_SLIM); - fprintf(f, " : \t"); - range.dump(f); - fprintf (f, "\n"); - } + fprintf (f, "%d->%d ", e->src->index, + e->dest->index); + char c = ' '; + if (e->flags & EDGE_TRUE_VALUE) + fprintf (f, " (T)%c", c); + else if (e->flags & EDGE_FALSE_VALUE) + fprintf (f, " (F)%c", c); + else + fprintf (f, " "); + print_generic_expr (f, name, TDF_SLIM); + fprintf(f, " : \t"); + range.dump(f); + fprintf (f, "\n"); } } } } } - - m_cache.dump (dump_file, (dump_flags & TDF_DETAILS) != 0); } -// If SCEV has any information about phi node NAME, return it as a range in R. +// Print the known table values to file F. void -gimple_ranger::range_of_ssa_name_with_loop_info (irange &r, tree name, - class loop *l, gphi *phi) -{ - gcc_checking_assert (TREE_CODE (name) == SSA_NAME); - tree min, max, type = TREE_TYPE (name); - if (bounds_of_var_in_loop (&min, &max, this, l, phi, name)) - { - // ?? We could do better here. Since MIN/MAX can only be an - // SSA, SSA +- INTEGER_CST, or INTEGER_CST, we could easily call - // the ranger and solve anything not an integer. - if (TREE_CODE (min) != INTEGER_CST) - min = vrp_val_min (type); - if (TREE_CODE (max) != INTEGER_CST) - max = vrp_val_max (type); - r.set (min, max); - } - else - r.set_varying (type); -} - -// -------------------------------------------------------------------------- -// trace_ranger implementation. - - -trace_ranger::trace_ranger () -{ - indent = 0; - trace_count = 0; -} - -// If dumping, return true and print the prefix for the next output line. - -bool -trace_ranger::dumping (unsigned counter, bool trailing) -{ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - // Print counter index as well as INDENT spaces. - if (!trailing) - fprintf (dump_file, " %-7u ", counter); - else - fprintf (dump_file, " "); - unsigned x; - for (x = 0; x< indent; x++) - fputc (' ', dump_file); - return true; - } - return false; -} - -// After calling a routine, if dumping, print the CALLER, NAME, and RESULT, -// returning RESULT. - -bool -trace_ranger::trailer (unsigned counter, const char *caller, bool result, - tree name, const irange &r) +gimple_ranger::dump (FILE *f) { - if (dumping (counter, true)) - { - indent -= bump; - fputs(result ? "TRUE : " : "FALSE : ", dump_file); - fprintf (dump_file, "(%u) ", counter); - fputs (caller, dump_file); - fputs (" (",dump_file); - if (name) - print_generic_expr (dump_file, name, TDF_SLIM); - fputs (") ",dump_file); - if (result) - { - r.dump (dump_file); - fputc('\n', dump_file); - } - else - fputc('\n', dump_file); - // Marks the end of a request. - if (indent == 0) - fputc('\n', dump_file); - } - return result; -} - -// Tracing version of range_on_edge. Call it with printing wrappers. + basic_block bb; -bool -trace_ranger::range_on_edge (irange &r, edge e, tree name) -{ - unsigned idx = ++trace_count; - if (dumping (idx)) - { - fprintf (dump_file, "range_on_edge ("); - print_generic_expr (dump_file, name, TDF_SLIM); - fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index); - indent += bump; - } + FOR_EACH_BB_FN (bb, cfun) + dump_bb (f, bb); - bool res = gimple_ranger::range_on_edge (r, e, name); - trailer (idx, "range_on_edge", true, name, r); - return res; + m_cache.dump (f); } -// Tracing version of range_on_entry. Call it with printing wrappers. +/* Create a new ranger instance and associate it with function FUN. + Each call must be paired with a call to disable_ranger to release + resources. */ -void -trace_ranger::range_on_entry (irange &r, basic_block bb, tree name) +gimple_ranger * +enable_ranger (struct function *fun) { - unsigned idx = ++trace_count; - if (dumping (idx)) - { - fprintf (dump_file, "range_on_entry ("); - print_generic_expr (dump_file, name, TDF_SLIM); - fprintf (dump_file, ") to BB %d\n", bb->index); - indent += bump; - } + gimple_ranger *r; - gimple_ranger::range_on_entry (r, bb, name); + r = new gimple_ranger; + fun->x_range_query = r; - trailer (idx, "range_on_entry", true, name, r); + return r; } -// Tracing version of range_on_exit. Call it with printing wrappers. +/* Destroy and release the ranger instance associated with function FUN + and replace it the global ranger. */ void -trace_ranger::range_on_exit (irange &r, basic_block bb, tree name) -{ - unsigned idx = ++trace_count; - if (dumping (idx)) - { - fprintf (dump_file, "range_on_exit ("); - print_generic_expr (dump_file, name, TDF_SLIM); - fprintf (dump_file, ") from BB %d\n", bb->index); - indent += bump; - } - - gimple_ranger::range_on_exit (r, bb, name); - - trailer (idx, "range_on_exit", true, name, r); -} - -// Tracing version of range_of_stmt. Call it with printing wrappers. - -bool -trace_ranger::range_of_stmt (irange &r, gimple *s, tree name) +disable_ranger (struct function *fun) { - bool res; - unsigned idx = ++trace_count; - if (dumping (idx)) - { - fprintf (dump_file, "range_of_stmt ("); - if (name) - print_generic_expr (dump_file, name, TDF_SLIM); - fputs (") at stmt ", dump_file); - print_gimple_stmt (dump_file, s, 0, TDF_SLIM); - indent += bump; - } - - res = gimple_ranger::range_of_stmt (r, s, name); - - return trailer (idx, "range_of_stmt", res, name, r); -} - -// Tracing version of range_of_expr. Call it with printing wrappers. - -bool -trace_ranger::range_of_expr (irange &r, tree name, gimple *s) -{ - bool res; - unsigned idx = ++trace_count; - if (dumping (idx)) - { - fprintf (dump_file, "range_of_expr("); - print_generic_expr (dump_file, name, TDF_SLIM); - fputs (")", dump_file); - if (s) - { - fputs (" at stmt ", dump_file); - print_gimple_stmt (dump_file, s, 0, TDF_SLIM); - } - else - fputs ("\n", dump_file); - indent += bump; - } - - res = gimple_ranger::range_of_expr (r, name, s); + delete fun->x_range_query; - return trailer (idx, "range_of_expr", res, name, r); + fun->x_range_query = &global_ranges; } |