diff options
author | Aldy Hernandez <aldyh@redhat.com> | 2020-03-31 18:29:13 +0200 |
---|---|---|
committer | Aldy Hernandez <aldyh@redhat.com> | 2020-04-02 11:06:21 +0200 |
commit | 9e927c2144e0037708f522df90a7bd58278522cf (patch) | |
tree | b46c4fea9ba5f590a2b8f2dc4651873dd7002828 /gcc | |
parent | 762129fe3681760cf93833f81bf3f23a1e8e2591 (diff) | |
download | gcc-9e927c2144e0037708f522df90a7bd58278522cf.zip gcc-9e927c2144e0037708f522df90a7bd58278522cf.tar.gz gcc-9e927c2144e0037708f522df90a7bd58278522cf.tar.bz2 |
Handle builtins in gimple_ranger::range_of_call.
Diffstat (limited to 'gcc')
-rw-r--r-- | gcc/gimple-ssa-evrp-analyze.c | 192 | ||||
-rw-r--r-- | gcc/ssa-range.cc | 253 | ||||
-rw-r--r-- | gcc/ssa-range.h | 2 | ||||
-rw-r--r-- | gcc/tree-vrp.c | 2 | ||||
-rw-r--r-- | gcc/vr-values.h | 10 |
5 files changed, 391 insertions, 68 deletions
diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c index 281170a..32bead1 100644 --- a/gcc/gimple-ssa-evrp-analyze.c +++ b/gcc/gimple-ssa-evrp-analyze.c @@ -83,7 +83,7 @@ evrp_range_analyzer::evrp_range_analyzer (bool update_global_ranges) FOR_EACH_EDGE (e, ei, bb->preds) e->flags |= EDGE_EXECUTABLE; } - vr_values = new class vr_values; + vr_values = new class vr_values_tester; ranger = new global_ranger; gori = new trace_vr_gori_interface (vr_values); } @@ -196,6 +196,8 @@ vr_gori_interface::range_of_ssa_name (irange &r, tree op, gimple *stmt ATTRIBUTE_UNUSED) { r = *store->get_value_range (op); + if (r.undefined_p ()) + r.set_varying (TREE_TYPE (op)); r.normalize_symbolics (); } @@ -329,44 +331,45 @@ trace_vr_gori_interface::refine_range_with_equivalences (irange &r, return trailer (idx, "refine_range_with_equivalences", res, name, r); } -// Class to assert that gori/ranger provide ranges that are at least -// as good as evrp. +// Class to assert that the new range is at least as good as the old +// one. -class vr_gori_comparison +class vr_comparison { public: - vr_gori_comparison (const value_range *r_evrp, const irange *r_gori); - void compare (tree name, edge, vr_values *vr); + vr_comparison (const irange *, const irange *, vr_values *); + void compare (tree name, edge); + void compare (gimple *); private: + void compare (); void dump_differences_and_trap () const; void dump_differences (FILE *) const; void dump_improvements (FILE *) const; - bool gori_range_is_same () const; - bool gori_range_is_better () const; + bool new_range_is_same () const; + bool new_range_is_better () const; tree m_name; edge m_edge; - const irange *m_range_evrp; - const irange *m_range_gori; + gimple *m_stmt; + const irange *m_old_range; + const irange *m_new_range; vr_values *m_vr_values; }; -vr_gori_comparison::vr_gori_comparison (const value_range *r_evrp, - const irange *r_gori) +vr_comparison::vr_comparison (const irange *old_range, + const irange *new_range, + vr_values *vr) { - m_range_evrp = r_evrp; - m_range_gori = r_gori; + m_old_range = old_range; + m_new_range = new_range; + m_vr_values = vr; } void -vr_gori_comparison::compare (tree name, edge e, vr_values *vr) +vr_comparison::compare () { - m_name = name; - m_edge = e; - m_vr_values = vr; - - if (gori_range_is_same ()) + if (new_range_is_same ()) return; - if (gori_range_is_better ()) + if (new_range_is_better ()) { if (dump_file) dump_improvements (dump_file); @@ -375,48 +378,72 @@ vr_gori_comparison::compare (tree name, edge e, vr_values *vr) dump_differences_and_trap (); } +void +vr_comparison::compare (tree name, edge e) +{ + m_name = name; + m_edge = e; + m_stmt = NULL; + compare (); +} + +void +vr_comparison::compare (gimple *stmt) +{ + m_name = get_output_for_vrp (stmt); + m_edge = NULL; + m_stmt = stmt; + compare (); +} + bool -vr_gori_comparison::gori_range_is_same () const +vr_comparison::new_range_is_same () const { // We may be able to normalize a symbolic to a [MIN,MAX] plus // or minus the end-points. Don't count that as a win just yet. - if (m_range_evrp && m_range_evrp->symbolic_p ()) + if (m_old_range && m_old_range->symbolic_p ()) return true; + widest_irange old; + if (m_old_range) + old = *m_old_range; // Treat UNDEFINED and VARYING as interchangeable. - widest_irange evrp; - if (m_range_evrp) - evrp = *m_range_evrp; - if (evrp.undefined_p () && m_range_gori->varying_p ()) + if (old.undefined_p () && m_new_range->varying_p ()) return true; - if (evrp.varying_p () && m_range_gori->undefined_p ()) + if (old.varying_p () && m_new_range->undefined_p ()) return true; - return evrp == *m_range_gori; + return old == *m_new_range; } bool -vr_gori_comparison::gori_range_is_better () const +vr_comparison::new_range_is_better () const { - if (gori_range_is_same ()) + if (new_range_is_same ()) return false; - if (!m_range_evrp) + if (!m_old_range) + return true; + // ?? Sometimes we get an undefined because the ranger determined a + // path was unexecutable. Verify this is actually the case by + // turning this off and analyzing all failures. + if (m_new_range->undefined_p ()) return true; - if (!range_has_numeric_bounds_p (m_range_evrp)) + if (!range_has_numeric_bounds_p (m_old_range)) { - gcc_checking_assert (range_has_numeric_bounds_p (m_range_gori)); + gcc_checking_assert (range_has_numeric_bounds_p (m_new_range)); return true; } - widest_irange inter (*m_range_gori); - inter.intersect (*m_range_evrp); - return inter == *m_range_gori; + widest_irange inter (*m_new_range); + inter.intersect (*m_old_range); + return inter == *m_new_range; } void -vr_gori_comparison::dump_differences_and_trap () const +vr_comparison::dump_differences_and_trap () const { - bool dumping = getenv("GORIME") && !strcmp (getenv ("GORIME"), "dump"); + bool dumping = getenv("GORI_DUMP_FILE") != NULL; if (dumping) { - FILE *out = fopen ("/tmp/gori-differences", "a"); + const char *filename = getenv("GORI_DUMP_FILE"); + FILE *out = fopen (filename, "a"); fprintf (out, "=========FILE: %s ========\n", main_input_filename ? main_input_filename : "UNKNOWN"); dump_differences (out); @@ -428,17 +455,29 @@ vr_gori_comparison::dump_differences_and_trap () const } void -vr_gori_comparison::dump_differences (FILE *out) const -{ - fprintf (out, "Different ranges on edge (%d -> %d) for SSA: ", - m_edge->src->index, m_edge->dest->index); - print_generic_stmt (out, m_name, TDF_VOPS|TDF_MEMSYMS); - fprintf (out, "\tevrp: "); - m_range_evrp->dump (out); - fprintf (out, "\n\tgori: "); - m_range_gori->dump (out); - fprintf (out, "\n\n"); - dump_bb (out, m_edge->src, 0, TDF_NONE); +vr_comparison::dump_differences (FILE *out) const +{ + dump_flags_t flags = TDF_NONE; + if (m_stmt) + { + fprintf (out, "Different ranges for stmt: "); + print_gimple_stmt (out, m_stmt, 0, flags); + } + else + { + fprintf (out, "Different ranges on edge (%d -> %d) for SSA: ", + m_edge->src->index, m_edge->dest->index); + print_generic_stmt (out, m_name, flags); + } + fprintf (out, "\told range: "); + m_old_range->dump (out); + fprintf (out, "\n\tnew range: "); + m_new_range->dump (out); + if (m_edge) + { + fprintf (out, "\n\n"); + dump_bb (out, m_edge->src, 0, TDF_NONE); + } fprintf (out, "\n"); fprintf (out, "==============================================\n"); dump_function_to_file (current_function_decl, out, TDF_NONE); @@ -450,25 +489,56 @@ vr_gori_comparison::dump_differences (FILE *out) const } void -vr_gori_comparison::dump_improvements (FILE *out) const +vr_comparison::dump_improvements (FILE *out) const { - if (m_range_evrp && !range_has_numeric_bounds_p (m_range_evrp)) + if (m_old_range && !range_has_numeric_bounds_p (m_old_range)) return; - if (gori_range_is_better ()) + if (new_range_is_better ()) { - fprintf (out, "GORI improved: "); - print_generic_expr (out, m_name); + fprintf (out, "New range improved: "); + if (m_name) + print_generic_expr (out, m_name); fprintf (out, " from: "); - if (m_range_evrp) - m_range_evrp->dump (out); + if (m_old_range) + m_old_range->dump (out); else fprintf (out, "UNDEFINED"); fprintf (out, " to: "); - m_range_gori->dump (out); + m_new_range->dump (out); fprintf (out, "\n"); } } +// ?? Eventually overload extract_range_from_stmt instead, since it is +// higher level and more comparable to gimple_ranger::range_of_stmt. + +void +vr_values_tester::extract_range_basic (value_range_equiv *vr, gimple *stmt) +{ + vr_values::extract_range_basic (vr, stmt); + + if (gimple_code (stmt) != GIMPLE_CALL) + return; + + class ranger_using_vrvalues : public gimple_ranger + { + public: + ranger_using_vrvalues (range_store *super) : super (super) { } + // Use the vr_values version of range_of_expr while the ranger + // comes up to par. + virtual bool range_of_expr (irange &r, tree expr, gimple *stmt) + { return super->range_of_expr (r, expr, stmt); } + private: + range_store *super; + } ranger (this); + + value_range ranger_vr; + ranger.range_of_stmt (ranger_vr, stmt); + + vr_comparison comp (vr, &ranger_vr, this); + comp.compare (stmt); +} + value_range_equiv * evrp_range_analyzer::try_find_new_range_for_assert (const assert_info &assert, edge e) @@ -514,8 +584,8 @@ evrp_range_analyzer::try_find_new_range_for_assert (const assert_info &assert, { if (CHECKING_P && dbg_cnt (evrp_find_range)) { - vr_gori_comparison comp (vr, &vr_gori); - comp.compare (name, e, vr_values); + vr_comparison comp (vr, &vr_gori, vr_values); + comp.compare (name, e); } if (!vr) { diff --git a/gcc/ssa-range.cc b/gcc/ssa-range.cc index 64cce18..1d3f644 100644 --- a/gcc/ssa-range.cc +++ b/gcc/ssa-range.cc @@ -51,6 +51,8 @@ along with GCC; see the file COPYING3. If not see #include "alloc-pool.h" #include "vr-values.h" #include "dbgcnt.h" +#include "case-cfn-macros.h" +#include "omp-general.h" // 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 @@ -205,6 +207,35 @@ gimple_ranger::range_of_phi (irange &r, gphi *phi) } +void +gimple_ranger::range_of_ubsan_call (irange &r, gcall *call, tree_code code) +{ + 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); +} + + // Calculate a range for call statement S and return it in R. // If a range cannot be calculated, return false. @@ -213,14 +244,226 @@ gimple_ranger::range_of_call (irange &r, gcall *call) { tree type = gimple_call_return_type (call); tree lhs = gimple_call_lhs (call); + tree arg; + int mini, maxi, zerov, prec; + scalar_int_mode mode; if (!irange::supports_type_p (type)) return false; - if (gimple_call_nonnull_result_p (call)) - r = range_nonzero (type); - else - r.set_varying (type); + combined_fn func = gimple_call_combined_fn (call); + switch (func) + { + case CFN_BUILT_IN_CONSTANT_P: + if (cfun->after_inlining) + { + r.set_zero (type); + // r.equiv_clean (); + } + break; + /* __builtin_ffs* and __builtin_popcount* return [0, prec]. */ + CASE_CFN_FFS: + CASE_CFN_POPCOUNT: + arg = gimple_call_arg (call, 0); + prec = TYPE_PRECISION (TREE_TYPE (arg)); + mini = 0; + maxi = prec; + if (TREE_CODE (arg) == SSA_NAME) + { + widest_irange vr0; + gcc_assert (range_of_expr (vr0, arg, call)); + /* If arg is non-zero, then ffs or popcount are non-zero. */ + if (range_includes_zero_p (&vr0) == 0) + mini = 1; + /* If some high bits are known to be zero, we can decrease + the maximum. */ + if (vr0.kind () == VR_RANGE + && TREE_CODE (vr0.max ()) == INTEGER_CST + && !operand_less_p (vr0.min (), + build_zero_cst (TREE_TYPE (vr0.min ())))) + maxi = tree_floor_log2 (vr0.max ()) + 1; + } + r.set (build_int_cst (type, mini), + build_int_cst (type, maxi)); + break; + /* __builtin_parity* returns [0, 1]. */ + CASE_CFN_PARITY: + r.set (build_int_cst (type, 0), + build_int_cst (type, 1)); + break; + /* __builtin_c[lt]z* return [0, prec-1], except for + 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. */ + CASE_CFN_CLZ: + 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) + /* Handle only the single common value. */ + && zerov != prec) + /* Magic value to give up, unless vr0 proves + arg is non-zero. */ + mini = -2; + if (TREE_CODE (arg) == SSA_NAME) + { + widest_irange vr0; + gcc_assert (range_of_expr (vr0, arg, call)); + /* From clz of VR_RANGE minimum we can compute + result maximum. */ + if (vr0.kind () == VR_RANGE + && TREE_CODE (vr0.min ()) == INTEGER_CST) + { + maxi = prec - 1 - tree_floor_log2 (vr0.min ()); + if (maxi != prec) + mini = 0; + } + else if (!range_includes_zero_p (&vr0)) + { + maxi = prec - 1; + mini = 0; + } + if (mini == -2) + break; + /* From clz of VR_RANGE maximum we can compute + result minimum. */ + if (vr0.kind () == VR_RANGE + && TREE_CODE (vr0.max ()) == INTEGER_CST) + { + mini = prec - 1 - tree_floor_log2 (vr0.max ()); + if (mini == prec) + break; + } + } + if (mini == -2) + break; + r.set (build_int_cst (type, mini), + build_int_cst (type, maxi)); + break; + /* __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. */ + CASE_CFN_CTZ: + 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 vr0 proves + arg is non-zero. */ + mini = -2; + } + if (TREE_CODE (arg) == SSA_NAME) + { + widest_irange vr0; + gcc_assert (range_of_expr (vr0, arg, call)); + /* If arg is non-zero, then use [0, prec - 1]. */ + if (vr0.kind () == VR_RANGE + && integer_nonzerop (vr0.min ())) + { + mini = 0; + maxi = prec - 1; + } + /* If some high bits are known to be zero, + we can decrease the result maximum. */ + if (vr0.kind () == VR_RANGE + && TREE_CODE (vr0.max ()) == INTEGER_CST) + { + maxi = tree_floor_log2 (vr0.max ()); + /* For vr0 [0, 0] give up. */ + if (maxi == -1) + break; + } + } + if (mini == -2) + break; + r.set (build_int_cst (type, mini), + build_int_cst (type, maxi)); + break; + /* __builtin_clrsb* returns [0, prec-1]. */ + 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)); + break; + case CFN_UBSAN_CHECK_ADD: + range_of_ubsan_call (r, call, PLUS_EXPR); + break; + case CFN_UBSAN_CHECK_SUB: + range_of_ubsan_call (r, call, MINUS_EXPR); + break; + case CFN_UBSAN_CHECK_MUL: + range_of_ubsan_call (r, call, MULT_EXPR); + break; + 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); + + tree type = TREE_TYPE (gimple_call_lhs (call)); + r.set (build_int_cst (type, is_pos ? 0 : 1), + size + ? build_int_cst (type, size - is_pos) : vrp_val_max (type)); + } + break; + 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); + break; + } + break; + default: + { + bool ignore; + if (gimple_stmt_nonnegative_warnv_p (call, &ignore)) + 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); + break; + } + } // If there is a lHS, intersect that with what is known. if (lhs) @@ -896,7 +1139,7 @@ if (DEBUG_CACHE) fprintf (dump_file, "BACK visiting block %d\n", node->index); loop_ranger::loop_ranger () { - m_vr_values = new vr_values; + m_vr_values = new vr_values_tester; } loop_ranger::~loop_ranger () diff --git a/gcc/ssa-range.h b/gcc/ssa-range.h index 941a84f..87acc95 100644 --- a/gcc/ssa-range.h +++ b/gcc/ssa-range.h @@ -51,6 +51,8 @@ protected: bool range_of_phi (irange &r, gphi *phi); bool range_of_call (irange &r, gcall *call); bool range_of_cond_expr (irange &r, gassign* cond); +private: + void range_of_ubsan_call (irange &r, gcall *call, tree_code code); }; diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index fcc79c7..e1658dd 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -3506,7 +3506,7 @@ class vrp_prop : public ssa_propagation_engine bool check_mem_ref (location_t, tree, bool); void search_for_addr_array (tree, location_t); - class vr_values vr_values; + class vr_values_tester vr_values; /* Temporary delegator to minimize code churn. */ const value_range_equiv *get_value_range (const_tree op) { return vr_values.get_value_range (op); } diff --git a/gcc/vr-values.h b/gcc/vr-values.h index bd121b7..a0fb538 100644 --- a/gcc/vr-values.h +++ b/gcc/vr-values.h @@ -95,8 +95,9 @@ private: range information fast or perform on-demand queries. */ class vr_values : public range_store { + protected: + vr_values (void); // FIXME: temporary for vr_values_tester. public: - vr_values (void); virtual ~vr_values (void); const value_range_equiv *get_value_range (const_tree); @@ -116,6 +117,7 @@ class vr_values : public range_store tree, tree, value_range_equiv *); void extract_range_from_phi_node (gphi *, value_range_equiv *); + virtual // FIXME: temporary tester for vr_values_tester. void extract_range_basic (value_range_equiv *, gimple *); void extract_range_from_stmt (gimple *, edge *, tree *, value_range_equiv *); @@ -170,4 +172,10 @@ extern tree get_output_for_vrp (gimple *); // FIXME: Move this to tree-vrp.c. void simplify_cond_using_ranges_2 (range_store *, gcond *); +class vr_values_tester : public vr_values +{ +public: + void extract_range_basic (value_range_equiv *, gimple *); +}; + #endif /* GCC_VR_VALUES_H */ |