diff options
Diffstat (limited to 'gcc/gimple-range.cc')
| -rw-r--r-- | gcc/gimple-range.cc | 1309 |
1 files changed, 1309 insertions, 0 deletions
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc new file mode 100644 index 0000000..e6cbb3a --- /dev/null +++ b/gcc/gimple-range.cc @@ -0,0 +1,1309 @@ +/* Code for GIMPLE range related routines. + Copyright (C) 2019-2020 Free Software Foundation, Inc. + Contributed by Andrew MacLeod <amacleod@redhat.com> + and Aldy Hernandez <aldyh@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 "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<1> 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<1> 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; + } +} + +// ------------------------------------------------------------------------ + +// This function will calculate the "constant" range on edge E from +// switch SW returning it in R, and return the switch statement +// itself. This is currently not very efficent as the way we +// represent switches in GIMPLE does not map well to this calculation. + +static gimple * +calc_range_for_switch_on_edge (irange &r, gswitch *sw, edge e) +{ + unsigned x, lim; + lim = gimple_switch_num_labels (sw); + tree type = TREE_TYPE (gimple_switch_index (sw)); + + // ADA and FORTRAN currently have cases where the index is 64 bits + // and the case arguments are 32 bit, causing a trap when we create + // a case_range. Until this is resolved + // (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798) punt on + // these switches. Furthermore, cfamily fails during a bootstrap + // due to a signed index and unsigned cases. So punting unless + // types_compatible_p () for now. + tree case_type = TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1))); + if (lim > 1 && !types_compatible_p (type, case_type)) + return NULL; + + edge default_edge = gimple_switch_default_edge (cfun, sw); + if (e != default_edge) + { + r.set_undefined (); + // Union all the ranges for each switch edge, ignoring the + // default edge. + for (x = 1; x < lim; x++) + { + if (gimple_switch_edge (cfun, sw, x) != e) + continue; + tree low = CASE_LOW (gimple_switch_label (sw, x)); + tree high = CASE_HIGH (gimple_switch_label (sw, x)); + if (!high) + high = low; + int_range<1> case_range (low, high); + r.union_ (case_range); + } + } + else + { + r.set_varying (type); + // Loop through all the switches edges, ignoring the default + // edge, while intersecting the ranges not covered by the case. + for (x = 1; x < lim; x++) + { + // Some other edge could still point to the default edge + // destination. Ignore it. + if (gimple_switch_edge (cfun, sw, x) == default_edge) + continue; + tree low = CASE_LOW (gimple_switch_label (sw, x)); + tree high = CASE_HIGH (gimple_switch_label (sw, x)); + if (!high) + high = low; + int_range<1> case_range (low, high, VR_ANTI_RANGE); + r.intersect (case_range); + } + } + return sw; +} + + +// If there is a range control statment at the end of block BB, return it. + +gimple_stmt_iterator +gsi_outgoing_range_stmt (basic_block bb) +{ + gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); + if (!gsi_end_p (gsi)) + { + gimple *s = gsi_stmt (gsi); + if (is_a<gcond *> (s) || is_a<gswitch *> (s)) + return gsi; + } + return gsi_none (); +} + + +// If there is a range control statment at the end of block BB, return it. + +gimple * +gimple_outgoing_range_stmt_p (basic_block bb) +{ + // This will return NULL if there is not a branch statement. + return gsi_stmt (gsi_outgoing_range_stmt (bb)); +} + + +// Calculate the range forced on on edge E by control flow, return it +// in R. Return the statment which defines the range, otherwise +// return NULL + +gimple * +gimple_outgoing_edge_range_p (irange &r, edge e) +{ + // Determine if there is an outgoing edge. + gimple *s = gimple_outgoing_range_stmt_p (e->src); + if (!s) + return NULL; + + if (is_a<gcond *> (s)) + { + if (e->flags & EDGE_TRUE_VALUE) + r = int_range<1> (boolean_true_node, boolean_true_node); + else if (e->flags & EDGE_FALSE_VALUE) + r = int_range<1> (boolean_false_node, boolean_false_node); + else + gcc_unreachable (); + return s; + } + + gcc_checking_assert (is_a<gswitch *> (s)); + gswitch *sw = as_a<gswitch *> (s); + tree type = TREE_TYPE (gimple_switch_index (sw)); + + if (!irange::supports_type_p (type)) + return NULL; + + return calc_range_for_switch_on_edge (r, sw, e); +} + + +// Return a range in R for the tree EXPR. Return true if a range is +// representable. + +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)) + return false; + + switch (TREE_CODE (expr)) + { + case INTEGER_CST: + 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<1> 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, so return an empty range. + + 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<1> 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, so return an empty range. + 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, so return an empty range. + 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 a 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)); + else + { + // 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; + } + // We don't understand the stmt, so return the global range. + r = gimple_range_global (name); + return true; + } + if (res) + { + if (r.undefined_p ()) + return true; + if (name && TREE_TYPE (name) != r.type ()) + range_cast (r, TREE_TYPE (name)); + return true; + } + return false; +} + +// 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) +{ + widest_irange range1, range2; + 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 (range_of_non_trivial_assignment (r, s)) + return true; + + 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; +} + + +// Calculate the range of a non-trivial assignment. That is, is one +// inolving arithmetic on an SSA name (for example, an ADDR_EXPR). +// Return the range in R. +// +// If a range cannot be calculated, return false. + +bool +gimple_ranger::range_of_non_trivial_assignment (irange &r, gimple *stmt) +{ + if (gimple_code (stmt) != GIMPLE_ASSIGN) + return false; + + tree base = gimple_range_base_of_assignment (stmt); + if (base && TREE_CODE (base) == MEM_REF + && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME) + { + widest_irange range1; + tree ssa = TREE_OPERAND (base, 0); + if (range_of_expr (range1, ssa, stmt)) + { + tree type = TREE_TYPE (ssa); + range_operator *op = range_op_handler (POINTER_PLUS_EXPR, type); + int_range<1> offset (TREE_OPERAND (base, 1), TREE_OPERAND (base, 1)); + op->fold_range (r, type, range1, offset); + return true; + } + } + return false; +} + + +// 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); + widest_irange phi_range; + unsigned x; + + if (!irange::supports_type_p (type)) + return false; + + // And start with an empty range, unioning in each argument's range. + r.set_undefined (); + for (x = 0; x < gimple_phi_num_args (phi); x++) + { + widest_irange arg_range; + tree arg = gimple_phi_arg_def (phi, x); + edge e = gimple_phi_arg_edge (phi, x); + + range_on_edge (arg_range, e, arg); + r.union_ (arg_range); + // Once the value reaches varying, stop looking. + if (r.varying_p ()) + break; + } + + 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 a lHS, intersect that with what is known. + if (lhs) + { + value_range def; + def = gimple_range_global (lhs); + r.intersect (def); + } + return true; +} + + +void +gimple_ranger::range_of_builtin_ubsan_call (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); + widest_irange ir0, ir1; + tree arg0 = gimple_call_arg (call, 0); + tree arg1 = gimple_call_arg (call, 1); + gcc_assert (range_of_expr (ir0, arg0, call)); + gcc_assert (range_of_expr (ir1, arg1, call)); + + bool saved_flag_wrapv = flag_wrapv; + /* Pretend the arithmetics 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); +} + + +bool +gimple_ranger::range_of_builtin_call (irange &r, gcall *call) +{ + 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, prec; + scalar_int_mode mode; + + switch (func) + { + 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 (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; + gcc_assert (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 ()) + { + 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. + // + // On many targets where the CLZ RTL or optab value is defined + // for 0, the value is prec, so include that in the range by + // default. + arg = gimple_call_arg (call, 0); + prec = TYPE_PRECISION (TREE_TYPE (arg)); + mini = 0; + maxi = prec; + mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg)); + if (optab_handler (clz_optab, mode) != CODE_FOR_nothing + && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov) + // Only handle the single common value. + && zerov != prec) + // Magic value to give up, unless we can prove arg is non-zero. + mini = -2; + + gcc_assert (range_of_expr (r, arg, call)); + // From clz of minimum we can compute result maximum. + if (r.constant_p ()) + { + maxi = prec - 1 - wi::floor_log2 (r.lower_bound ()); + if (maxi != prec) + mini = 0; + } + 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 ()) + { + mini = prec - 1 - wi::floor_log2 (r.upper_bound ()); + if (mini == prec) + break; + } + 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. + // + // If there is a ctz optab for this mode and + // CTZ_DEFINED_VALUE_AT_ZERO, include that in the range, + // otherwise just assume 0 won't be seen. + 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 (optab_handler (ctz_optab, mode) != CODE_FOR_nothing + && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov)) + { + // 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; + } + gcc_assert (range_of_expr (r, arg, call)); + if (!r.undefined_p ()) + { + 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) + break; + maxi = wi::floor_log2 (max); + } + 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 (r, call, PLUS_EXPR); + return true; + case CFN_UBSAN_CHECK_SUB: + range_of_builtin_ubsan_call (r, call, MINUS_EXPR); + return true; + case CFN_UBSAN_CHECK_MUL: + range_of_builtin_ubsan_call (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; +} + + + + +// 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) +{ + widest_irange 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; + + gcc_assert (range_of_expr (cond_range, cond, s)); + gcc_assert (range_of_expr (range1, op1, s)); + gcc_assert (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); + } + 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.m_globals.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) + gcc_assert (range_of_stmt (r, def_stmt, expr)); + 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)); + + return true; +} + + +// Return the range of NAME on entry to block BB in R. + +void +gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name) +{ + widest_irange entry_range; + gcc_checking_assert (gimple_range_ssa_p (name)); + + // Start with any known range + gcc_assert (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); +} + + +// Calculate the range for NAME at the end of block BB and return it in R. +// Return false if no range can be calculated. + +void +gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name) +{ + // on-exit from the exit block? + gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); + + 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 + gcc_assert (range_of_expr (r, name, s)); + gcc_checking_assert (r.undefined_p () + || types_compatible_p (r.type(), TREE_TYPE (name))); +} + +// Calculate a range for NAME on edge E and return it in R. + +void +gimple_ranger::range_on_edge (irange &r, edge e, tree name) +{ + widest_irange edge_range; + gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name))); + + // PHI arguments can be constants, catch these here. + if (!gimple_range_ssa_p (name)) + { + gcc_assert (range_of_expr (r, name)); + return; + } + + range_on_exit (r, e->src, name); + gcc_checking_assert (r.undefined_p () + || types_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)) + r.intersect (edge_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. Check +// the global cache for NAME first to see if the evaluation can be +// avoided. If a range cannot be calculated, return false. + +bool +gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name) +{ + // If no name, simply call the base routine. + if (!name) + name = gimple_get_lhs (s); + + if (!name) + return calc_stmt (r, s, NULL_TREE); + + gcc_checking_assert (TREE_CODE (name) == SSA_NAME && + irange::supports_type_p (TREE_TYPE (name))); + + // If this STMT has already been processed, return that value. + if (m_cache.m_globals.get_global_range (r, name)) + return true; + + // Avoid infinite recursion by initializing global cache + widest_irange tmp = gimple_range_global (name); + m_cache.m_globals.set_global_range (name, tmp); + + gcc_assert (calc_stmt (r, s, name)); + + if (is_a<gphi *> (s)) + r.intersect (tmp); + m_cache.m_globals.set_global_range (name, r); + return true; +} + + +// This routine will export whatever global ranges are known to GCC +// SSA_RANGE_NAME_INFO fields. + +void +gimple_ranger::export_global_ranges () +{ + unsigned x; + widest_irange r; + if (dump_file) + { + fprintf (dump_file, "Exported global range table\n"); + fprintf (dump_file, "===========================\n"); + } + + for ( x = 1; x < num_ssa_names; x++) + { + tree name = ssa_name (x); + if (name && !SSA_NAME_IN_FREE_LIST (name) + && gimple_range_ssa_p (name) + && m_cache.m_globals.get_global_range (r, name) + && !r.varying_p()) + { + // Make sure the new range is a subset of the old range. + widest_irange 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); + + // WTF? Can't write non-null pointer ranges?? stupid set_range_info! + if (!POINTER_TYPE_P (TREE_TYPE (name)) && !r.undefined_p ()) + { + 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 known table values to file F. + +void +gimple_ranger::dump (FILE *f) +{ + basic_block bb; + + FOR_EACH_BB_FN (bb, cfun) + { + unsigned x; + edge_iterator ei; + edge e; + widest_irange range; + fprintf (f, "\n=========== BB %d ============\n", bb->index); + m_cache.m_on_entry.dump (f, bb); + + dump_bb (f, bb, 4, TDF_NONE); + + // 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.m_globals.get_global_range (range, name)) + { + if (!range.varying_p ()) + { + 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) + { + for (x = 1; x < num_ssa_names; x++) + { + 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 (range, bb, name, false) || + m_cache.block_range (range, e->dest, name, false)) + { + 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"); + } + } + } + } + } + } + + m_cache.m_globals.dump (dump_file); + fprintf (f, "\n"); + + if (dump_flags & TDF_DETAILS) + { + fprintf (f, "\nDUMPING GORI MAP\n"); + m_cache.dump (f); + fprintf (f, "\n"); + } +} + + +// loop_ranger implementation. + +loop_ranger::loop_ranger () +{ + m_vr_values = new vr_values; +} + +loop_ranger::~loop_ranger () +{ + delete m_vr_values; +} + +void +loop_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); + value_range_equiv vr; + vr.set_varying (TREE_TYPE (name)); + m_vr_values->adjust_range_with_scev (&vr, l, phi, name); + vr.normalize_symbolics (); + r = vr; +} + +// If NAME is either a PHI result or a PHI argument, see if we can +// determine range information by querying loop info. If so, return +// TRUE and set the range in R. + +bool +loop_ranger::range_with_loop_info (irange &r, tree name) +{ + if (!scev_initialized_p ()) + return false; + + gimple *def = SSA_NAME_DEF_STMT (name); + class loop *l = loop_containing_stmt (def); + if (!l) + return false; + + basic_block header = l->header; + for (gphi_iterator iter = gsi_start_phis (header); + !gsi_end_p (iter); gsi_next (&iter)) + { + gphi *phi = iter.phi (); + if (PHI_RESULT (phi) == name) + { + range_of_ssa_name_with_loop_info (r, name, l, phi); + return true; + } + for (size_t i = 0; i < gimple_phi_num_args (phi); ++i) + if (PHI_ARG_DEF (phi, i) == name) + { + range_of_ssa_name_with_loop_info (r, name, l, phi); + return true; + } + } + return false; +} + +bool +loop_ranger::range_of_stmt (irange &r, gimple *stmt, tree name) +{ + // If there is no global range for a PHI, start the party with + // whatever information SCEV may have. + if (gphi *phi = dyn_cast<gphi *> (stmt)) + { + tree phi_result = PHI_RESULT (phi); + if (!POINTER_TYPE_P (TREE_TYPE (phi_result)) + && !m_cache.m_globals.get_global_range (r, phi_result) + && range_with_loop_info (r, phi_result)) + { + value_range loop_range; + get_range_info (phi_result, loop_range); + r.intersect (loop_range); + if (!r.varying_p ()) + set_range_info (phi_result, r); + } + } + return super::range_of_stmt (r, stmt, name); +} + +void +loop_ranger::range_on_edge (irange &r, edge e, tree name) +{ + super::range_on_edge (r, e, name); + + if (TREE_CODE (name) == SSA_NAME) + { + value_range loop_range; + if (range_with_loop_info (loop_range, name)) + r.intersect (loop_range); + } +} |