* [RFC][PATCH 0/3] Re-enable zero/sign extension elimination using value ranges
@ 2015-01-17 2:10 Kugan
2015-01-17 2:11 ` [RFC][PATCH 1/3] Free a bit in SSA_NAME to save wrapped information Kugan
` (2 more replies)
0 siblings, 3 replies; 14+ messages in thread
From: Kugan @ 2015-01-17 2:10 UTC (permalink / raw)
To: gcc-patches; +Cc: Richard Biener, Jakub Jelinek, Jeff Law
Hi,
Due to wrapping in the value ranges, there was a regression in
aplha-linux (https://gcc.gnu.org/ml/gcc-patches/2014-08/msg02458.html)
and hence I had to revert the patch that enabled zero/sign extension
elimination using value range. I have now attempted to propagate this
information and enable it again.
PATCH1: Free a bit in SSA_NAME to save wrapped information
PATCH2: Propagate and save value ranges wrapped information
PATCH3: Enable zero/sign extension elimination
Bootstrapped and regression tested for x86_64-linux-gnu with no new
regressions.
Thanks,
Kugan
^ permalink raw reply [flat|nested] 14+ messages in thread* [RFC][PATCH 1/3] Free a bit in SSA_NAME to save wrapped information 2015-01-17 2:10 [RFC][PATCH 0/3] Re-enable zero/sign extension elimination using value ranges Kugan @ 2015-01-17 2:11 ` Kugan 2015-04-22 22:14 ` Kugan 2015-01-17 2:44 ` [RFC][PATCH 2/3] Propagate and save value ranges " Kugan 2015-01-17 2:58 ` [RFC][PATCH 3/3] Enable zero/sign extension elimination Kugan 2 siblings, 1 reply; 14+ messages in thread From: Kugan @ 2015-01-17 2:11 UTC (permalink / raw) To: gcc-patches; +Cc: Richard Biener, Jakub Jelinek, Jeff Law [-- Attachment #1: Type: text/plain, Size: 695 bytes --] Freeing a spare-bit to store wrapped attribute by going back to representing VR_ANTI_RANGE as [max + 1, min - 1] in SSA_NAME. Thanks, Kugan gcc/ChangeLog: 2015-01-16 Kugan Vivekanandarajah <kuganv@linaro.org> * tree-ssanames.c (set_range_info): Change range info representation and represent VR_ANTI_RANGE as [max + 1, min - 1]. (get_range_info): Likewise. (set_nonzero_bits): Likewise. (duplicate_ssa_name_range_info): Likewise. * tree-ssanames.h (set_range_info): Change prototype. (get_range_info): Likewise. (set_nonzero_bits): Likewise. (duplicate_ssa_name_range_info): Likewise. * tree-vrp.c (remove_range_assertions): Use new representation. (vrp_finalize): Likewise. [-- Attachment #2: patch1.txt --] [-- Type: text/plain, Size: 6304 bytes --] diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 9c39f65..744dc43 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -200,11 +200,10 @@ make_ssa_name_fn (struct function *fn, tree var, gimple stmt) /* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME. */ void -set_range_info (tree name, enum value_range_type range_type, +set_range_info (tree name, const wide_int_ref &min, const wide_int_ref &max) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); - gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); range_info_def *ri = SSA_NAME_RANGE_INFO (name); unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); @@ -219,16 +218,12 @@ set_range_info (tree name, enum value_range_type range_type, ri->set_nonzero_bits (wi::shwi (-1, precision)); } - /* Record the range type. */ - if (SSA_NAME_RANGE_TYPE (name) != range_type) - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); - /* Set the values. */ ri->set_min (min); ri->set_max (max); /* If it is a range, try to improve nonzero_bits from the min/max. */ - if (range_type == VR_RANGE) + if (wi::cmp (min, max, TYPE_SIGN (TREE_TYPE (name))) < 0) { wide_int xorv = ri->get_min () ^ ri->get_max (); if (xorv != 0) @@ -248,6 +243,7 @@ get_range_info (const_tree name, wide_int *min, wide_int *max) gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (min && max); range_info_def *ri = SSA_NAME_RANGE_INFO (name); + value_range_type range_type; /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision. */ @@ -255,9 +251,22 @@ get_range_info (const_tree name, wide_int *min, wide_int *max) > 2 * HOST_BITS_PER_WIDE_INT)) return VR_VARYING; - *min = ri->get_min (); - *max = ri->get_max (); - return SSA_NAME_RANGE_TYPE (name); + /* If max < min, it is VR_ANTI_RANGE. */ + if (wi::cmp (ri->get_max (), ri->get_min (), TYPE_SIGN (TREE_TYPE (name))) < 0) + { + /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1]. */ + range_type = VR_ANTI_RANGE; + *min = wi::add (ri->get_max (), 1); + *max = wi::sub (ri->get_min (), 1); + } + else + { + /* Otherwise (when min <= max), it is VR_RANGE. */ + range_type = VR_RANGE; + *min = ri->get_min (); + *max = ri->get_max (); + } + return range_type; } /* Change non-zero bits bitmask of NAME. */ @@ -267,7 +276,7 @@ set_nonzero_bits (tree name, const wide_int_ref &mask) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); if (SSA_NAME_RANGE_INFO (name) == NULL) - set_range_info (name, VR_RANGE, + set_range_info (name, TYPE_MIN_VALUE (TREE_TYPE (name)), TYPE_MAX_VALUE (TREE_TYPE (name))); range_info_def *ri = SSA_NAME_RANGE_INFO (name); @@ -495,7 +504,8 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) /* Creates a duplicate of the range_info_def at RANGE_INFO of type RANGE_TYPE for use by the SSA name NAME. */ void -duplicate_ssa_name_range_info (tree name, enum value_range_type range_type, +duplicate_ssa_name_range_info (tree name, + enum value_range_type range_type ATTRIBUTE_UNUSED, struct range_info_def *range_info) { struct range_info_def *new_range_info; @@ -513,8 +523,6 @@ duplicate_ssa_name_range_info (tree name, enum value_range_type range_type, new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size)); memcpy (new_range_info, range_info, size); - gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); SSA_NAME_RANGE_INFO (name) = new_range_info; } diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index a7eeb8f..0d4b212 100644 --- a/gcc/tree-ssanames.h +++ b/gcc/tree-ssanames.h @@ -68,7 +68,7 @@ struct GTY ((variable_size)) range_info_def { enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; /* Sets the value range to SSA. */ -extern void set_range_info (tree, enum value_range_type, const wide_int_ref &, +extern void set_range_info (tree, const wide_int_ref &, const wide_int_ref &); /* Gets the value range from SSA. */ extern enum value_range_type get_range_info (const_tree, wide_int *, diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 2e0b158..9b7695d 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -6915,7 +6915,7 @@ remove_range_assertions (void) && all_imm_uses_in_stmt_or_feed_cond (var, stmt, single_pred (bb))) { - set_range_info (var, SSA_NAME_RANGE_TYPE (lhs), + set_range_info (var, SSA_NAME_RANGE_INFO (lhs)->get_min (), SSA_NAME_RANGE_INFO (lhs)->get_max ()); maybe_set_nonzero_bits (bb, var); @@ -10238,12 +10238,35 @@ vrp_finalize (void) || (vr_value[i]->type == VR_UNDEFINED)) continue; - if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST) - && (TREE_CODE (vr_value[i]->max) == INTEGER_CST) - && (vr_value[i]->type == VR_RANGE - || vr_value[i]->type == VR_ANTI_RANGE)) - set_range_info (name, vr_value[i]->type, vr_value[i]->min, - vr_value[i]->max); + if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST) + && (TREE_CODE (vr_value[i]->max) == INTEGER_CST) + && (vr_value[i]->type == VR_RANGE + || vr_value[i]->type == VR_ANTI_RANGE)) + { + if (vr_value[i]->type == VR_RANGE) + set_range_info (name, vr_value[i]->min, vr_value[i]->max); + else if (vr_value[i]->type == VR_ANTI_RANGE) + { + /* VR_ANTI_RANGE + ~[min, max] is encoded compactly as + [max + 1, min - 1] without additional attributes. + When min value > max value, we know that it is + VR_ANTI_RANGE; it is VR_RANGE otherwise. */ + + if (TYPE_UNSIGNED (TREE_TYPE (name)) + && integer_zerop (vr_value[i]->min) + && integer_zerop (vr_value[i]->max)) + /* ~[0,0] anti-range is represented as range. */ + set_range_info (name, + build_int_cst (TREE_TYPE (name), 1), + TYPE_MAXVAL (TREE_TYPE (name))); + else + set_range_info (name, + wi::add (vr_value[i]->max, 1), + wi::sub (vr_value[i]->min, 1)); + } + } + } /* Free allocated memory. */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 1/3] Free a bit in SSA_NAME to save wrapped information 2015-01-17 2:11 ` [RFC][PATCH 1/3] Free a bit in SSA_NAME to save wrapped information Kugan @ 2015-04-22 22:14 ` Kugan 0 siblings, 0 replies; 14+ messages in thread From: Kugan @ 2015-04-22 22:14 UTC (permalink / raw) To: gcc-patches; +Cc: Richard Biener, Jakub Jelinek, Jeff Law [-- Attachment #1: Type: text/plain, Size: 926 bytes --] On 17/01/15 13:06, Kugan wrote: > Freeing a spare-bit to store wrapped attribute by going back to > representing VR_ANTI_RANGE as [max + 1, min - 1] in SSA_NAME. > Now that stage-1 is open, rebased it and regression tested on x86-64-none-linux-gnu with no new regressions. Is this OK for trunk? Thanks, Kugan gcc/ChangeLog: 2015-04-22 Kugan Vivekanandarajah <kuganv@linaro.org> * tree-ssanames.c (set_range_info): Change range info representation and represent VR_ANTI_RANGE as [max + 1, min - 1]. (get_range_info): Likewise. (set_nonzero_bits): Likewise. (duplicate_ssa_name_range_info): Likewise. * tree-ssanames.h (set_range_info): Change prototype. (get_range_info): Likewise. (set_nonzero_bits): Likewise. (duplicate_ssa_name_range_info): Likewise. * tree-vrp.c (remove_range_assertions): Use new representation. (vrp_finalize): Likewise. * tree-ssa-pre.c (insert_into_preds_of_block): Likewise. [-- Attachment #2: patch1.txt --] [-- Type: text/plain, Size: 6842 bytes --] diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index d857d84..67e5351 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -3205,7 +3205,6 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, && !wi::neg_p (max, SIGNED)) /* Just handle extension and sign-changes of all-positive ranges. */ set_range_info (temp, - SSA_NAME_RANGE_TYPE (expr->u.nary->op[0]), wide_int_storage::from (min, TYPE_PRECISION (type), TYPE_SIGN (type)), wide_int_storage::from (max, TYPE_PRECISION (type), diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 9c39f65..744dc43 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -200,11 +200,10 @@ make_ssa_name_fn (struct function *fn, tree var, gimple stmt) /* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME. */ void -set_range_info (tree name, enum value_range_type range_type, +set_range_info (tree name, const wide_int_ref &min, const wide_int_ref &max) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); - gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); range_info_def *ri = SSA_NAME_RANGE_INFO (name); unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); @@ -219,16 +218,12 @@ set_range_info (tree name, enum value_range_type range_type, ri->set_nonzero_bits (wi::shwi (-1, precision)); } - /* Record the range type. */ - if (SSA_NAME_RANGE_TYPE (name) != range_type) - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); - /* Set the values. */ ri->set_min (min); ri->set_max (max); /* If it is a range, try to improve nonzero_bits from the min/max. */ - if (range_type == VR_RANGE) + if (wi::cmp (min, max, TYPE_SIGN (TREE_TYPE (name))) < 0) { wide_int xorv = ri->get_min () ^ ri->get_max (); if (xorv != 0) @@ -248,6 +243,7 @@ get_range_info (const_tree name, wide_int *min, wide_int *max) gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (min && max); range_info_def *ri = SSA_NAME_RANGE_INFO (name); + value_range_type range_type; /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision. */ @@ -255,9 +251,22 @@ get_range_info (const_tree name, wide_int *min, wide_int *max) > 2 * HOST_BITS_PER_WIDE_INT)) return VR_VARYING; - *min = ri->get_min (); - *max = ri->get_max (); - return SSA_NAME_RANGE_TYPE (name); + /* If max < min, it is VR_ANTI_RANGE. */ + if (wi::cmp (ri->get_max (), ri->get_min (), TYPE_SIGN (TREE_TYPE (name))) < 0) + { + /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1]. */ + range_type = VR_ANTI_RANGE; + *min = wi::add (ri->get_max (), 1); + *max = wi::sub (ri->get_min (), 1); + } + else + { + /* Otherwise (when min <= max), it is VR_RANGE. */ + range_type = VR_RANGE; + *min = ri->get_min (); + *max = ri->get_max (); + } + return range_type; } /* Change non-zero bits bitmask of NAME. */ @@ -267,7 +276,7 @@ set_nonzero_bits (tree name, const wide_int_ref &mask) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); if (SSA_NAME_RANGE_INFO (name) == NULL) - set_range_info (name, VR_RANGE, + set_range_info (name, TYPE_MIN_VALUE (TREE_TYPE (name)), TYPE_MAX_VALUE (TREE_TYPE (name))); range_info_def *ri = SSA_NAME_RANGE_INFO (name); @@ -495,7 +504,8 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) /* Creates a duplicate of the range_info_def at RANGE_INFO of type RANGE_TYPE for use by the SSA name NAME. */ void -duplicate_ssa_name_range_info (tree name, enum value_range_type range_type, +duplicate_ssa_name_range_info (tree name, + enum value_range_type range_type ATTRIBUTE_UNUSED, struct range_info_def *range_info) { struct range_info_def *new_range_info; @@ -513,8 +523,6 @@ duplicate_ssa_name_range_info (tree name, enum value_range_type range_type, new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size)); memcpy (new_range_info, range_info, size); - gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); SSA_NAME_RANGE_INFO (name) = new_range_info; } diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index a7eeb8f..0d4b212 100644 --- a/gcc/tree-ssanames.h +++ b/gcc/tree-ssanames.h @@ -68,7 +68,7 @@ struct GTY ((variable_size)) range_info_def { enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; /* Sets the value range to SSA. */ -extern void set_range_info (tree, enum value_range_type, const wide_int_ref &, +extern void set_range_info (tree, const wide_int_ref &, const wide_int_ref &); /* Gets the value range from SSA. */ extern enum value_range_type get_range_info (const_tree, wide_int *, diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index e7ab23c..d823be9 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -6934,7 +6934,7 @@ remove_range_assertions (void) && all_imm_uses_in_stmt_or_feed_cond (var, stmt, single_pred (bb))) { - set_range_info (var, SSA_NAME_RANGE_TYPE (lhs), + set_range_info (var, SSA_NAME_RANGE_INFO (lhs)->get_min (), SSA_NAME_RANGE_INFO (lhs)->get_max ()); maybe_set_nonzero_bits (bb, var); @@ -10258,12 +10258,35 @@ vrp_finalize (void) || (vr_value[i]->type == VR_UNDEFINED)) continue; - if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST) - && (TREE_CODE (vr_value[i]->max) == INTEGER_CST) - && (vr_value[i]->type == VR_RANGE - || vr_value[i]->type == VR_ANTI_RANGE)) - set_range_info (name, vr_value[i]->type, vr_value[i]->min, - vr_value[i]->max); + if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST) + && (TREE_CODE (vr_value[i]->max) == INTEGER_CST) + && (vr_value[i]->type == VR_RANGE + || vr_value[i]->type == VR_ANTI_RANGE)) + { + if (vr_value[i]->type == VR_RANGE) + set_range_info (name, vr_value[i]->min, vr_value[i]->max); + else if (vr_value[i]->type == VR_ANTI_RANGE) + { + /* VR_ANTI_RANGE + ~[min, max] is encoded compactly as + [max + 1, min - 1] without additional attributes. + When min value > max value, we know that it is + VR_ANTI_RANGE; it is VR_RANGE otherwise. */ + + if (TYPE_UNSIGNED (TREE_TYPE (name)) + && integer_zerop (vr_value[i]->min) + && integer_zerop (vr_value[i]->max)) + /* ~[0,0] anti-range is represented as range. */ + set_range_info (name, + build_int_cst (TREE_TYPE (name), 1), + TYPE_MAXVAL (TREE_TYPE (name))); + else + set_range_info (name, + wi::add (vr_value[i]->max, 1), + wi::sub (vr_value[i]->min, 1)); + } + } + } /* Free allocated memory. */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* [RFC][PATCH 2/3] Propagate and save value ranges wrapped information 2015-01-17 2:10 [RFC][PATCH 0/3] Re-enable zero/sign extension elimination using value ranges Kugan 2015-01-17 2:11 ` [RFC][PATCH 1/3] Free a bit in SSA_NAME to save wrapped information Kugan @ 2015-01-17 2:44 ` Kugan 2015-01-19 12:52 ` Richard Biener 2015-01-17 2:58 ` [RFC][PATCH 3/3] Enable zero/sign extension elimination Kugan 2 siblings, 1 reply; 14+ messages in thread From: Kugan @ 2015-01-17 2:44 UTC (permalink / raw) To: gcc-patches; +Cc: Richard Biener, Jakub Jelinek, Jeff Law [-- Attachment #1: Type: text/plain, Size: 2508 bytes --] This patch propagate value range wrapps attribute and save this to SSA_NAME. Thanks, Kugan gcc/ChangeLog: 2015-01-16 Kugan Vivekanandarajah <kuganv@linaro.org> * builtins.c (determine_block_size): Use new definition of get_range_info. * gimple-pretty-print.c (dump_ssaname_info): Dump new wrapped info. * internal-fn.c (get_range_pos_neg): Use new definition of get_range_info. (get_min_precision): Likewise. * tree-ssa-copy.c (fini_copy_prop): Use new definition of duplicate_ssa_range_info. * tree-ssa-loop-im.c (move_computations_dom_walker::before_dom_children): Likewise. * tree-ssa-pre.c (eliminate_dom_walker::before_dom_children): Likewise. * tree-ssa-loop-niter.c (determine_value_range): Use new definition. * tree-ssanames.c (set_range_info): Save wrapped information. (get_range_info): Retrive wrapped information. (set_nonzero_bits): Set wrapped info. (duplicate_ssa_name_range_info): Likewise. (duplicate_ssa_name_fn): Likewise. * tree-ssanames.h: (set_range_info): Update definition. (get_range_info): Ditto. * tree-vect-patterns.c (vect_recog_divmod_pattern): Use new declaration get_range_info. * tree-vrp.c (struct value_range_d): Add wrapped field. (set_value_range): Calculate and add wrapped field. (set_and_canonicalize_value_range): Likewise. (copy_value_range): Likewise. (set_value_range_to_value): Likewise. (set_value_range_to_nonnegative): Likewise. (set_value_range_to_nonnull): Likewise. (set_value_range_to_truthvalue): Likewise. (abs_extent_range): Likewise. (get_value_range): Return wrapped info. (update_value_range): Save wrapped info. (extract_range_from_assert): Extract and update wrapped info. (extract_range_from_ssa_name): Likewise. (vrp_int_const_binop): Likewise. (extract_range_from_multiplicative_op_1): Likewise. (extract_range_from_binary_expr_1): Likewise. (extract_range_from_binary_expr): Likewise. (extract_range_from_unary_expr_1): Likewise. (extract_range_from_comparison): Likewise. (extract_range_basic): Likewise. (adjust_range_with_scev): Likewise. (dump_value_range): Dump wrapped info. (remove_range_assertions): Update parameters. (vrp_intersect_ranges_1): Propagate wrapped info. (vrp_meet_1): Likewise. (vrp_visit_phi_node): Save wrapped info to SSA. (vrp_finalize): Likewise. * tree.h (SSA_NAME_ANTI_RANGE_P): Remove. (SSA_NAME_RANGE_OVF_P): New. gcc/testsuite/ChangeLog: 2015-01-16 Kugan Vivekanandarajah <kuganv@linaro.org> * gcc.dg/tree-ssa/vrp92.c: Update scanned pattern. [-- Attachment #2: patch2.txt --] [-- Type: text/plain, Size: 32642 bytes --] diff --git a/gcc/builtins.c b/gcc/builtins.c index 9280704..83a0882 100644 --- a/gcc/builtins.c +++ b/gcc/builtins.c @@ -3150,7 +3150,7 @@ determine_block_size (tree len, rtx len_rtx, *probable_max_size = *max_size = GET_MODE_MASK (GET_MODE (len_rtx)); if (TREE_CODE (len) == SSA_NAME) - range_type = get_range_info (len, &min, &max); + range_type = get_range_info (len, &min, &max, NULL); if (range_type == VR_RANGE) { if (wi::fits_uhwi_p (min) && *min_size < min.to_uhwi ()) diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c index 21e98c6..4d41bca 100644 --- a/gcc/gimple-pretty-print.c +++ b/gcc/gimple-pretty-print.c @@ -1812,13 +1812,15 @@ dump_ssaname_info (pretty_printer *buffer, tree node, int spc) && SSA_NAME_RANGE_INFO (node)) { wide_int min, max, nonzero_bits; - value_range_type range_type = get_range_info (node, &min, &max); + bool wrapped; + value_range_type range_type = get_range_info (node, &min, &max, &wrapped); if (range_type == VR_VARYING) pp_printf (buffer, "# RANGE VR_VARYING"); else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE) { pp_printf (buffer, "# RANGE "); + pp_printf (buffer, "WRAPPED = %s ", wrapped ? "true" : "false"); pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~"); pp_wide_int (buffer, min, TYPE_SIGN (TREE_TYPE (node))); pp_printf (buffer, ", "); diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c index 07a9ec5..8955bb8 100644 --- a/gcc/internal-fn.c +++ b/gcc/internal-fn.c @@ -262,7 +262,7 @@ get_range_pos_neg (tree arg) if (TREE_CODE (arg) != SSA_NAME) return 3; wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + while (get_range_info (arg, &arg_min, &arg_max, NULL) != VR_RANGE) { gimple g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) @@ -344,7 +344,7 @@ get_min_precision (tree arg, signop sign) if (TREE_CODE (arg) != SSA_NAME) return prec + (orig_sign != sign); wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + while (get_range_info (arg, &arg_min, &arg_max, NULL) != VR_RANGE) { gimple g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c index a84ba8e..67a2afc 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c @@ -18,6 +18,6 @@ int foo (int i, int j) return j; } -/* { dg-final { scan-tree-dump "res_.: \\\[1, 1\\\]" "vrp1" } } */ +/* { dg-final { scan-tree-dump "res_.: NOWRAPP \\\[1, 1\\\]" "vrp1" } } */ /* { dg-final { scan-tree-dump-not "Threaded" "vrp1" } } */ /* { dg-final { cleanup-tree-dump "vrp1" } } */ diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c index 5ae8e6c..637588c 100644 --- a/gcc/tree-ssa-copy.c +++ b/gcc/tree-ssa-copy.c @@ -574,8 +574,8 @@ fini_copy_prop (void) && !SSA_NAME_RANGE_INFO (copy_of[i].value) && var_bb == copy_of_bb) duplicate_ssa_name_range_info (copy_of[i].value, - SSA_NAME_RANGE_TYPE (var), - SSA_NAME_RANGE_INFO (var)); + SSA_NAME_RANGE_INFO (var), + SSA_NAME_RANGE_WRAPPED_P (var)); } } diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index 9aba79b..3c97fb2 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -1245,7 +1245,6 @@ move_computations_dom_walker::before_dom_children (basic_block bb) { tree lhs = gimple_assign_lhs (new_stmt); SSA_NAME_RANGE_INFO (lhs) = NULL; - SSA_NAME_ANTI_RANGE_P (lhs) = 0; } gsi_insert_on_edge (loop_preheader_edge (level), new_stmt); remove_phi_node (&bsi, false); @@ -1315,7 +1314,6 @@ move_computations_dom_walker::before_dom_children (basic_block bb) { tree lhs = gimple_get_lhs (stmt); SSA_NAME_RANGE_INFO (lhs) = NULL; - SSA_NAME_ANTI_RANGE_P (lhs) = 0; } /* In case this is a stmt that is not unconditionally executed when the target loop header is executed and the stmt may diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 7b0313a..5655e06 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -165,7 +165,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, gphi_iterator gsi; /* Either for VAR itself... */ - rtype = get_range_info (var, &minv, &maxv); + rtype = get_range_info (var, &minv, &maxv, NULL); /* Or for PHI results in loop->header where VAR is used as PHI argument from the loop preheader edge. */ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) @@ -173,7 +173,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, gphi *phi = gsi.phi (); wide_int minc, maxc; if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var - && (get_range_info (gimple_phi_result (phi), &minc, &maxc) + && (get_range_info (gimple_phi_result (phi), &minc, &maxc, NULL) == VR_RANGE)) { if (rtype != VR_RANGE) @@ -192,7 +192,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, involved. */ if (wi::gt_p (minv, maxv, sgn)) { - rtype = get_range_info (var, &minv, &maxv); + rtype = get_range_info (var, &minv, &maxv, NULL); break; } } diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 497890f..6a61232 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -4107,8 +4107,8 @@ eliminate_dom_walker::before_dom_children (basic_block b) && !SSA_NAME_RANGE_INFO (sprime) && b == sprime_b) duplicate_ssa_name_range_info (sprime, - SSA_NAME_RANGE_TYPE (lhs), - SSA_NAME_RANGE_INFO (lhs)); + SSA_NAME_RANGE_INFO (lhs), + SSA_NAME_RANGE_WRAPPED_P (lhs)); } /* Inhibit the use of an inserted PHI on a loop header when diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 744dc43..6e49616 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -201,7 +201,7 @@ make_ssa_name_fn (struct function *fn, tree var, gimple stmt) void set_range_info (tree name, - const wide_int_ref &min, const wide_int_ref &max) + const wide_int_ref &min, const wide_int_ref &max, bool is_wrapped) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); range_info_def *ri = SSA_NAME_RANGE_INFO (name); @@ -221,6 +221,7 @@ set_range_info (tree name, /* Set the values. */ ri->set_min (min); ri->set_max (max); + SSA_NAME_RANGE_WRAPPED_P (name) = is_wrapped; /* If it is a range, try to improve nonzero_bits from the min/max. */ if (wi::cmp (min, max, TYPE_SIGN (TREE_TYPE (name))) < 0) @@ -238,7 +239,7 @@ set_range_info (tree name, is used to determine if MIN and MAX are valid values. */ enum value_range_type -get_range_info (const_tree name, wide_int *min, wide_int *max) +get_range_info (const_tree name, wide_int *min, wide_int *max, bool *is_wrapped) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (min && max); @@ -266,6 +267,8 @@ get_range_info (const_tree name, wide_int *min, wide_int *max) *min = ri->get_min (); *max = ri->get_max (); } + if (is_wrapped) + *is_wrapped = SSA_NAME_RANGE_WRAPPED_P (name); return range_type; } @@ -278,7 +281,8 @@ set_nonzero_bits (tree name, const wide_int_ref &mask) if (SSA_NAME_RANGE_INFO (name) == NULL) set_range_info (name, TYPE_MIN_VALUE (TREE_TYPE (name)), - TYPE_MAX_VALUE (TREE_TYPE (name))); + TYPE_MAX_VALUE (TREE_TYPE (name)), + false); range_info_def *ri = SSA_NAME_RANGE_INFO (name); ri->set_nonzero_bits (mask); } @@ -505,14 +509,13 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) RANGE_TYPE for use by the SSA name NAME. */ void duplicate_ssa_name_range_info (tree name, - enum value_range_type range_type ATTRIBUTE_UNUSED, - struct range_info_def *range_info) + struct range_info_def *range_info, + bool is_wrapped) { struct range_info_def *new_range_info; gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (!SSA_NAME_RANGE_INFO (name)); - gcc_assert (!SSA_NAME_ANTI_RANGE_P (name)); if (!range_info) return; @@ -523,6 +526,7 @@ duplicate_ssa_name_range_info (tree name, new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size)); memcpy (new_range_info, range_info, size); + SSA_NAME_RANGE_WRAPPED_P (name) = is_wrapped; SSA_NAME_RANGE_INFO (name) = new_range_info; } @@ -547,8 +551,9 @@ duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt) struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name); if (old_range_info) - duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name), - old_range_info); + duplicate_ssa_name_range_info (new_name, + old_range_info, + SSA_NAME_RANGE_WRAPPED_P (name)); } return new_name; diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index 0d4b212..7bb33db 100644 --- a/gcc/tree-ssanames.h +++ b/gcc/tree-ssanames.h @@ -69,10 +69,10 @@ enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; /* Sets the value range to SSA. */ extern void set_range_info (tree, const wide_int_ref &, - const wide_int_ref &); + const wide_int_ref &, bool); /* Gets the value range from SSA. */ extern enum value_range_type get_range_info (const_tree, wide_int *, - wide_int *); + wide_int *, bool *); extern void set_nonzero_bits (tree, const wide_int_ref &); extern wide_int get_nonzero_bits (const_tree); extern void init_ssanames (struct function *, int); @@ -92,8 +92,9 @@ extern struct ptr_info_def *get_ptr_info (tree); extern tree copy_ssa_name_fn (struct function *, tree, gimple); extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *); extern tree duplicate_ssa_name_fn (struct function *, tree, gimple); -extern void duplicate_ssa_name_range_info (tree, enum value_range_type, - struct range_info_def *); +extern void duplicate_ssa_name_range_info (tree, + struct range_info_def *, + bool); extern void release_defs (gimple); extern void replace_ssa_name_symbol (tree, tree); diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c index 814222b..09ca14d 100644 --- a/gcc/tree-vect-patterns.c +++ b/gcc/tree-vect-patterns.c @@ -2553,7 +2553,7 @@ vect_recog_divmod_pattern (vec<gimple> *stmts, wide_int oprnd0_min, oprnd0_max; int msb = 1; - if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE) + if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max, NULL) == VR_RANGE) { if (!wi::neg_p (oprnd0_min, TYPE_SIGN (itype))) msb = 0; diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 9b7695d..832c35d 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -103,6 +103,9 @@ struct value_range_d tree min; tree max; + /* Set to true if values in this value range could wrapp. */ + bool is_wrapped; + /* Set of SSA names whose value ranges are equivalent to this one. This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ bitmap equiv; @@ -110,7 +113,7 @@ struct value_range_d typedef struct value_range_d value_range_t; -#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } +#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, false, NULL } /* Set of SSA names found live during the RPO traversal of the function for still active basic-blocks. */ @@ -447,7 +450,7 @@ set_value_range_to_varying (value_range_t *vr) static void set_value_range (value_range_t *vr, enum value_range_type t, tree min, - tree max, bitmap equiv) + tree max, bool is_wrapped, bitmap equiv) { #if defined ENABLE_CHECKING /* Check the validity of the range. */ @@ -481,6 +484,7 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, vr->type = t; vr->min = min; vr->max = max; + vr->is_wrapped = is_wrapped; /* Since updating the equivalence set involves deep copying the bitmaps, only do it if absolutely necessary. */ @@ -509,7 +513,7 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, static void set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, - tree min, tree max, bitmap equiv) + tree min, tree max, bool is_wrapped, bitmap equiv) { /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ if (t == VR_UNDEFINED) @@ -527,7 +531,7 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, if (TREE_CODE (min) != INTEGER_CST || TREE_CODE (max) != INTEGER_CST) { - set_value_range (vr, t, min, max, equiv); + set_value_range (vr, t, min, max, is_wrapped, equiv); return; } @@ -615,7 +619,7 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, return; } - set_value_range (vr, t, min, max, equiv); + set_value_range (vr, t, min, max, is_wrapped, equiv); } /* Copy value range FROM into value range TO. */ @@ -623,7 +627,8 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, static inline void copy_value_range (value_range_t *to, value_range_t *from) { - set_value_range (to, from->type, from->min, from->max, from->equiv); + set_value_range (to, from->type, from->min, from->max, + from->is_wrapped, from->equiv); } /* Set value range VR to a single value. This function is only called @@ -637,7 +642,7 @@ set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv) gcc_assert (is_gimple_min_invariant (val)); if (TREE_OVERFLOW_P (val)) val = drop_tree_overflow (val); - set_value_range (vr, VR_RANGE, val, val, equiv); + set_value_range (vr, VR_RANGE, val, val, false, equiv); } /* Set value range VR to a non-negative range of type TYPE. @@ -663,6 +668,7 @@ set_value_range_to_nonnegative (value_range_t *vr, tree type, (overflow_infinity ? positive_overflow_infinity (type) : TYPE_MAX_VALUE (type)), + false, vr->equiv); } @@ -672,7 +678,7 @@ static inline void set_value_range_to_nonnull (value_range_t *vr, tree type) { tree zero = build_int_cst (type, 0); - set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv); + set_value_range (vr, VR_ANTI_RANGE, zero, zero, false, vr->equiv); } @@ -695,6 +701,7 @@ set_value_range_to_truthvalue (value_range_t *vr, tree type) else set_value_range (vr, VR_RANGE, build_int_cst (type, 0), build_int_cst (type, 1), + false, vr->equiv); } @@ -731,7 +738,7 @@ abs_extent_range (value_range_t *vr, tree min, tree max) set_value_range_to_varying (vr); return; } - set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); + set_and_canonicalize_value_range (vr, VR_RANGE, min, max, false, NULL); } @@ -744,7 +751,7 @@ static value_range_t * get_value_range (const_tree var) { static const struct value_range_d vr_const_varying - = { VR_VARYING, NULL_TREE, NULL_TREE, NULL }; + = { VR_VARYING, NULL_TREE, NULL_TREE, false, NULL }; value_range_t *vr; tree sym; unsigned ver = SSA_NAME_VERSION (var); @@ -842,6 +849,7 @@ update_value_range (const_tree var, value_range_t *new_vr) is_new = old_vr->type != new_vr->type || !vrp_operand_equal_p (old_vr->min, new_vr->min) || !vrp_operand_equal_p (old_vr->max, new_vr->max) + || old_vr->is_wrapped != new_vr->is_wrapped || !vrp_bitmap_equal_p (old_vr->equiv, new_vr->equiv); if (is_new) @@ -856,6 +864,7 @@ update_value_range (const_tree var, value_range_t *new_vr) set_value_range_to_varying (old_vr); else set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max, + new_vr->is_wrapped, new_vr->equiv); } @@ -1745,10 +1754,10 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) this for us. */ if (cond_code == LE_EXPR) set_and_canonicalize_value_range (vr_p, VR_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); else if (cond_code == GT_EXPR) set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); else gcc_unreachable (); } @@ -1769,7 +1778,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) max = limit; } - set_value_range (vr_p, range_type, min, max, vr_p->equiv); + set_value_range (vr_p, range_type, min, max, false, vr_p->equiv); /* When asserting the equality VAR == LIMIT and LIMIT is another SSA name, the new range will also inherit the equivalence set @@ -1821,7 +1830,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) min = max = limit; set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); } else if (cond_code == LE_EXPR || cond_code == LT_EXPR) { @@ -1860,7 +1869,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) TREE_NO_WARNING (max) = 1; } - set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); + set_value_range (vr_p, VR_RANGE, min, max, false, vr_p->equiv); } } else if (cond_code == GE_EXPR || cond_code == GT_EXPR) @@ -1900,7 +1909,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) TREE_NO_WARNING (min) = 1; } - set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); + set_value_range (vr_p, VR_RANGE, min, max, false, vr_p->equiv); } } else @@ -1932,7 +1941,7 @@ extract_range_from_ssa_name (value_range_t *vr, tree var) if (var_vr->type != VR_VARYING) copy_value_range (vr, var_vr); else - set_value_range (vr, VR_RANGE, var, var, NULL); + set_value_range (vr, VR_RANGE, var, var, false, NULL); add_equivalence (&vr->equiv, var); } @@ -1945,11 +1954,13 @@ extract_range_from_ssa_name (value_range_t *vr, tree var) the type does not support it. */ static tree -vrp_int_const_binop (enum tree_code code, tree val1, tree val2) +vrp_int_const_binop (enum tree_code code, tree val1, tree val2, bool *is_wrapped) { tree res; res = int_const_binop (code, val1, val2); + if (is_wrapped) + *is_wrapped = false; /* If we are using unsigned arithmetic, operate symbolically on -INF and +INF as int_const_binop only handles signed overflow. */ @@ -1993,7 +2004,10 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1))) /* If the singed operation wraps then int_const_binop has done everything we want. */ - ; + { + if (is_wrapped) + *is_wrapped = true; + } /* Signed division of -1/0 overflows and by the time it gets here returns NULL_TREE. */ else if (!res) @@ -2187,6 +2201,8 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, tree min, max; bool sop; int cmp; + bool is_wrapped = false; + bool t_is_wrapped = false; /* Multiplications, divisions and shifts are a bit tricky to handle, depending on the mix of signs we have in the two ranges, we @@ -2216,35 +2232,43 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, /* Compute the 4 cross operations. */ sop = false; - val[0] = vrp_int_const_binop (code, vr0->min, vr1->min); + val[0] = vrp_int_const_binop (code, vr0->min, vr1->min, &t_is_wrapped); if (val[0] == NULL_TREE) sop = true; + if (t_is_wrapped) + is_wrapped = true; if (vr1->max == vr1->min) val[1] = NULL_TREE; else { - val[1] = vrp_int_const_binop (code, vr0->min, vr1->max); + val[1] = vrp_int_const_binop (code, vr0->min, vr1->max, &t_is_wrapped); if (val[1] == NULL_TREE) sop = true; + if (t_is_wrapped) + is_wrapped = true; } if (vr0->max == vr0->min) val[2] = NULL_TREE; else { - val[2] = vrp_int_const_binop (code, vr0->max, vr1->min); + val[2] = vrp_int_const_binop (code, vr0->max, vr1->min, &t_is_wrapped); if (val[2] == NULL_TREE) sop = true; + if (t_is_wrapped) + is_wrapped = true; } if (vr0->min == vr0->max || vr1->min == vr1->max) val[3] = NULL_TREE; else { - val[3] = vrp_int_const_binop (code, vr0->max, vr1->max); + val[3] = vrp_int_const_binop (code, vr0->max, vr1->max, &t_is_wrapped); if (val[3] == NULL_TREE) sop = true; + if (t_is_wrapped) + is_wrapped = true; } if (sop) @@ -2324,7 +2348,7 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, type, min, max, NULL); + set_value_range (vr, type, min, max, is_wrapped, NULL); } /* Extract range information from a binary operation CODE based on @@ -2341,6 +2365,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, enum value_range_type type; tree min = NULL_TREE, max = NULL_TREE; int cmp; + bool vr_is_wrapped = false; if (!INTEGRAL_TYPE_P (expr_type) && !POINTER_TYPE_P (expr_type)) @@ -2640,6 +2665,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, range kind and bounds appropriately. */ wide_int tmin = wide_int::from (wmin, prec, sgn); wide_int tmax = wide_int::from (wmax, prec, sgn); + vr_is_wrapped = true; if (min_ovf == max_ovf) { /* No overflow or both overflow or underflow. The @@ -2792,8 +2818,8 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* For operations that make the resulting range directly proportional to the original ranges, apply the operation to the same end of each range. */ - min = vrp_int_const_binop (code, vr0.min, vr1.min); - max = vrp_int_const_binop (code, vr0.max, vr1.max); + min = vrp_int_const_binop (code, vr0.min, vr1.min, NULL); + max = vrp_int_const_binop (code, vr0.max, vr1.max, NULL); } else if (code == MIN_EXPR) { @@ -2917,9 +2943,10 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* The following should handle the wrapping and selecting VR_ANTI_RANGE for us. */ + vr_is_wrapped = true; min = wide_int_to_tree (expr_type, prod0); max = wide_int_to_tree (expr_type, prod3); - set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); + set_and_canonicalize_value_range (vr, VR_RANGE, min, max, vr_is_wrapped, NULL); return; } @@ -3287,7 +3314,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, type, min, max, NULL); + set_value_range (vr, type, min, max, vr_is_wrapped, NULL); } /* Extract range information from a binary expression OP0 CODE OP1 based on @@ -3336,15 +3363,15 @@ extract_range_from_binary_expr (value_range_t *vr, /* Try with VR0 and [-INF, OP1]. */ if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min)) - set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); + set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, false, NULL); /* Try with VR0 and [OP1, +INF]. */ else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max)) - set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); + set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), false, NULL); /* Try with VR0 and [OP1, OP1]. */ else - set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL); + set_value_range (&n_vr1, VR_RANGE, op1, op1, false, NULL); extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1); } @@ -3360,15 +3387,15 @@ extract_range_from_binary_expr (value_range_t *vr, /* Try with [-INF, OP0] and VR1. */ if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min)) - set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL); + set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, false, NULL); /* Try with [OP0, +INF] and VR1. */ else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max)) - set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL); + set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), false, NULL); /* Try with [OP0, OP0] and VR1. */ else - set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL); + set_value_range (&n_vr0, VR_RANGE, op0, op0, false, NULL); extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1); } @@ -3384,6 +3411,7 @@ extract_range_from_unary_expr_1 (value_range_t *vr, value_range_t *vr0_, tree op0_type) { value_range_t vr0 = *vr0_, vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER; + bool vr_is_wrapped = false; /* VRP only operates on integral and pointer types. */ if (!(INTEGRAL_TYPE_P (op0_type) @@ -3504,15 +3532,23 @@ extract_range_from_unary_expr_1 (value_range_t *vr, if (is_overflow_infinity (vr0.min)) new_min = negative_overflow_infinity (outer_type); else - new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), - 0, false); + { + if (!int_fits_type_p (vr0.min, outer_type)) + vr_is_wrapped = true; + new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), + 0, false); + } if (is_overflow_infinity (vr0.max)) new_max = positive_overflow_infinity (outer_type); else - new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), - 0, false); + { + if (!int_fits_type_p (vr0.max, outer_type)) + vr_is_wrapped = true; + new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), + 0, false); + } set_and_canonicalize_value_range (vr, vr0.type, - new_min, new_max, NULL); + new_min, new_max, vr_is_wrapped, NULL); return; } @@ -3626,6 +3662,7 @@ extract_range_from_unary_expr_1 (value_range_t *vr, anti-range. */ vr0.type = VR_RANGE; min = build_int_cst (type, 0); + vr_is_wrapped = true; if (needs_overflow_infinity (type)) { if (supports_overflow_infinity (type)) @@ -3669,7 +3706,7 @@ extract_range_from_unary_expr_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, vr0.type, min, max, NULL); + set_value_range (vr, vr0.type, min, max, vr_is_wrapped, NULL); return; } @@ -3763,7 +3800,7 @@ extract_range_from_comparison (value_range_t *vr, enum tree_code code, if (is_gimple_min_invariant (val)) set_value_range_to_value (vr, val, vr->equiv); else - set_value_range (vr, VR_RANGE, val, val, vr->equiv); + set_value_range (vr, VR_RANGE, val, val, false, vr->equiv); } else /* The result of a comparison is always true or false. */ @@ -4060,7 +4097,7 @@ extract_range_basic (value_range_t *vr, gimple stmt) goto bitop_builtin; bitop_builtin: set_value_range (vr, VR_RANGE, build_int_cst (type, mini), - build_int_cst (type, maxi), NULL); + build_int_cst (type, maxi), false, NULL); return; default: break; @@ -4150,7 +4187,7 @@ extract_range_basic (value_range_t *vr, gimple stmt) NULL); else set_value_range (vr, VR_RANGE, build_int_cst (type, 0), - build_int_cst (type, 1), NULL); + build_int_cst (type, 1), false, NULL); } else if (types_compatible_p (type, TREE_TYPE (op0)) && types_compatible_p (type, TREE_TYPE (op1))) @@ -4244,6 +4281,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, { tree init, step, chrec, tmin, tmax, min, max, type, tem; enum ev_direction dir; + bool t_is_wrapped = false, is_wrapped = false; /* TODO. Don't adjust anti-ranges. An anti-range may provide better opportunities than a regular range, but I'm not sure. */ @@ -4339,6 +4377,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, /* Likewise if the addition did. */ if (maxvr.type == VR_RANGE) { + t_is_wrapped = maxvr.is_wrapped; tmin = maxvr.min; tmax = maxvr.max; } @@ -4350,6 +4389,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, { min = tmin; max = tmax; + is_wrapped = t_is_wrapped; /* For VARYING or UNDEFINED ranges, just about anything we get from scalar evolutions should be better. */ @@ -4403,7 +4443,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, && is_positive_overflow_infinity (max))) return; - set_value_range (vr, VR_RANGE, min, max, vr->equiv); + set_value_range (vr, VR_RANGE, min, max, is_wrapped, vr->equiv); } @@ -4722,7 +4762,8 @@ dump_value_range (FILE *file, value_range_t *vr) { tree type = TREE_TYPE (vr->min); - fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); + fprintf (file, "%s %s[", vr->is_wrapped ? "WRAPP" : "NOWRAPP", + (vr->type == VR_ANTI_RANGE) ? "~" : ""); if (is_negative_overflow_infinity (vr->min)) fprintf (file, "-INF(OVF)"); @@ -6917,7 +6958,8 @@ remove_range_assertions (void) { set_range_info (var, SSA_NAME_RANGE_INFO (lhs)->get_min (), - SSA_NAME_RANGE_INFO (lhs)->get_max ()); + SSA_NAME_RANGE_INFO (lhs)->get_max (), + SSA_NAME_RANGE_WRAPPED_P (lhs)); maybe_set_nonzero_bits (bb, var); } } @@ -8584,7 +8626,9 @@ vrp_intersect_ranges_1 (value_range_t *vr0, value_range_t *vr1) /* Make sure to canonicalize the result though as the inversion of a VR_RANGE can still be a VR_RANGE. */ set_and_canonicalize_value_range (vr0, vr0->type, - vr0->min, vr0->max, vr0->equiv); + vr0->min, vr0->max, + vr0->is_wrapped && vr1->is_wrapped, + vr0->equiv); /* If that failed, use the saved original VR0. */ if (vr0->type == VR_VARYING) { @@ -8635,7 +8679,7 @@ vrp_meet_1 (value_range_t *vr0, value_range_t *vr1) if (vr0->type == VR_UNDEFINED) { - set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv); + set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->is_wrapped, vr1->equiv); return; } @@ -8689,6 +8733,7 @@ vrp_meet_1 (value_range_t *vr0, value_range_t *vr1) return; } set_and_canonicalize_value_range (vr0, vr0->type, vr0->min, vr0->max, + vr0->is_wrapped && vr1->is_wrapped, vr0->equiv); if (vr0->type == VR_VARYING) return; @@ -8747,6 +8792,7 @@ vrp_visit_phi_node (gphi *phi) for (i = 0; i < gimple_phi_num_args (phi); i++) { edge e = gimple_phi_arg_edge (phi, i); + bool is_wrapped = false; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -8792,6 +8838,7 @@ vrp_visit_phi_node (gphi *phi) vr_arg.type = VR_RANGE; vr_arg.min = arg; vr_arg.max = arg; + vr_arg.is_wrapped = is_wrapped; vr_arg.equiv = NULL; } } @@ -8804,6 +8851,7 @@ vrp_visit_phi_node (gphi *phi) vr_arg.type = VR_RANGE; vr_arg.min = arg; vr_arg.max = arg; + vr_arg.is_wrapped = is_wrapped; vr_arg.equiv = NULL; } @@ -10244,7 +10292,7 @@ vrp_finalize (void) || vr_value[i]->type == VR_ANTI_RANGE)) { if (vr_value[i]->type == VR_RANGE) - set_range_info (name, vr_value[i]->min, vr_value[i]->max); + set_range_info (name, vr_value[i]->min, vr_value[i]->max, vr_value[i]->is_wrapped); else if (vr_value[i]->type == VR_ANTI_RANGE) { /* VR_ANTI_RANGE @@ -10259,11 +10307,13 @@ vrp_finalize (void) /* ~[0,0] anti-range is represented as range. */ set_range_info (name, build_int_cst (TREE_TYPE (name), 1), - TYPE_MAXVAL (TREE_TYPE (name))); + TYPE_MAXVAL (TREE_TYPE (name)), + vr_value[i]->is_wrapped); else set_range_info (name, wi::add (vr_value[i]->max, 1), - wi::sub (vr_value[i]->min, 1)); + wi::sub (vr_value[i]->min, 1), + vr_value[i]->is_wrapped); } } diff --git a/gcc/tree.h b/gcc/tree.h index ac27268..946321a 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -1467,7 +1467,7 @@ extern void protected_set_expr_location (tree, location_t); SSA_NAME_CHECK (N)->ssa_name.info.ptr_info /* True if SSA_NAME_RANGE_INFO describes an anti-range. */ -#define SSA_NAME_ANTI_RANGE_P(N) \ +#define SSA_NAME_RANGE_WRAPPED_P(N) \ SSA_NAME_CHECK (N)->base.static_flag /* The type of range described by SSA_NAME_RANGE_INFO. */ ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 2/3] Propagate and save value ranges wrapped information 2015-01-17 2:44 ` [RFC][PATCH 2/3] Propagate and save value ranges " Kugan @ 2015-01-19 12:52 ` Richard Biener 2015-04-22 22:11 ` Kugan 0 siblings, 1 reply; 14+ messages in thread From: Richard Biener @ 2015-01-19 12:52 UTC (permalink / raw) To: Kugan; +Cc: gcc-patches, Jakub Jelinek, Jeff Law On Sat, 17 Jan 2015, Kugan wrote: > > This patch propagate value range wrapps attribute and save this to > SSA_NAME. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 9b7695d..832c35d 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -103,6 +103,9 @@ struct value_range_d tree min; tree max; + /* Set to true if values in this value range could wrapp. */ + bool is_wrapped; + /* Set of SSA names whose value ranges are equivalent to this one. This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ bitmap equiv; I can't make sense of this description (wrap with one p as well). I assume you mean that the expression that has this value-range assigned has an operation that may have wrapped? (a value can't wrap) You need to specify how is_wrapped behaves for range union and intersect operations and which operations can wrap. I miss an overall description of these patches as to a) why you need this information and b) why it helps. It's now also too late and thus you have plenty of time until stage1 starts again. Thanks, Richard. > Thanks, > Kugan > > gcc/ChangeLog: > > 2015-01-16 Kugan Vivekanandarajah <kuganv@linaro.org> > > * builtins.c (determine_block_size): Use new definition of > get_range_info. > * gimple-pretty-print.c (dump_ssaname_info): Dump new wrapped info. > * internal-fn.c (get_range_pos_neg): Use new definition of > get_range_info. > (get_min_precision): Likewise. > * tree-ssa-copy.c (fini_copy_prop): Use new definition of > duplicate_ssa_range_info. > * tree-ssa-loop-im.c > (move_computations_dom_walker::before_dom_children): Likewise. > * tree-ssa-pre.c (eliminate_dom_walker::before_dom_children): Likewise. > * tree-ssa-loop-niter.c (determine_value_range): Use new definition. > * tree-ssanames.c (set_range_info): Save wrapped information. > (get_range_info): Retrive wrapped information. > (set_nonzero_bits): Set wrapped info. > (duplicate_ssa_name_range_info): Likewise. > (duplicate_ssa_name_fn): Likewise. > * tree-ssanames.h: (set_range_info): Update definition. > (get_range_info): Ditto. > * tree-vect-patterns.c (vect_recog_divmod_pattern): Use new > declaration get_range_info. > * tree-vrp.c (struct value_range_d): Add wrapped field. > (set_value_range): Calculate and add wrapped field. > (set_and_canonicalize_value_range): Likewise. > (copy_value_range): Likewise. > (set_value_range_to_value): Likewise. > (set_value_range_to_nonnegative): Likewise. > (set_value_range_to_nonnull): Likewise. > (set_value_range_to_truthvalue): Likewise. > (abs_extent_range): Likewise. > (get_value_range): Return wrapped info. > (update_value_range): Save wrapped info. > (extract_range_from_assert): Extract and update wrapped info. > (extract_range_from_ssa_name): Likewise. > (vrp_int_const_binop): Likewise. > (extract_range_from_multiplicative_op_1): Likewise. > (extract_range_from_binary_expr_1): Likewise. > (extract_range_from_binary_expr): Likewise. > (extract_range_from_unary_expr_1): Likewise. > (extract_range_from_comparison): Likewise. > (extract_range_basic): Likewise. > (adjust_range_with_scev): Likewise. > (dump_value_range): Dump wrapped info. > (remove_range_assertions): Update parameters. > (vrp_intersect_ranges_1): Propagate wrapped info. > (vrp_meet_1): Likewise. > (vrp_visit_phi_node): Save wrapped info to SSA. > (vrp_finalize): Likewise. > * tree.h (SSA_NAME_ANTI_RANGE_P): Remove. > (SSA_NAME_RANGE_OVF_P): New. > > gcc/testsuite/ChangeLog: > > 2015-01-16 Kugan Vivekanandarajah <kuganv@linaro.org> > > * gcc.dg/tree-ssa/vrp92.c: Update scanned pattern. > > -- Richard Biener <rguenther@suse.de> SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Jennifer Guild, Dilip Upmanyu, Graham Norton HRB 21284 (AG Nuernberg) ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 2/3] Propagate and save value ranges wrapped information 2015-01-19 12:52 ` Richard Biener @ 2015-04-22 22:11 ` Kugan 2015-04-30 11:44 ` Richard Biener 0 siblings, 1 reply; 14+ messages in thread From: Kugan @ 2015-04-22 22:11 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches, Jakub Jelinek, Jeff Law [-- Attachment #1: Type: text/plain, Size: 5598 bytes --] On 19/01/15 22:28, Richard Biener wrote: > On Sat, 17 Jan 2015, Kugan wrote: > >> >> This patch propagate value range wrapps attribute and save this to >> SSA_NAME. > > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > index 9b7695d..832c35d 100644 > --- a/gcc/tree-vrp.c > +++ b/gcc/tree-vrp.c > @@ -103,6 +103,9 @@ struct value_range_d > tree min; > tree max; > > + /* Set to true if values in this value range could wrapp. */ > + bool is_wrapped; > + > /* Set of SSA names whose value ranges are equivalent to this one. > This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ > bitmap equiv; > > I can't make sense of this description (wrap with one p as well). > I assume you mean that the expression that has this value-range > assigned has an operation that may have wrapped? (a value > can't wrap) > > You need to specify how is_wrapped behaves for range union and > intersect operations and which operations can wrap. > > I miss an overall description of these patches as to a) why you > need this information and b) why it helps. > > It's now also too late and thus you have plenty of time until stage1 > starts again. Thanks Richard for the comments. Now that stage1 is open, here is the modified patch with the changes requested. Due to wrapping in the value range computation, there was a regression in aplha-linux (https://gcc.gnu.org/ml/gcc-patches/2014-08/msg02458.html) while using value range infromation to remove zero/sign extensions in rtl expansaion. Hence I had to revert the patch that enabled zero/sign extension. Now I am propgating this wrap_p information to SSA_NAME so that we know, when used in PROMOTE_MODE, the values can have unpredictable bits beyon the type width. I have also updated the comments as below: + /* Set to true if the values in this range might have been wrapped + during the operation that computed it. + + This is mainly used in zero/sign-extension elimination where value ranges + computed are for the type of SSA_NAME and computation is ultimately done + in PROMOTE_MODE. Therefore, the value ranges has to be correct upto + PROMOTE_MODE precision. If the operation can WRAP, higher bits in + PROMOTE_MODE can be unpredictable and cannot be used in zero/sign extension + elimination; additional wrap_p attribute is needed to show this. + + For example: + on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned + variable, + _343 = ivtmp.179_52 + 2147483645; [0x80000004, 0x800000043] + + the value range VRP will compute is: + + _344 = _343 * 2; [0x8, 0x86] + _345 = (integer(kind=4)) _344; [0x8, 0x86] + + In PROMOTE_MODE, there will be garbage above the type width. In places + like this, attribute wrap_p will be true. + + wrap_p in range union operation will be true if either of the value range + has wrap_p set. In intersect operation, true when both the value ranges + have wrap_p set. */ + bool wrap_p; + Thanks, Kugan gcc/testsuite/ChangeLog: 2015-04-22 Kugan Vivekanandarajah <kuganv@linaro.org> * gcc.dg/tree-ssa/vrp92.c: Update scanned pattern. gcc/ChangeLog: 2015-04-22 Kugan Vivekanandarajah <kuganv@linaro.org> * builtins.c (determine_block_size): Use new definition of get_range_info. * gimple-pretty-print.c (dump_ssaname_info): Dump new wrap_p info. * internal-fn.c (get_range_pos_neg): Use new definition of get_range_info. (get_min_precision): Likewise. * tree-ssa-copy.c (fini_copy_prop): Use new definition of duplicate_ssa_range_info. * tree-ssa-pre.c (insert_into_preds_of_block): Likewise. (move_computations_dom_walker::before_dom_children): Likewise. * tree-ssa-phiopt.c (value_replacement): Likewise. * tree-ssa-pre.c (eliminate_dom_walker::before_dom_children): Likewise. * tree-ssa-loop-niter.c (determine_value_range): Use new definition. (record_nonwrapping_iv): Likewise. * tree-ssanames.c (set_range_info): Save wrap_p information. (get_range_info): Retrive wrap_p information. (set_nonzero_bits): Set wrap_p info. (duplicate_ssa_name_range_info): Likewise. (duplicate_ssa_name_fn): Likewise. * tree-ssanames.h: (set_range_info): Update definition. (get_range_info): Likewise. * tree-vect-patterns.c (vect_recog_divmod_pattern): Use new declaration get_range_info. * tree-vrp.c (struct value_range_d): Add wrap_p field. (set_value_range): Calculate and add wrap_p field. (set_and_canonicalize_value_range): Likewise. (copy_value_range): Likewise. (set_value_range_to_value): Likewise. (set_value_range_to_nonnegative): Likewise. (set_value_range_to_nonnull): Likewise. (set_value_range_to_truthvalue): Likewise. (abs_extent_range): Likewise. (get_value_range): Return wrap_p info. (update_value_range): Save wrap_p info. (extract_range_from_assert): Extract and update wrap_p info. (extract_range_from_ssa_name): Likewise. (vrp_int_const_binop): Likewise. (ranges_from_anti_range): Likewise. (extract_range_from_multiplicative_op_1): Likewise. (extract_range_from_binary_expr_1): Likewise. (extract_range_from_binary_expr): Likewise. (extract_range_from_unary_expr_1): Likewise. (extract_range_from_comparison): Likewise. (extract_range_basic): Likewise. (adjust_range_with_scev): Likewise. (dump_value_range): Dump wrap_p info. (remove_range_assertions): Update parameters. (vrp_intersect_ranges_1): Propagate wrap_p info. (vrp_meet_1): Likewise. (vrp_visit_phi_node): Save wrap_p info to SSA. (vrp_finalize): Likewise. * tree.h (SSA_NAME_ANTI_RANGE_P): Remove. (SSA_NAME_RANGE_WRAP_P): New. [-- Attachment #2: patch2.txt --] [-- Type: text/plain, Size: 36977 bytes --] diff --git a/gcc/builtins.c b/gcc/builtins.c index 9263777..02e97f1 100644 --- a/gcc/builtins.c +++ b/gcc/builtins.c @@ -3158,7 +3158,7 @@ determine_block_size (tree len, rtx len_rtx, *probable_max_size = *max_size = GET_MODE_MASK (GET_MODE (len_rtx)); if (TREE_CODE (len) == SSA_NAME) - range_type = get_range_info (len, &min, &max); + range_type = get_range_info (len, &min, &max, NULL); if (range_type == VR_RANGE) { if (wi::fits_uhwi_p (min) && *min_size < min.to_uhwi ()) diff --git a/gcc/gimple-pretty-print.c b/gcc/gimple-pretty-print.c index 2f9671f..0a5c4da 100644 --- a/gcc/gimple-pretty-print.c +++ b/gcc/gimple-pretty-print.c @@ -1847,13 +1847,15 @@ dump_ssaname_info (pretty_printer *buffer, tree node, int spc) && SSA_NAME_RANGE_INFO (node)) { wide_int min, max, nonzero_bits; - value_range_type range_type = get_range_info (node, &min, &max); + bool wrapped; + value_range_type range_type = get_range_info (node, &min, &max, &wrapped); if (range_type == VR_VARYING) pp_printf (buffer, "# RANGE VR_VARYING"); else if (range_type == VR_RANGE || range_type == VR_ANTI_RANGE) { pp_printf (buffer, "# RANGE "); + pp_printf (buffer, "WRAPPED = %s ", wrapped ? "true" : "false"); pp_printf (buffer, "%s[", range_type == VR_RANGE ? "" : "~"); pp_wide_int (buffer, min, TYPE_SIGN (TREE_TYPE (node))); pp_printf (buffer, ", "); diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c index 0053ed9..9b10eaa 100644 --- a/gcc/internal-fn.c +++ b/gcc/internal-fn.c @@ -282,7 +282,7 @@ get_range_pos_neg (tree arg) if (TREE_CODE (arg) != SSA_NAME) return 3; wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + while (get_range_info (arg, &arg_min, &arg_max, NULL) != VR_RANGE) { gimple g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) @@ -364,7 +364,7 @@ get_min_precision (tree arg, signop sign) if (TREE_CODE (arg) != SSA_NAME) return prec + (orig_sign != sign); wide_int arg_min, arg_max; - while (get_range_info (arg, &arg_min, &arg_max) != VR_RANGE) + while (get_range_info (arg, &arg_min, &arg_max, NULL) != VR_RANGE) { gimple g = SSA_NAME_DEF_STMT (arg); if (is_gimple_assign (g) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c index a84ba8e..0c05ead 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp92.c @@ -18,6 +18,6 @@ int foo (int i, int j) return j; } -/* { dg-final { scan-tree-dump "res_.: \\\[1, 1\\\]" "vrp1" } } */ +/* { dg-final { scan-tree-dump "res_.: NOWRAP \\\[1, 1\\\]" "vrp1" } } */ /* { dg-final { scan-tree-dump-not "Threaded" "vrp1" } } */ /* { dg-final { cleanup-tree-dump "vrp1" } } */ diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c index 5ae8e6c..963c5a7 100644 --- a/gcc/tree-ssa-copy.c +++ b/gcc/tree-ssa-copy.c @@ -574,8 +574,8 @@ fini_copy_prop (void) && !SSA_NAME_RANGE_INFO (copy_of[i].value) && var_bb == copy_of_bb) duplicate_ssa_name_range_info (copy_of[i].value, - SSA_NAME_RANGE_TYPE (var), - SSA_NAME_RANGE_INFO (var)); + SSA_NAME_RANGE_INFO (var), + SSA_NAME_RANGE_WRAP_P (var)); } } diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index 11fc699..987add1 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -1245,7 +1245,6 @@ move_computations_dom_walker::before_dom_children (basic_block bb) { tree lhs = gimple_assign_lhs (new_stmt); SSA_NAME_RANGE_INFO (lhs) = NULL; - SSA_NAME_ANTI_RANGE_P (lhs) = 0; } gsi_insert_on_edge (loop_preheader_edge (level), new_stmt); remove_phi_node (&bsi, false); @@ -1315,7 +1314,6 @@ move_computations_dom_walker::before_dom_children (basic_block bb) { tree lhs = gimple_get_lhs (stmt); SSA_NAME_RANGE_INFO (lhs) = NULL; - SSA_NAME_ANTI_RANGE_P (lhs) = 0; } /* In case this is a stmt that is not unconditionally executed when the target loop header is executed and the stmt may diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index fc63825..1a32a8f 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -176,7 +176,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, gphi_iterator gsi; /* Either for VAR itself... */ - rtype = get_range_info (var, &minv, &maxv); + rtype = get_range_info (var, &minv, &maxv, NULL); /* Or for PHI results in loop->header where VAR is used as PHI argument from the loop preheader edge. */ for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) @@ -184,7 +184,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, gphi *phi = gsi.phi (); wide_int minc, maxc; if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var - && (get_range_info (gimple_phi_result (phi), &minc, &maxc) + && (get_range_info (gimple_phi_result (phi), &minc, &maxc, NULL) == VR_RANGE)) { if (rtype != VR_RANGE) @@ -203,7 +203,7 @@ determine_value_range (struct loop *loop, tree type, tree var, mpz_t off, involved. */ if (wi::gt_p (minv, maxv, sgn)) { - rtype = get_range_info (var, &minv, &maxv); + rtype = get_range_info (var, &minv, &maxv, NULL); break; } } @@ -2785,7 +2785,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt, if (TREE_CODE (orig_base) == SSA_NAME && TREE_CODE (high) == INTEGER_CST && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) - && get_range_info (orig_base, &min, &max) == VR_RANGE + && get_range_info (orig_base, &min, &max, NULL) == VR_RANGE && wi::gts_p (high, max)) base = wide_int_to_tree (unsigned_type, max); else if (TREE_CODE (base) != INTEGER_CST) @@ -2800,7 +2800,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt, if (TREE_CODE (orig_base) == SSA_NAME && TREE_CODE (low) == INTEGER_CST && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) - && get_range_info (orig_base, &min, &max) == VR_RANGE + && get_range_info (orig_base, &min, &max, NULL) == VR_RANGE && wi::gts_p (min, low)) base = wide_int_to_tree (unsigned_type, min); else if (TREE_CODE (base) != INTEGER_CST) diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index 7c846c2..b6f4e10 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -911,14 +911,14 @@ value_replacement (basic_block cond_bb, basic_block middle_bb, <bb 4>: # u_3 = PHI <u_6(3), 4294967295(2)> */ SSA_NAME_RANGE_INFO (lhs) = NULL; - SSA_NAME_ANTI_RANGE_P (lhs) = 0; /* If available, we can use VR of phi result at least. */ tree phires = gimple_phi_result (phi); struct range_info_def *phires_range_info = SSA_NAME_RANGE_INFO (phires); if (phires_range_info) - duplicate_ssa_name_range_info (lhs, SSA_NAME_RANGE_TYPE (phires), - phires_range_info); + duplicate_ssa_name_range_info (lhs, + phires_range_info, + SSA_NAME_RANGE_WRAP_P (phires)); } gimple_stmt_iterator gsi_from = gsi_for_stmt (assign); gsi_move_before (&gsi_from, &gsi); diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 67e5351..b5e2e87 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -3200,7 +3200,7 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, && SSA_NAME_RANGE_INFO (expr->u.nary->op[0])) { wide_int min, max; - if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE + if (get_range_info (expr->u.nary->op[0], &min, &max, NULL) == VR_RANGE && !wi::neg_p (min, SIGNED) && !wi::neg_p (max, SIGNED)) /* Just handle extension and sign-changes of all-positive ranges. */ @@ -3208,7 +3208,8 @@ insert_into_preds_of_block (basic_block block, unsigned int exprnum, wide_int_storage::from (min, TYPE_PRECISION (type), TYPE_SIGN (type)), wide_int_storage::from (max, TYPE_PRECISION (type), - TYPE_SIGN (type))); + TYPE_SIGN (type)), + false); } if (dump_file && (dump_flags & TDF_DETAILS)) @@ -4146,8 +4147,8 @@ eliminate_dom_walker::before_dom_children (basic_block b) && !SSA_NAME_RANGE_INFO (sprime) && b == sprime_b) duplicate_ssa_name_range_info (sprime, - SSA_NAME_RANGE_TYPE (lhs), - SSA_NAME_RANGE_INFO (lhs)); + SSA_NAME_RANGE_INFO (lhs), + SSA_NAME_RANGE_WRAP_P (lhs)); } /* Inhibit the use of an inserted PHI on a loop header when diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c index 744dc43..4b0e232 100644 --- a/gcc/tree-ssanames.c +++ b/gcc/tree-ssanames.c @@ -201,7 +201,7 @@ make_ssa_name_fn (struct function *fn, tree var, gimple stmt) void set_range_info (tree name, - const wide_int_ref &min, const wide_int_ref &max) + const wide_int_ref &min, const wide_int_ref &max, bool wrap_p) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); range_info_def *ri = SSA_NAME_RANGE_INFO (name); @@ -221,6 +221,7 @@ set_range_info (tree name, /* Set the values. */ ri->set_min (min); ri->set_max (max); + SSA_NAME_RANGE_WRAP_P (name) = wrap_p; /* If it is a range, try to improve nonzero_bits from the min/max. */ if (wi::cmp (min, max, TYPE_SIGN (TREE_TYPE (name))) < 0) @@ -238,7 +239,7 @@ set_range_info (tree name, is used to determine if MIN and MAX are valid values. */ enum value_range_type -get_range_info (const_tree name, wide_int *min, wide_int *max) +get_range_info (const_tree name, wide_int *min, wide_int *max, bool *wrap_p) { gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (min && max); @@ -266,6 +267,8 @@ get_range_info (const_tree name, wide_int *min, wide_int *max) *min = ri->get_min (); *max = ri->get_max (); } + if (wrap_p) + *wrap_p = SSA_NAME_RANGE_WRAP_P (name); return range_type; } @@ -278,7 +281,8 @@ set_nonzero_bits (tree name, const wide_int_ref &mask) if (SSA_NAME_RANGE_INFO (name) == NULL) set_range_info (name, TYPE_MIN_VALUE (TREE_TYPE (name)), - TYPE_MAX_VALUE (TREE_TYPE (name))); + TYPE_MAX_VALUE (TREE_TYPE (name)), + false); range_info_def *ri = SSA_NAME_RANGE_INFO (name); ri->set_nonzero_bits (mask); } @@ -505,14 +509,13 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) RANGE_TYPE for use by the SSA name NAME. */ void duplicate_ssa_name_range_info (tree name, - enum value_range_type range_type ATTRIBUTE_UNUSED, - struct range_info_def *range_info) + struct range_info_def *range_info, + bool wrap_p) { struct range_info_def *new_range_info; gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); gcc_assert (!SSA_NAME_RANGE_INFO (name)); - gcc_assert (!SSA_NAME_ANTI_RANGE_P (name)); if (!range_info) return; @@ -523,6 +526,7 @@ duplicate_ssa_name_range_info (tree name, new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size)); memcpy (new_range_info, range_info, size); + SSA_NAME_RANGE_WRAP_P (name) = wrap_p; SSA_NAME_RANGE_INFO (name) = new_range_info; } @@ -547,8 +551,9 @@ duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt) struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name); if (old_range_info) - duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name), - old_range_info); + duplicate_ssa_name_range_info (new_name, + old_range_info, + SSA_NAME_RANGE_WRAP_P (name)); } return new_name; diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h index 0d4b212..7bb33db 100644 --- a/gcc/tree-ssanames.h +++ b/gcc/tree-ssanames.h @@ -69,10 +69,10 @@ enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING }; /* Sets the value range to SSA. */ extern void set_range_info (tree, const wide_int_ref &, - const wide_int_ref &); + const wide_int_ref &, bool); /* Gets the value range from SSA. */ extern enum value_range_type get_range_info (const_tree, wide_int *, - wide_int *); + wide_int *, bool *); extern void set_nonzero_bits (tree, const wide_int_ref &); extern wide_int get_nonzero_bits (const_tree); extern void init_ssanames (struct function *, int); @@ -92,8 +92,9 @@ extern struct ptr_info_def *get_ptr_info (tree); extern tree copy_ssa_name_fn (struct function *, tree, gimple); extern void duplicate_ssa_name_ptr_info (tree, struct ptr_info_def *); extern tree duplicate_ssa_name_fn (struct function *, tree, gimple); -extern void duplicate_ssa_name_range_info (tree, enum value_range_type, - struct range_info_def *); +extern void duplicate_ssa_name_range_info (tree, + struct range_info_def *, + bool); extern void release_defs (gimple); extern void replace_ssa_name_symbol (tree, tree); diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c index 86d2447..fc22f53 100644 --- a/gcc/tree-vect-patterns.c +++ b/gcc/tree-vect-patterns.c @@ -2563,7 +2563,7 @@ vect_recog_divmod_pattern (vec<gimple> *stmts, wide_int oprnd0_min, oprnd0_max; int msb = 1; - if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE) + if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max, NULL) == VR_RANGE) { if (!wi::neg_p (oprnd0_min, TYPE_SIGN (itype))) msb = 0; diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index d823be9..a988aaf 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -114,6 +114,34 @@ struct value_range_d tree min; tree max; + /* Set to true if the values in this range might have been wrapped + during the operation that computed it. + + This is mainly used in zero/sign-extension elimination where value ranges + computed are for the type of SSA_NAME and computation is ultimately done + in PROMOTE_MODE. Therefore, the value ranges has to be correct upto + PROMOTE_MODE precision. If the operation can WRAP, higher bits in + PROMOTE_MODE can be unpredictable and cannot be used in zero/sign extension + elimination; additional wrap_p attribute is needed to show this. + + For example: + on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned + variable, + _343 = ivtmp.179_52 + 2147483645; [0x80000004, 0x800000043] + + the value range VRP will compute is: + + _344 = _343 * 2; [0x8, 0x86] + _345 = (integer(kind=4)) _344; [0x8, 0x86] + + In PROMOTE_MODE, there will be garbage above the type width. In places + like this, attribute wrap_p will be true. + + wrap_p in range union operation will be true if either of the value range + has wrap_p set. In intersect operation, true when both the value ranges + have wrap_p set. */ + bool wrap_p; + /* Set of SSA names whose value ranges are equivalent to this one. This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ bitmap equiv; @@ -121,7 +149,7 @@ struct value_range_d typedef struct value_range_d value_range_t; -#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } +#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, false, NULL } /* Set of SSA names found live during the RPO traversal of the function for still active basic-blocks. */ @@ -469,7 +497,7 @@ set_value_range_to_varying (value_range_t *vr) static void set_value_range (value_range_t *vr, enum value_range_type t, tree min, - tree max, bitmap equiv) + tree max, bool wrap_p, bitmap equiv) { #if defined ENABLE_CHECKING /* Check the validity of the range. */ @@ -503,6 +531,7 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, vr->type = t; vr->min = min; vr->max = max; + vr->wrap_p = wrap_p; /* Since updating the equivalence set involves deep copying the bitmaps, only do it if absolutely necessary. */ @@ -531,7 +560,7 @@ set_value_range (value_range_t *vr, enum value_range_type t, tree min, static void set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, - tree min, tree max, bitmap equiv) + tree min, tree max, bool wrap_p, bitmap equiv) { /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ if (t == VR_UNDEFINED) @@ -549,7 +578,7 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, if (TREE_CODE (min) != INTEGER_CST || TREE_CODE (max) != INTEGER_CST) { - set_value_range (vr, t, min, max, equiv); + set_value_range (vr, t, min, max, wrap_p, equiv); return; } @@ -637,7 +666,7 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, return; } - set_value_range (vr, t, min, max, equiv); + set_value_range (vr, t, min, max, wrap_p, equiv); } /* Copy value range FROM into value range TO. */ @@ -645,7 +674,8 @@ set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t, static inline void copy_value_range (value_range_t *to, value_range_t *from) { - set_value_range (to, from->type, from->min, from->max, from->equiv); + set_value_range (to, from->type, from->min, from->max, + from->wrap_p, from->equiv); } /* Set value range VR to a single value. This function is only called @@ -659,7 +689,7 @@ set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv) gcc_assert (is_gimple_min_invariant (val)); if (TREE_OVERFLOW_P (val)) val = drop_tree_overflow (val); - set_value_range (vr, VR_RANGE, val, val, equiv); + set_value_range (vr, VR_RANGE, val, val, false, equiv); } /* Set value range VR to a non-negative range of type TYPE. @@ -685,6 +715,7 @@ set_value_range_to_nonnegative (value_range_t *vr, tree type, (overflow_infinity ? positive_overflow_infinity (type) : TYPE_MAX_VALUE (type)), + false, vr->equiv); } @@ -694,7 +725,7 @@ static inline void set_value_range_to_nonnull (value_range_t *vr, tree type) { tree zero = build_int_cst (type, 0); - set_value_range (vr, VR_ANTI_RANGE, zero, zero, vr->equiv); + set_value_range (vr, VR_ANTI_RANGE, zero, zero, false, vr->equiv); } @@ -717,6 +748,7 @@ set_value_range_to_truthvalue (value_range_t *vr, tree type) else set_value_range (vr, VR_RANGE, build_int_cst (type, 0), build_int_cst (type, 1), + false, vr->equiv); } @@ -753,7 +785,7 @@ abs_extent_range (value_range_t *vr, tree min, tree max) set_value_range_to_varying (vr); return; } - set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); + set_and_canonicalize_value_range (vr, VR_RANGE, min, max, false, NULL); } @@ -766,7 +798,7 @@ static value_range_t * get_value_range (const_tree var) { static const struct value_range_d vr_const_varying - = { VR_VARYING, NULL_TREE, NULL_TREE, NULL }; + = { VR_VARYING, NULL_TREE, NULL_TREE, false, NULL }; value_range_t *vr; tree sym; unsigned ver = SSA_NAME_VERSION (var); @@ -864,13 +896,15 @@ update_value_range (const_tree var, value_range_t *new_vr) if (INTEGRAL_TYPE_P (TREE_TYPE (var))) { wide_int min, max; - value_range_type rtype = get_range_info (var, &min, &max); + bool wrap_p = false; + value_range_type rtype = get_range_info (var, &min, &max, &wrap_p); if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE) { value_range_d nr; nr.type = rtype; nr.min = wide_int_to_tree (TREE_TYPE (var), min); nr.max = wide_int_to_tree (TREE_TYPE (var), max); + nr.wrap_p = wrap_p; nr.equiv = NULL; vrp_intersect_ranges (new_vr, &nr); } @@ -895,6 +929,7 @@ update_value_range (const_tree var, value_range_t *new_vr) set_value_range_to_varying (old_vr); else set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max, + new_vr->wrap_p, new_vr->equiv); } @@ -1788,10 +1823,10 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) this for us. */ if (cond_code == LE_EXPR) set_and_canonicalize_value_range (vr_p, VR_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); else if (cond_code == GT_EXPR) set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); else gcc_unreachable (); } @@ -1812,7 +1847,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) max = limit; } - set_value_range (vr_p, range_type, min, max, vr_p->equiv); + set_value_range (vr_p, range_type, min, max, false, vr_p->equiv); /* When asserting the equality VAR == LIMIT and LIMIT is another SSA name, the new range will also inherit the equivalence set @@ -1864,7 +1899,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) min = max = limit; set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE, - min, max, vr_p->equiv); + min, max, false, vr_p->equiv); } else if (cond_code == LE_EXPR || cond_code == LT_EXPR) { @@ -1903,7 +1938,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) TREE_NO_WARNING (max) = 1; } - set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); + set_value_range (vr_p, VR_RANGE, min, max, false, vr_p->equiv); } } else if (cond_code == GE_EXPR || cond_code == GT_EXPR) @@ -1943,7 +1978,7 @@ extract_range_from_assert (value_range_t *vr_p, tree expr) TREE_NO_WARNING (min) = 1; } - set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv); + set_value_range (vr_p, VR_RANGE, min, max, false, vr_p->equiv); } } else @@ -1975,12 +2010,11 @@ extract_range_from_ssa_name (value_range_t *vr, tree var) if (var_vr->type != VR_VARYING) copy_value_range (vr, var_vr); else - set_value_range (vr, VR_RANGE, var, var, NULL); + set_value_range (vr, VR_RANGE, var, var, false, NULL); add_equivalence (&vr->equiv, var); } - /* Wrapper around int_const_binop. If the operation overflows and we are not using wrapping arithmetic, then adjust the result to be -INF or +INF depending on CODE, VAL1 and VAL2. This can return @@ -1988,11 +2022,13 @@ extract_range_from_ssa_name (value_range_t *vr, tree var) the type does not support it. */ static tree -vrp_int_const_binop (enum tree_code code, tree val1, tree val2) +vrp_int_const_binop (enum tree_code code, tree val1, tree val2, bool *wrap_p) { tree res; res = int_const_binop (code, val1, val2); + if (wrap_p) + *wrap_p = false; /* If we are using unsigned arithmetic, operate symbolically on -INF and +INF as int_const_binop only handles signed overflow. */ @@ -2036,7 +2072,10 @@ vrp_int_const_binop (enum tree_code code, tree val1, tree val2) else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1))) /* If the singed operation wraps then int_const_binop has done everything we want. */ - ; + { + if (wrap_p) + *wrap_p = true; + } /* Signed division of -1/0 overflows and by the time it gets here returns NULL_TREE. */ else if (!res) @@ -2200,12 +2239,14 @@ ranges_from_anti_range (value_range_t *ar, vr0->type = VR_RANGE; vr0->min = vrp_val_min (type); vr0->max = wide_int_to_tree (type, wi::sub (ar->min, 1)); + vr0->wrap_p = ar->wrap_p; } if (!vrp_val_is_max (ar->max)) { vr1->type = VR_RANGE; vr1->min = wide_int_to_tree (type, wi::add (ar->max, 1)); vr1->max = vrp_val_max (type); + vr1->wrap_p = ar->wrap_p; } if (vr0->type == VR_UNDEFINED) { @@ -2230,6 +2271,8 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, tree min, max; bool sop; int cmp; + bool wrap_p = false; + bool t_wrap_p = false; /* Multiplications, divisions and shifts are a bit tricky to handle, depending on the mix of signs we have in the two ranges, we @@ -2259,35 +2302,43 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, /* Compute the 4 cross operations. */ sop = false; - val[0] = vrp_int_const_binop (code, vr0->min, vr1->min); + val[0] = vrp_int_const_binop (code, vr0->min, vr1->min, &t_wrap_p); if (val[0] == NULL_TREE) sop = true; + if (t_wrap_p) + wrap_p = true; if (vr1->max == vr1->min) val[1] = NULL_TREE; else { - val[1] = vrp_int_const_binop (code, vr0->min, vr1->max); + val[1] = vrp_int_const_binop (code, vr0->min, vr1->max, &t_wrap_p); if (val[1] == NULL_TREE) sop = true; + if (t_wrap_p) + wrap_p = true; } if (vr0->max == vr0->min) val[2] = NULL_TREE; else { - val[2] = vrp_int_const_binop (code, vr0->max, vr1->min); + val[2] = vrp_int_const_binop (code, vr0->max, vr1->min, &t_wrap_p); if (val[2] == NULL_TREE) sop = true; + if (t_wrap_p) + wrap_p = true; } if (vr0->min == vr0->max || vr1->min == vr1->max) val[3] = NULL_TREE; else { - val[3] = vrp_int_const_binop (code, vr0->max, vr1->max); + val[3] = vrp_int_const_binop (code, vr0->max, vr1->max, &t_wrap_p); if (val[3] == NULL_TREE) sop = true; + if (t_wrap_p) + wrap_p = true; } if (sop) @@ -2367,7 +2418,7 @@ extract_range_from_multiplicative_op_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, type, min, max, NULL); + set_value_range (vr, type, min, max, wrap_p, NULL); } /* Extract range information from a binary operation CODE based on @@ -2384,6 +2435,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, enum value_range_type type; tree min = NULL_TREE, max = NULL_TREE; int cmp; + bool vr_wrap_p = false; if (!INTEGRAL_TYPE_P (expr_type) && !POINTER_TYPE_P (expr_type)) @@ -2683,6 +2735,13 @@ extract_range_from_binary_expr_1 (value_range_t *vr, range kind and bounds appropriately. */ wide_int tmin = wide_int::from (wmin, prec, sgn); wide_int tmax = wide_int::from (wmax, prec, sgn); + + if (wi::cmp (wmin, type_min, sgn) == -1 + || wi::cmp (wmin, type_max, sgn) == 1 + || wi::cmp (wmax, type_min, sgn) == -1 + || wi::cmp (wmax, type_max, sgn) == 1) + vr_wrap_p = true; + if (min_ovf == max_ovf) { /* No overflow or both overflow or underflow. The @@ -2835,8 +2894,8 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* For operations that make the resulting range directly proportional to the original ranges, apply the operation to the same end of each range. */ - min = vrp_int_const_binop (code, vr0.min, vr1.min); - max = vrp_int_const_binop (code, vr0.max, vr1.max); + min = vrp_int_const_binop (code, vr0.min, vr1.min, NULL); + max = vrp_int_const_binop (code, vr0.max, vr1.max, NULL); } else if (code == MIN_EXPR) { @@ -2960,9 +3019,10 @@ extract_range_from_binary_expr_1 (value_range_t *vr, /* The following should handle the wrapping and selecting VR_ANTI_RANGE for us. */ + vr_wrap_p = true; min = wide_int_to_tree (expr_type, prod0); max = wide_int_to_tree (expr_type, prod3); - set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); + set_and_canonicalize_value_range (vr, VR_RANGE, min, max, vr_wrap_p, NULL); return; } @@ -3330,7 +3390,7 @@ extract_range_from_binary_expr_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, type, min, max, NULL); + set_value_range (vr, type, min, max, vr_wrap_p, NULL); } /* Extract range information from a binary expression OP0 CODE OP1 based on @@ -3379,15 +3439,15 @@ extract_range_from_binary_expr (value_range_t *vr, /* Try with VR0 and [-INF, OP1]. */ if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min)) - set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); + set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, false, NULL); /* Try with VR0 and [OP1, +INF]. */ else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max)) - set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); + set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), false, NULL); /* Try with VR0 and [OP1, OP1]. */ else - set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL); + set_value_range (&n_vr1, VR_RANGE, op1, op1, false, NULL); extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1); } @@ -3403,15 +3463,15 @@ extract_range_from_binary_expr (value_range_t *vr, /* Try with [-INF, OP0] and VR1. */ if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min)) - set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL); + set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, false, NULL); /* Try with [OP0, +INF] and VR1. */ else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max)) - set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL); + set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), false, NULL); /* Try with [OP0, OP0] and VR1. */ else - set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL); + set_value_range (&n_vr0, VR_RANGE, op0, op0, false, NULL); extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1); } @@ -3544,18 +3604,27 @@ extract_range_from_unary_expr_1 (value_range_t *vr, size_int (TYPE_PRECISION (outer_type))))))) { tree new_min, new_max; + bool wrap_p = vr0.wrap_p; if (is_overflow_infinity (vr0.min)) new_min = negative_overflow_infinity (outer_type); else - new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), - 0, false); + { + if (!int_fits_type_p (vr0.max, outer_type)) + wrap_p = true; + new_min = force_fit_type (outer_type, wi::to_widest (vr0.min), + 0, false); + } if (is_overflow_infinity (vr0.max)) new_max = positive_overflow_infinity (outer_type); else - new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), - 0, false); + { + if (!int_fits_type_p (vr0.max, outer_type)) + wrap_p = true; + new_max = force_fit_type (outer_type, wi::to_widest (vr0.max), + 0, false); + } set_and_canonicalize_value_range (vr, vr0.type, - new_min, new_max, NULL); + new_min, new_max, wrap_p, NULL); return; } @@ -3712,7 +3781,7 @@ extract_range_from_unary_expr_1 (value_range_t *vr, set_value_range_to_varying (vr); } else - set_value_range (vr, vr0.type, min, max, NULL); + set_value_range (vr, vr0.type, min, max, false, NULL); return; } @@ -3806,7 +3875,7 @@ extract_range_from_comparison (value_range_t *vr, enum tree_code code, if (is_gimple_min_invariant (val)) set_value_range_to_value (vr, val, vr->equiv); else - set_value_range (vr, VR_RANGE, val, val, vr->equiv); + set_value_range (vr, VR_RANGE, val, val, false, vr->equiv); } else /* The result of a comparison is always true or false. */ @@ -4103,7 +4172,7 @@ extract_range_basic (value_range_t *vr, gimple stmt) goto bitop_builtin; bitop_builtin: set_value_range (vr, VR_RANGE, build_int_cst (type, mini), - build_int_cst (type, maxi), NULL); + build_int_cst (type, maxi), false, NULL); return; default: break; @@ -4193,7 +4262,7 @@ extract_range_basic (value_range_t *vr, gimple stmt) NULL); else set_value_range (vr, VR_RANGE, build_int_cst (type, 0), - build_int_cst (type, 1), NULL); + build_int_cst (type, 1), false, NULL); } else if (types_compatible_p (type, TREE_TYPE (op0)) && types_compatible_p (type, TREE_TYPE (op1))) @@ -4287,6 +4356,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, { tree init, step, chrec, tmin, tmax, min, max, type, tem; enum ev_direction dir; + bool t_wrap_p = false, wrap_p = false; /* TODO. Don't adjust anti-ranges. An anti-range may provide better opportunities than a regular range, but I'm not sure. */ @@ -4382,6 +4452,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, /* Likewise if the addition did. */ if (maxvr.type == VR_RANGE) { + t_wrap_p = maxvr.wrap_p; tmin = maxvr.min; tmax = maxvr.max; } @@ -4393,6 +4464,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, { min = tmin; max = tmax; + wrap_p = t_wrap_p; /* For VARYING or UNDEFINED ranges, just about anything we get from scalar evolutions should be better. */ @@ -4446,7 +4518,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, && is_positive_overflow_infinity (max))) return; - set_value_range (vr, VR_RANGE, min, max, vr->equiv); + set_value_range (vr, VR_RANGE, min, max, wrap_p, vr->equiv); } @@ -4765,7 +4837,8 @@ dump_value_range (FILE *file, value_range_t *vr) { tree type = TREE_TYPE (vr->min); - fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : ""); + fprintf (file, "%s %s[", vr->wrap_p ? "WRAP" : "NOWRAP", + (vr->type == VR_ANTI_RANGE) ? "~" : ""); if (is_negative_overflow_infinity (vr->min)) fprintf (file, "-INF(OVF)"); @@ -6936,7 +7009,8 @@ remove_range_assertions (void) { set_range_info (var, SSA_NAME_RANGE_INFO (lhs)->get_min (), - SSA_NAME_RANGE_INFO (lhs)->get_max ()); + SSA_NAME_RANGE_INFO (lhs)->get_max (), + SSA_NAME_RANGE_WRAP_P (lhs)); maybe_set_nonzero_bits (bb, var); } } @@ -8604,7 +8678,9 @@ vrp_intersect_ranges_1 (value_range_t *vr0, value_range_t *vr1) /* Make sure to canonicalize the result though as the inversion of a VR_RANGE can still be a VR_RANGE. */ set_and_canonicalize_value_range (vr0, vr0->type, - vr0->min, vr0->max, vr0->equiv); + vr0->min, vr0->max, + vr0->wrap_p && vr1->wrap_p, + vr0->equiv); /* If that failed, use the saved original VR0. */ if (vr0->type == VR_VARYING) { @@ -8655,7 +8731,8 @@ vrp_meet_1 (value_range_t *vr0, value_range_t *vr1) if (vr0->type == VR_UNDEFINED) { - set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv); + set_value_range (vr0, vr1->type, vr1->min, vr1->max, + vr1->wrap_p, vr1->equiv); return; } @@ -8709,6 +8786,7 @@ vrp_meet_1 (value_range_t *vr0, value_range_t *vr1) return; } set_and_canonicalize_value_range (vr0, vr0->type, vr0->min, vr0->max, + vr0->wrap_p || vr1->wrap_p, vr0->equiv); if (vr0->type == VR_VARYING) return; @@ -8812,6 +8890,7 @@ vrp_visit_phi_node (gphi *phi) vr_arg.type = VR_RANGE; vr_arg.min = arg; vr_arg.max = arg; + vr_arg.wrap_p = false; vr_arg.equiv = NULL; } } @@ -8824,6 +8903,7 @@ vrp_visit_phi_node (gphi *phi) vr_arg.type = VR_RANGE; vr_arg.min = arg; vr_arg.max = arg; + vr_arg.wrap_p = false; vr_arg.equiv = NULL; } @@ -10264,7 +10344,9 @@ vrp_finalize (void) || vr_value[i]->type == VR_ANTI_RANGE)) { if (vr_value[i]->type == VR_RANGE) - set_range_info (name, vr_value[i]->min, vr_value[i]->max); + set_range_info (name, vr_value[i]->min, + vr_value[i]->max, + vr_value[i]->wrap_p); else if (vr_value[i]->type == VR_ANTI_RANGE) { /* VR_ANTI_RANGE @@ -10279,11 +10361,13 @@ vrp_finalize (void) /* ~[0,0] anti-range is represented as range. */ set_range_info (name, build_int_cst (TREE_TYPE (name), 1), - TYPE_MAXVAL (TREE_TYPE (name))); + TYPE_MAXVAL (TREE_TYPE (name)), + vr_value[i]->wrap_p); else set_range_info (name, wi::add (vr_value[i]->max, 1), - wi::sub (vr_value[i]->min, 1)); + wi::sub (vr_value[i]->min, 1), + vr_value[i]->wrap_p); } } diff --git a/gcc/tree.h b/gcc/tree.h index bedf103..cc147bb 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -1542,14 +1542,11 @@ extern void protected_set_expr_location (tree, location_t); #define SSA_NAME_PTR_INFO(N) \ SSA_NAME_CHECK (N)->ssa_name.info.ptr_info -/* True if SSA_NAME_RANGE_INFO describes an anti-range. */ -#define SSA_NAME_ANTI_RANGE_P(N) \ +/* True if SSA_NAME_RANGE_INFO may have wrapped during the operation that + calculated it. */ +#define SSA_NAME_RANGE_WRAP_P(N) \ SSA_NAME_CHECK (N)->base.static_flag -/* The type of range described by SSA_NAME_RANGE_INFO. */ -#define SSA_NAME_RANGE_TYPE(N) \ - (SSA_NAME_ANTI_RANGE_P (N) ? VR_ANTI_RANGE : VR_RANGE) - /* Value range info attributes for SSA_NAMEs of non pointer-type variables. */ #define SSA_NAME_RANGE_INFO(N) \ SSA_NAME_CHECK (N)->ssa_name.info.range_info ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 2/3] Propagate and save value ranges wrapped information 2015-04-22 22:11 ` Kugan @ 2015-04-30 11:44 ` Richard Biener 2015-04-30 11:53 ` Jakub Jelinek 2015-05-01 4:55 ` Kugan 0 siblings, 2 replies; 14+ messages in thread From: Richard Biener @ 2015-04-30 11:44 UTC (permalink / raw) To: Kugan; +Cc: Richard Biener, gcc-patches, Jakub Jelinek, Jeff Law On Thu, Apr 23, 2015 at 12:11 AM, Kugan <kugan.vivekanandarajah@linaro.org> wrote: > > On 19/01/15 22:28, Richard Biener wrote: >> On Sat, 17 Jan 2015, Kugan wrote: >> >>> >>> This patch propagate value range wrapps attribute and save this to >>> SSA_NAME. >> >> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c >> index 9b7695d..832c35d 100644 >> --- a/gcc/tree-vrp.c >> +++ b/gcc/tree-vrp.c >> @@ -103,6 +103,9 @@ struct value_range_d >> tree min; >> tree max; >> >> + /* Set to true if values in this value range could wrapp. */ >> + bool is_wrapped; >> + >> /* Set of SSA names whose value ranges are equivalent to this one. >> This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ >> bitmap equiv; >> >> I can't make sense of this description (wrap with one p as well). >> I assume you mean that the expression that has this value-range >> assigned has an operation that may have wrapped? (a value >> can't wrap) >> >> You need to specify how is_wrapped behaves for range union and >> intersect operations and which operations can wrap. >> >> I miss an overall description of these patches as to a) why you >> need this information and b) why it helps. >> >> It's now also too late and thus you have plenty of time until stage1 >> starts again. > > > Thanks Richard for the comments. Now that stage1 is open, here is the > modified patch with the changes requested. > > Due to wrapping in the value range computation, there was a regression > in aplha-linux > (https://gcc.gnu.org/ml/gcc-patches/2014-08/msg02458.html) while using > value range infromation to remove zero/sign extensions in rtl > expansaion. Hence I had to revert the patch that enabled zero/sign > extension. Now I am propgating this wrap_p information to SSA_NAME so > that we know, when used in PROMOTE_MODE, the values can have > unpredictable bits beyon the type width. > > I have also updated the comments as below: > > > + /* Set to true if the values in this range might have been wrapped > + during the operation that computed it. > + > + This is mainly used in zero/sign-extension elimination where value > ranges > + computed are for the type of SSA_NAME and computation is > ultimately done > + in PROMOTE_MODE. Therefore, the value ranges has to be correct upto > + PROMOTE_MODE precision. If the operation can WRAP, higher bits in > + PROMOTE_MODE can be unpredictable and cannot be used in zero/sign > extension > + elimination; additional wrap_p attribute is needed to show this. > + > + For example: > + on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned > + variable, > + _343 = ivtmp.179_52 + 2147483645; [0x80000004, 0x800000043] > + > + the value range VRP will compute is: > + > + _344 = _343 * 2; [0x8, 0x86] > + _345 = (integer(kind=4)) _344; [0x8, 0x86] > + > + In PROMOTE_MODE, there will be garbage above the type width. In > places > + like this, attribute wrap_p will be true. > + > + wrap_p in range union operation will be true if either of the > value range > + has wrap_p set. In intersect operation, true when both the value > ranges > + have wrap_p set. */ > + bool wrap_p; > + So what you'd like to know is whether the value range is the same if all operations were carried out in infinite precision (well, in PROMOTE_MODE precision). I'm not sure you can simply assert that we didn't wrap for example in extract_range_from_assert. Consider your above code and if (_344 < 0x87) { _346 = ASSERT_EXPR <_344, _344 < 0x87>; ... _346 definitely should have wrap_p set. That said, I'm not convinced this is a sustainable approach to the issue. I've long pondered with replacing the VRP overflow checking code (for -fstrict-overflow) with keeping two lattices - one honoring undefined overflow and one not and then comparing the results in the end. A similar approach could be used for your wrap_p flag. BUT ... a way more sensible approach to reduce the required sign/zero extensions for PROMOTE_MODE targets is to lower the IL earlier, before we perform the 2nd VRP run and thus have the sign-/zero-extensions being eliminated by GIMPLE optimizers rather than only at RTL time. ISTR you (or somebody else) played with that a bit? Thanks, Richard. > Thanks, > Kugan > > > gcc/testsuite/ChangeLog: > > 2015-04-22 Kugan Vivekanandarajah <kuganv@linaro.org> > > * gcc.dg/tree-ssa/vrp92.c: Update scanned pattern. > > gcc/ChangeLog: > > 2015-04-22 Kugan Vivekanandarajah <kuganv@linaro.org> > > * builtins.c (determine_block_size): Use new definition of > get_range_info. > * gimple-pretty-print.c (dump_ssaname_info): Dump new wrap_p info. > * internal-fn.c (get_range_pos_neg): Use new definition of > get_range_info. > (get_min_precision): Likewise. > * tree-ssa-copy.c (fini_copy_prop): Use new definition of > duplicate_ssa_range_info. > * tree-ssa-pre.c (insert_into_preds_of_block): Likewise. > (move_computations_dom_walker::before_dom_children): Likewise. > * tree-ssa-phiopt.c (value_replacement): Likewise. > * tree-ssa-pre.c (eliminate_dom_walker::before_dom_children): > Likewise. > * tree-ssa-loop-niter.c (determine_value_range): Use new definition. > (record_nonwrapping_iv): Likewise. > * tree-ssanames.c (set_range_info): Save wrap_p information. > (get_range_info): Retrive wrap_p information. > (set_nonzero_bits): Set wrap_p info. > (duplicate_ssa_name_range_info): Likewise. > (duplicate_ssa_name_fn): Likewise. > * tree-ssanames.h: (set_range_info): Update definition. > (get_range_info): Likewise. > * tree-vect-patterns.c (vect_recog_divmod_pattern): Use new > declaration get_range_info. > * tree-vrp.c (struct value_range_d): Add wrap_p field. > (set_value_range): Calculate and add wrap_p field. > (set_and_canonicalize_value_range): Likewise. > (copy_value_range): Likewise. > (set_value_range_to_value): Likewise. > (set_value_range_to_nonnegative): Likewise. > (set_value_range_to_nonnull): Likewise. > (set_value_range_to_truthvalue): Likewise. > (abs_extent_range): Likewise. > (get_value_range): Return wrap_p info. > (update_value_range): Save wrap_p info. > (extract_range_from_assert): Extract and update wrap_p info. > (extract_range_from_ssa_name): Likewise. > (vrp_int_const_binop): Likewise. > (ranges_from_anti_range): Likewise. > (extract_range_from_multiplicative_op_1): Likewise. > (extract_range_from_binary_expr_1): Likewise. > (extract_range_from_binary_expr): Likewise. > (extract_range_from_unary_expr_1): Likewise. > (extract_range_from_comparison): Likewise. > (extract_range_basic): Likewise. > (adjust_range_with_scev): Likewise. > (dump_value_range): Dump wrap_p info. > (remove_range_assertions): Update parameters. > (vrp_intersect_ranges_1): Propagate wrap_p info. > (vrp_meet_1): Likewise. > (vrp_visit_phi_node): Save wrap_p info to SSA. > (vrp_finalize): Likewise. > * tree.h (SSA_NAME_ANTI_RANGE_P): Remove. > (SSA_NAME_RANGE_WRAP_P): New. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 2/3] Propagate and save value ranges wrapped information 2015-04-30 11:44 ` Richard Biener @ 2015-04-30 11:53 ` Jakub Jelinek 2015-04-30 12:13 ` Richard Biener 2015-05-01 4:55 ` Kugan 1 sibling, 1 reply; 14+ messages in thread From: Jakub Jelinek @ 2015-04-30 11:53 UTC (permalink / raw) To: Richard Biener; +Cc: Kugan, Richard Biener, gcc-patches, Jeff Law On Thu, Apr 30, 2015 at 01:35:25PM +0200, Richard Biener wrote: > I've long pondered with replacing the VRP overflow checking code > (for -fstrict-overflow) with keeping two lattices - one honoring undefined > overflow and one not and then comparing the results in the end. Yeah, that would be greatly appreciated. The (OVF) stuff is complete mess. Jakub ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 2/3] Propagate and save value ranges wrapped information 2015-04-30 11:53 ` Jakub Jelinek @ 2015-04-30 12:13 ` Richard Biener 0 siblings, 0 replies; 14+ messages in thread From: Richard Biener @ 2015-04-30 12:13 UTC (permalink / raw) To: Jakub Jelinek; +Cc: Richard Biener, Kugan, gcc-patches, Jeff Law On Thu, 30 Apr 2015, Jakub Jelinek wrote: > On Thu, Apr 30, 2015 at 01:35:25PM +0200, Richard Biener wrote: > > I've long pondered with replacing the VRP overflow checking code > > (for -fstrict-overflow) with keeping two lattices - one honoring undefined > > overflow and one not and then comparing the results in the end. > > Yeah, that would be greatly appreciated. The (OVF) stuff is complete mess. Just to explain a little bit, the idea is to have two lattices and run the VRP propagation stage on each one, once with flag_wrapv forced to 1 (all conditional on -Wstrict-overflow of course). At stmt simplifiation time then determine if the outcome is dependent on the choice of the lattice and if so, emit a strict-overflow warning. This will avoid the missed optimizations we currently have due to the (OVF) stuff. And it will simplify the code and make it easier to maintain. As for doing sth similar for PROMOTE_MODE you'd have to replace all SSA names TREE_TYPE (and hope VRP doesn't explode on inconsistencies). I don't think thats going to fly well though. Instead you could "lower" at VRP instrumentation time, inserting sign-/zero-extensions and remove those not necessary at VRPs final stage. Of course that would tie lowering to VRP which probably we don't want to do. I've meanwhile found the prototype lowering pass and as I've commented on that patch you need to add at least a sign-extension tree operator for efficiency (otherwise you need two stmts and an intermediate non-promoted type). zero-extension can be done via a BIT_AND_EXPR (not 100% nice, but we avoid having two ways to compute sth which speaks against having an explicit zero-extension operator). Richard. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 2/3] Propagate and save value ranges wrapped information 2015-04-30 11:44 ` Richard Biener 2015-04-30 11:53 ` Jakub Jelinek @ 2015-05-01 4:55 ` Kugan 1 sibling, 0 replies; 14+ messages in thread From: Kugan @ 2015-05-01 4:55 UTC (permalink / raw) To: Richard Biener; +Cc: Richard Biener, gcc-patches, Jakub Jelinek, Jeff Law On 30/04/15 21:35, Richard Biener wrote: > On Thu, Apr 23, 2015 at 12:11 AM, Kugan > <kugan.vivekanandarajah@linaro.org> wrote: >> >> On 19/01/15 22:28, Richard Biener wrote: >>> On Sat, 17 Jan 2015, Kugan wrote: >>> >>>> >>>> This patch propagate value range wrapps attribute and save this to >>>> SSA_NAME. >>> >>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c >>> index 9b7695d..832c35d 100644 >>> --- a/gcc/tree-vrp.c >>> +++ b/gcc/tree-vrp.c >>> @@ -103,6 +103,9 @@ struct value_range_d >>> tree min; >>> tree max; >>> >>> + /* Set to true if values in this value range could wrapp. */ >>> + bool is_wrapped; >>> + >>> /* Set of SSA names whose value ranges are equivalent to this one. >>> This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */ >>> bitmap equiv; >>> >>> I can't make sense of this description (wrap with one p as well). >>> I assume you mean that the expression that has this value-range >>> assigned has an operation that may have wrapped? (a value >>> can't wrap) >>> >>> You need to specify how is_wrapped behaves for range union and >>> intersect operations and which operations can wrap. >>> >>> I miss an overall description of these patches as to a) why you >>> need this information and b) why it helps. >>> >>> It's now also too late and thus you have plenty of time until stage1 >>> starts again. >> >> >> Thanks Richard for the comments. Now that stage1 is open, here is the >> modified patch with the changes requested. >> >> Due to wrapping in the value range computation, there was a regression >> in aplha-linux >> (https://gcc.gnu.org/ml/gcc-patches/2014-08/msg02458.html) while using >> value range infromation to remove zero/sign extensions in rtl >> expansaion. Hence I had to revert the patch that enabled zero/sign >> extension. Now I am propgating this wrap_p information to SSA_NAME so >> that we know, when used in PROMOTE_MODE, the values can have >> unpredictable bits beyon the type width. >> >> I have also updated the comments as below: >> >> >> + /* Set to true if the values in this range might have been wrapped >> + during the operation that computed it. >> + >> + This is mainly used in zero/sign-extension elimination where value >> ranges >> + computed are for the type of SSA_NAME and computation is >> ultimately done >> + in PROMOTE_MODE. Therefore, the value ranges has to be correct upto >> + PROMOTE_MODE precision. If the operation can WRAP, higher bits in >> + PROMOTE_MODE can be unpredictable and cannot be used in zero/sign >> extension >> + elimination; additional wrap_p attribute is needed to show this. >> + >> + For example: >> + on alpha where PROMOTE_MODE is 64 bit and _344 is a 32 bit unsigned >> + variable, >> + _343 = ivtmp.179_52 + 2147483645; [0x80000004, 0x800000043] >> + >> + the value range VRP will compute is: >> + >> + _344 = _343 * 2; [0x8, 0x86] >> + _345 = (integer(kind=4)) _344; [0x8, 0x86] >> + >> + In PROMOTE_MODE, there will be garbage above the type width. In >> places >> + like this, attribute wrap_p will be true. >> + >> + wrap_p in range union operation will be true if either of the >> value range >> + has wrap_p set. In intersect operation, true when both the value >> ranges >> + have wrap_p set. */ >> + bool wrap_p; >> + Thanks for the review. > So what you'd like to know is whether the value range is the same if > all operations were carried out in infinite precision (well, in PROMOTE_MODE > precision). > > I'm not sure you can simply assert that we didn't wrap for example in > extract_range_from_assert. Consider your above code and > > if (_344 < 0x87) > { > _346 = ASSERT_EXPR <_344, _344 < 0x87>; > ... > > _346 definitely should have wrap_p set. I agree. I tried to do this in my patch by propagating wrap_p in extract_range_from_unary_expr_1 for unary assignment of SSA. > That said, I'm not convinced this is a sustainable approach to the issue. > > I've long pondered with replacing the VRP overflow checking code > (for -fstrict-overflow) with keeping two lattices - one honoring undefined > overflow and one not and then comparing the results in the end. > > A similar approach could be used for your wrap_p flag. > > BUT ... a way more sensible approach to reduce the required sign/zero > extensions for PROMOTE_MODE targets is to lower the IL earlier, > before we perform the 2nd VRP run and thus have the sign-/zero-extensions > being eliminated by GIMPLE optimizers rather than only at RTL time. > > ISTR you (or somebody else) played with that a bit? Sorry, I should have mentioned that I am also working on this and will post it as a separate patch. I wanted to try both the approaches and see what is the best ultimately (and also if they can complement each other). Since there are some issues to sort with the wrap_p and you prefer type promotion, I have posted the updated patch for type promotion at: https://gcc.gnu.org/ml/gcc-patches/2015-05/msg00005.html Thanks, Kugan ^ permalink raw reply [flat|nested] 14+ messages in thread
* [RFC][PATCH 3/3] Enable zero/sign extension elimination 2015-01-17 2:10 [RFC][PATCH 0/3] Re-enable zero/sign extension elimination using value ranges Kugan 2015-01-17 2:11 ` [RFC][PATCH 1/3] Free a bit in SSA_NAME to save wrapped information Kugan 2015-01-17 2:44 ` [RFC][PATCH 2/3] Propagate and save value ranges " Kugan @ 2015-01-17 2:58 ` Kugan 2015-04-22 22:15 ` Kugan 2 siblings, 1 reply; 14+ messages in thread From: Kugan @ 2015-01-17 2:58 UTC (permalink / raw) To: gcc-patches; +Cc: Richard Biener, Jakub Jelinek, Jeff Law [-- Attachment #1: Type: text/plain, Size: 561 bytes --] Re-enable zero/sign extension elimination using value range that includes wrapped attribute. Thanks, Kugan gcc/ChangeLog: 2015-01-16 Kugan Vivekanandarajah <kuganv@linaro.org> * calls.c (precompute_arguments): Check promoted_for_signed_and_unsigned_p and set the promoted mode. * expr.c (expand_expr_real_1): Likewise. (promoted_for_signed_and_unsigned_p): New function. * cfgexpand.c (expand_gimple_stmt_1): Call emit_move_insn if SUBREG is promoted with SRP_SIGNED_AND_UNSIGNED. * expr.h (promoted_for_signed_and_unsigned_p): New definition. [-- Attachment #2: patch3.txt --] [-- Type: text/plain, Size: 3622 bytes --] diff --git a/gcc/calls.c b/gcc/calls.c index 36aa19f..71d2469 100644 --- a/gcc/calls.c +++ b/gcc/calls.c @@ -1620,7 +1620,10 @@ precompute_arguments (int num_actuals, struct arg_data *args) args[i].initial_value = gen_lowpart_SUBREG (mode, args[i].value); SUBREG_PROMOTED_VAR_P (args[i].initial_value) = 1; - SUBREG_PROMOTED_SET (args[i].initial_value, args[i].unsignedp); + if (promoted_for_signed_and_unsigned_p (args[i].tree_value)) + SUBREG_PROMOTED_SET (args[i].initial_value, SRP_SIGNED_AND_UNSIGNED); + else + SUBREG_PROMOTED_SET (args[i].initial_value, args[i].unsignedp); } } } diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c index 8926e8f..39d52db 100644 --- a/gcc/cfgexpand.c +++ b/gcc/cfgexpand.c @@ -3410,7 +3410,13 @@ expand_gimple_stmt_1 (gimple stmt) GET_MODE (target), temp, unsignedp); } - convert_move (SUBREG_REG (target), temp, unsignedp); + if ((SUBREG_PROMOTED_GET (target) == SRP_SIGNED_AND_UNSIGNED) + && (GET_CODE (temp) == SUBREG) + && (GET_MODE (target) == GET_MODE (temp)) + && (GET_MODE (SUBREG_REG (target)) == GET_MODE (SUBREG_REG (temp)))) + emit_move_insn (SUBREG_REG (target), SUBREG_REG (temp)); + else + convert_move (SUBREG_REG (target), temp, unsignedp); } else if (nontemporal && emit_storent_insn (target, temp)) ; diff --git a/gcc/expr.c b/gcc/expr.c index fc22862..48a5d13 100644 --- a/gcc/expr.c +++ b/gcc/expr.c @@ -174,6 +174,39 @@ static void emit_single_push_insn (machine_mode, rtx, tree); static void do_tablejump (rtx, machine_mode, rtx, rtx, rtx, int); static rtx const_vector_from_tree (tree); +/* Return TRUE if value in SSA is zero and sign extended for wider mode MODE + using value range information stored. Return FALSE otherwise. + + This is used to check if SUBREG is zero and sign extended and to set + promoted mode SRP_SIGNED_AND_UNSIGNED to SUBREG. */ + +bool +promoted_for_signed_and_unsigned_p (tree ssa) +{ + wide_int min, max; + bool ovf; + + if (ssa == NULL_TREE + || TREE_CODE (ssa) != SSA_NAME + || !INTEGRAL_TYPE_P (TREE_TYPE (ssa))) + return false; + + /* Return FALSE if value_range is not recorded for SSA. */ + if (get_range_info (ssa, &min, &max, &ovf) != VR_RANGE) + return false; + + if (ovf) + return false; + + /* Return true (to set SRP_SIGNED_AND_UNSIGNED to SUBREG) if MSB of the + smaller mode is not set (i.e. MSB of ssa is not set). */ + if (!wi::neg_p (min, SIGNED) && !wi::neg_p(max, SIGNED)) + return true; + else + return false; + +} + \f /* This is run to set up which modes can be used directly in memory and to initialize the block move optab. It is run @@ -9656,7 +9689,10 @@ expand_expr_real_1 (tree exp, rtx target, machine_mode tmode, temp = gen_lowpart_SUBREG (mode, decl_rtl); SUBREG_PROMOTED_VAR_P (temp) = 1; - SUBREG_PROMOTED_SET (temp, unsignedp); + if (promoted_for_signed_and_unsigned_p (ssa_name)) + SUBREG_PROMOTED_SET (temp, SRP_SIGNED_AND_UNSIGNED); + else + SUBREG_PROMOTED_SET (temp, unsignedp); return temp; } diff --git a/gcc/expr.h b/gcc/expr.h index a7638b8..8fb1339 100644 --- a/gcc/expr.h +++ b/gcc/expr.h @@ -288,6 +288,7 @@ extern rtx expand_expr_real_1 (tree, rtx, machine_mode, enum expand_modifier, rtx *, bool); extern rtx expand_expr_real_2 (sepops, rtx, machine_mode, enum expand_modifier); +extern bool promoted_for_signed_and_unsigned_p (tree); /* Generate code for computing expression EXP. An rtx for the computed value is returned. The value is never null. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 3/3] Enable zero/sign extension elimination 2015-01-17 2:58 ` [RFC][PATCH 3/3] Enable zero/sign extension elimination Kugan @ 2015-04-22 22:15 ` Kugan 2015-04-22 23:48 ` H.J. Lu 0 siblings, 1 reply; 14+ messages in thread From: Kugan @ 2015-04-22 22:15 UTC (permalink / raw) To: gcc-patches; +Cc: Richard Biener, Jakub Jelinek, Jeff Law [-- Attachment #1: Type: text/plain, Size: 733 bytes --] On 17/01/15 13:11, Kugan wrote: > > Re-enable zero/sign extension elimination using value range that > includes wrapped attribute. > Now that stage-1 is open, rebased it and regression tested on x86-64-none-linux-gnu with no new regressions. Is this OK for trunk? Thanks, Kugan gcc/ChangeLog: 2015-04-22 Kugan Vivekanandarajah <kuganv@linaro.org> * calls.c (precompute_arguments): Check promoted_for_signed_and_unsigned_p and set the promoted mode. * expr.c (expand_expr_real_1): Likewise. (promoted_for_signed_and_unsigned_p): New function. * cfgexpand.c (expand_gimple_stmt_1): Call emit_move_insn if SUBREG is promoted with SRP_SIGNED_AND_UNSIGNED. * expr.h (promoted_for_signed_and_unsigned_p): New definition. [-- Attachment #2: patch3.txt --] [-- Type: text/plain, Size: 3579 bytes --] diff --git a/gcc/calls.c b/gcc/calls.c index 3be7ca5..6b8d861 100644 --- a/gcc/calls.c +++ b/gcc/calls.c @@ -1637,7 +1637,10 @@ precompute_arguments (int num_actuals, struct arg_data *args) args[i].initial_value = gen_lowpart_SUBREG (mode, args[i].value); SUBREG_PROMOTED_VAR_P (args[i].initial_value) = 1; - SUBREG_PROMOTED_SET (args[i].initial_value, args[i].unsignedp); + if (promoted_for_signed_and_unsigned_p (args[i].tree_value)) + SUBREG_PROMOTED_SET (args[i].initial_value, SRP_SIGNED_AND_UNSIGNED); + else + SUBREG_PROMOTED_SET (args[i].initial_value, args[i].unsignedp); } } } diff --git a/gcc/cfgexpand.c b/gcc/cfgexpand.c index ca491a0..5fcee87 100644 --- a/gcc/cfgexpand.c +++ b/gcc/cfgexpand.c @@ -3452,7 +3452,13 @@ expand_gimple_stmt_1 (gimple stmt) GET_MODE (target), temp, unsignedp); } - convert_move (SUBREG_REG (target), temp, unsignedp); + if ((SUBREG_PROMOTED_GET (target) == SRP_SIGNED_AND_UNSIGNED) + && (GET_CODE (temp) == SUBREG) + && (GET_MODE (target) == GET_MODE (temp)) + && (GET_MODE (SUBREG_REG (target)) == GET_MODE (SUBREG_REG (temp)))) + emit_move_insn (SUBREG_REG (target), SUBREG_REG (temp)); + else + convert_move (SUBREG_REG (target), temp, unsignedp); } else if (nontemporal && emit_storent_insn (target, temp)) ; diff --git a/gcc/expr.c b/gcc/expr.c index 530a944..224a50f 100644 --- a/gcc/expr.c +++ b/gcc/expr.c @@ -185,6 +185,39 @@ static rtx const_vector_from_tree (tree); static tree tree_expr_size (const_tree); static HOST_WIDE_INT int_expr_size (tree); +/* Return TRUE if value in SSA is zero and sign extended for wider mode MODE + using value range information stored. Return FALSE otherwise. + + This is used to check if SUBREG is zero and sign extended and to set + promoted mode SRP_SIGNED_AND_UNSIGNED to SUBREG. */ + +bool +promoted_for_signed_and_unsigned_p (tree ssa) +{ + wide_int min, max; + bool ovf; + + if (ssa == NULL_TREE + || TREE_CODE (ssa) != SSA_NAME + || !INTEGRAL_TYPE_P (TREE_TYPE (ssa))) + return false; + + /* Return FALSE if value_range is not recorded for SSA. */ + if (get_range_info (ssa, &min, &max, &ovf) != VR_RANGE) + return false; + + if (ovf) + return false; + + /* Return true (to set SRP_SIGNED_AND_UNSIGNED to SUBREG) if MSB of the + smaller mode is not set (i.e. MSB of ssa is not set). */ + if (!wi::neg_p (min, SIGNED) && !wi::neg_p(max, SIGNED)) + return true; + else + return false; + +} + \f /* This is run to set up which modes can be used directly in memory and to initialize the block move optab. It is run @@ -9674,7 +9707,10 @@ expand_expr_real_1 (tree exp, rtx target, machine_mode tmode, temp = gen_lowpart_SUBREG (mode, decl_rtl); SUBREG_PROMOTED_VAR_P (temp) = 1; - SUBREG_PROMOTED_SET (temp, unsignedp); + if (promoted_for_signed_and_unsigned_p (ssa_name)) + SUBREG_PROMOTED_SET (temp, SRP_SIGNED_AND_UNSIGNED); + else + SUBREG_PROMOTED_SET (temp, unsignedp); return temp; } diff --git a/gcc/expr.h b/gcc/expr.h index 867852e..f965fe0 100644 --- a/gcc/expr.h +++ b/gcc/expr.h @@ -243,6 +243,7 @@ extern rtx expand_expr_real_1 (tree, rtx, machine_mode, enum expand_modifier, rtx *, bool); extern rtx expand_expr_real_2 (sepops, rtx, machine_mode, enum expand_modifier); +extern bool promoted_for_signed_and_unsigned_p (tree); /* Generate code for computing expression EXP. An rtx for the computed value is returned. The value is never null. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 3/3] Enable zero/sign extension elimination 2015-04-22 22:15 ` Kugan @ 2015-04-22 23:48 ` H.J. Lu 2015-04-22 23:54 ` Kugan 0 siblings, 1 reply; 14+ messages in thread From: H.J. Lu @ 2015-04-22 23:48 UTC (permalink / raw) To: Kugan; +Cc: gcc-patches, Richard Biener, Jakub Jelinek, Jeff Law On Wed, Apr 22, 2015 at 3:15 PM, Kugan <kugan.vivekanandarajah@linaro.org> wrote: > On 17/01/15 13:11, Kugan wrote: >> >> Re-enable zero/sign extension elimination using value range that >> includes wrapped attribute. >> > > Now that stage-1 is open, rebased it and regression tested on > x86-64-none-linux-gnu with no new regressions. > > Is this OK for trunk? > > Thanks, > Kugan > > gcc/ChangeLog: > > 2015-04-22 Kugan Vivekanandarajah <kuganv@linaro.org> > > * calls.c (precompute_arguments): Check > promoted_for_signed_and_unsigned_p and set the promoted mode. > * expr.c (expand_expr_real_1): Likewise. > (promoted_for_signed_and_unsigned_p): New function. > * cfgexpand.c (expand_gimple_stmt_1): Call emit_move_insn if > SUBREG is promoted with SRP_SIGNED_AND_UNSIGNED. > * expr.h (promoted_for_signed_and_unsigned_p): New definition. Are you planning to submit some testcases to show its improvement? Will it help https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53639 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33349 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=44532 -- H.J. ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [RFC][PATCH 3/3] Enable zero/sign extension elimination 2015-04-22 23:48 ` H.J. Lu @ 2015-04-22 23:54 ` Kugan 0 siblings, 0 replies; 14+ messages in thread From: Kugan @ 2015-04-22 23:54 UTC (permalink / raw) To: H.J. Lu; +Cc: gcc-patches, Richard Biener, Jakub Jelinek, Jeff Law On 23/04/15 09:48, H.J. Lu wrote: > On Wed, Apr 22, 2015 at 3:15 PM, Kugan > <kugan.vivekanandarajah@linaro.org> wrote: >> On 17/01/15 13:11, Kugan wrote: >>> >>> Re-enable zero/sign extension elimination using value range that >>> includes wrapped attribute. >>> >> >> Now that stage-1 is open, rebased it and regression tested on >> x86-64-none-linux-gnu with no new regressions. >> >> Is this OK for trunk? >> >> Thanks, >> Kugan >> >> gcc/ChangeLog: >> >> 2015-04-22 Kugan Vivekanandarajah <kuganv@linaro.org> >> >> * calls.c (precompute_arguments): Check >> promoted_for_signed_and_unsigned_p and set the promoted mode. >> * expr.c (expand_expr_real_1): Likewise. >> (promoted_for_signed_and_unsigned_p): New function. >> * cfgexpand.c (expand_gimple_stmt_1): Call emit_move_insn if >> SUBREG is promoted with SRP_SIGNED_AND_UNSIGNED. >> * expr.h (promoted_for_signed_and_unsigned_p): New definition. > > Are you planning to submit some testcases to show its improvement? > Will it help > > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53639 > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=33349 > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=44532 Thanks H.J. Lu for the link. I will investigate them and will come up with test cases if my patches help these. Kugan ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2015-05-01 4:55 UTC | newest] Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2015-01-17 2:10 [RFC][PATCH 0/3] Re-enable zero/sign extension elimination using value ranges Kugan 2015-01-17 2:11 ` [RFC][PATCH 1/3] Free a bit in SSA_NAME to save wrapped information Kugan 2015-04-22 22:14 ` Kugan 2015-01-17 2:44 ` [RFC][PATCH 2/3] Propagate and save value ranges " Kugan 2015-01-19 12:52 ` Richard Biener 2015-04-22 22:11 ` Kugan 2015-04-30 11:44 ` Richard Biener 2015-04-30 11:53 ` Jakub Jelinek 2015-04-30 12:13 ` Richard Biener 2015-05-01 4:55 ` Kugan 2015-01-17 2:58 ` [RFC][PATCH 3/3] Enable zero/sign extension elimination Kugan 2015-04-22 22:15 ` Kugan 2015-04-22 23:48 ` H.J. Lu 2015-04-22 23:54 ` Kugan
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).