* Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321)
@ 2018-02-12 15:30 Richard Sandiford
2018-02-13 15:26 ` Richard Biener
0 siblings, 1 reply; 3+ messages in thread
From: Richard Sandiford @ 2018-02-12 15:30 UTC (permalink / raw)
To: gcc-patches
VR_ANTI_RANGE is basically a union of two ranges, and although
intersect_range_with_nonzero_bits had code to deal with the upper
one being empty, it didn't handle the lower one being empty.
There were also some off-by-one errors.
This patch rewrites the code in a hopefully clearer way.
Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install?
Richard
2018-02-12 Richard Sandiford <richard.sandiford@linaro.org>
gcc/
PR tree-optimization/84321
* tree-vrp.c (intersect_range_with_nonzero_bits): Fix VR_ANTI_RANGE
handling. Also check whether the anti-range contains any values
that satisfy the mask; switch to a VR_RANGE if not.
gcc/testsuite/
PR tree-optimization/84321
* gcc.dg/pr84321.c: New test.
Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c 2018-02-08 15:16:21.784407397 +0000
--- gcc/tree-vrp.c 2018-02-12 15:26:13.703500747 +0000
*************** intersect_range_with_nonzero_bits (enum
*** 184,220 ****
const wide_int &nonzero_bits,
signop sgn)
{
! if (vr_type == VR_RANGE)
{
! *max = wi::round_down_for_mask (*max, nonzero_bits);
! /* Check that the range contains at least one valid value. */
! if (wi::gt_p (*min, *max, sgn))
! return VR_UNDEFINED;
! *min = wi::round_up_for_mask (*min, nonzero_bits);
! gcc_checking_assert (wi::le_p (*min, *max, sgn));
! }
! if (vr_type == VR_ANTI_RANGE)
! {
! *max = wi::round_up_for_mask (*max, nonzero_bits);
! /* If the calculation wrapped, we now have a VR_RANGE whose
! lower bound is *MAX and whose upper bound is *MIN. */
! if (wi::gt_p (*min, *max, sgn))
{
! std::swap (*min, *max);
! *max = wi::round_down_for_mask (*max, nonzero_bits);
gcc_checking_assert (wi::le_p (*min, *max, sgn));
return VR_RANGE;
}
! *min = wi::round_down_for_mask (*min, nonzero_bits);
gcc_checking_assert (wi::le_p (*min, *max, sgn));
! /* Check whether we now have an empty set of values. */
! if (*min - 1 == *max)
return VR_UNDEFINED;
}
return vr_type;
}
--- 184,244 ----
const wide_int &nonzero_bits,
signop sgn)
{
! if (vr_type == VR_ANTI_RANGE)
{
! /* The VR_ANTI_RANGE is equivalent to the union of the ranges
! A: [-INF, *MIN) and B: (*MAX, +INF]. First use NONZERO_BITS
! to create an inclusive upper bound for A and an inclusive lower
! bound for B. */
! wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits);
! wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits);
! /* If the calculation of A_MAX wrapped, A is effectively empty
! and A_MAX is the highest value that satisfies NONZERO_BITS.
! Likewise if the calculation of B_MIN wrapped, B is effectively
! empty and B_MIN is the lowest value that satisfies NONZERO_BITS. */
! bool a_empty = wi::ge_p (a_max, *min, sgn);
! bool b_empty = wi::le_p (b_min, *max, sgn);
! /* If both A and B are empty, there are no valid values. */
! if (a_empty && b_empty)
! return VR_UNDEFINED;
! /* If exactly one of A or B is empty, return a VR_RANGE for the
! other one. */
! if (a_empty || b_empty)
{
! *min = b_min;
! *max = a_max;
gcc_checking_assert (wi::le_p (*min, *max, sgn));
return VR_RANGE;
}
! /* Update the VR_ANTI_RANGE bounds. */
! *min = a_max + 1;
! *max = b_min - 1;
gcc_checking_assert (wi::le_p (*min, *max, sgn));
! /* Now check whether the excluded range includes any values that
! satisfy NONZERO_BITS. If not, switch to a full VR_RANGE. */
! if (wi::round_up_for_mask (*min, nonzero_bits) == b_min)
! {
! unsigned int precision = min->get_precision ();
! *min = wi::min_value (precision, sgn);
! *max = wi::max_value (precision, sgn);
! vr_type = VR_RANGE;
! }
! }
! if (vr_type == VR_RANGE)
! {
! *max = wi::round_down_for_mask (*max, nonzero_bits);
!
! /* Check that the range contains at least one valid value. */
! if (wi::gt_p (*min, *max, sgn))
return VR_UNDEFINED;
+
+ *min = wi::round_up_for_mask (*min, nonzero_bits);
+ gcc_checking_assert (wi::le_p (*min, *max, sgn));
}
return vr_type;
}
Index: gcc/testsuite/gcc.dg/pr84321.c
===================================================================
*** /dev/null 2018-02-10 09:05:46.714416790 +0000
--- gcc/testsuite/gcc.dg/pr84321.c 2018-02-12 15:26:13.702500788 +0000
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O3 -fwrapv" } */
+
+ int c;
+
+ void
+ foo (int *a, int b)
+ {
+ int e;
+ if (b == 1)
+ return;
+ for (e = 0; e < (b & ~7); e += 8)
+ ;
+ for (++e; e < b;)
+ c = a[e];
+ }
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321)
2018-02-12 15:30 Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321) Richard Sandiford
@ 2018-02-13 15:26 ` Richard Biener
2018-02-13 15:49 ` Jeff Law
0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2018-02-13 15:26 UTC (permalink / raw)
To: GCC Patches, Richard Sandiford
On Mon, Feb 12, 2018 at 4:29 PM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> VR_ANTI_RANGE is basically a union of two ranges, and although
> intersect_range_with_nonzero_bits had code to deal with the upper
> one being empty, it didn't handle the lower one being empty.
> There were also some off-by-one errors.
>
> This patch rewrites the code in a hopefully clearer way.
>
> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install?
Ok.
Richard.
> Richard
>
>
> 2018-02-12 Richard Sandiford <richard.sandiford@linaro.org>
>
> gcc/
> PR tree-optimization/84321
> * tree-vrp.c (intersect_range_with_nonzero_bits): Fix VR_ANTI_RANGE
> handling. Also check whether the anti-range contains any values
> that satisfy the mask; switch to a VR_RANGE if not.
>
> gcc/testsuite/
> PR tree-optimization/84321
> * gcc.dg/pr84321.c: New test.
>
> Index: gcc/tree-vrp.c
> ===================================================================
> *** gcc/tree-vrp.c 2018-02-08 15:16:21.784407397 +0000
> --- gcc/tree-vrp.c 2018-02-12 15:26:13.703500747 +0000
> *************** intersect_range_with_nonzero_bits (enum
> *** 184,220 ****
> const wide_int &nonzero_bits,
> signop sgn)
> {
> ! if (vr_type == VR_RANGE)
> {
> ! *max = wi::round_down_for_mask (*max, nonzero_bits);
>
> ! /* Check that the range contains at least one valid value. */
> ! if (wi::gt_p (*min, *max, sgn))
> ! return VR_UNDEFINED;
>
> ! *min = wi::round_up_for_mask (*min, nonzero_bits);
> ! gcc_checking_assert (wi::le_p (*min, *max, sgn));
> ! }
> ! if (vr_type == VR_ANTI_RANGE)
> ! {
> ! *max = wi::round_up_for_mask (*max, nonzero_bits);
>
> ! /* If the calculation wrapped, we now have a VR_RANGE whose
> ! lower bound is *MAX and whose upper bound is *MIN. */
> ! if (wi::gt_p (*min, *max, sgn))
> {
> ! std::swap (*min, *max);
> ! *max = wi::round_down_for_mask (*max, nonzero_bits);
> gcc_checking_assert (wi::le_p (*min, *max, sgn));
> return VR_RANGE;
> }
>
> ! *min = wi::round_down_for_mask (*min, nonzero_bits);
> gcc_checking_assert (wi::le_p (*min, *max, sgn));
>
> ! /* Check whether we now have an empty set of values. */
> ! if (*min - 1 == *max)
> return VR_UNDEFINED;
> }
> return vr_type;
> }
> --- 184,244 ----
> const wide_int &nonzero_bits,
> signop sgn)
> {
> ! if (vr_type == VR_ANTI_RANGE)
> {
> ! /* The VR_ANTI_RANGE is equivalent to the union of the ranges
> ! A: [-INF, *MIN) and B: (*MAX, +INF]. First use NONZERO_BITS
> ! to create an inclusive upper bound for A and an inclusive lower
> ! bound for B. */
> ! wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits);
> ! wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits);
>
> ! /* If the calculation of A_MAX wrapped, A is effectively empty
> ! and A_MAX is the highest value that satisfies NONZERO_BITS.
> ! Likewise if the calculation of B_MIN wrapped, B is effectively
> ! empty and B_MIN is the lowest value that satisfies NONZERO_BITS. */
> ! bool a_empty = wi::ge_p (a_max, *min, sgn);
> ! bool b_empty = wi::le_p (b_min, *max, sgn);
>
> ! /* If both A and B are empty, there are no valid values. */
> ! if (a_empty && b_empty)
> ! return VR_UNDEFINED;
>
> ! /* If exactly one of A or B is empty, return a VR_RANGE for the
> ! other one. */
> ! if (a_empty || b_empty)
> {
> ! *min = b_min;
> ! *max = a_max;
> gcc_checking_assert (wi::le_p (*min, *max, sgn));
> return VR_RANGE;
> }
>
> ! /* Update the VR_ANTI_RANGE bounds. */
> ! *min = a_max + 1;
> ! *max = b_min - 1;
> gcc_checking_assert (wi::le_p (*min, *max, sgn));
>
> ! /* Now check whether the excluded range includes any values that
> ! satisfy NONZERO_BITS. If not, switch to a full VR_RANGE. */
> ! if (wi::round_up_for_mask (*min, nonzero_bits) == b_min)
> ! {
> ! unsigned int precision = min->get_precision ();
> ! *min = wi::min_value (precision, sgn);
> ! *max = wi::max_value (precision, sgn);
> ! vr_type = VR_RANGE;
> ! }
> ! }
> ! if (vr_type == VR_RANGE)
> ! {
> ! *max = wi::round_down_for_mask (*max, nonzero_bits);
> !
> ! /* Check that the range contains at least one valid value. */
> ! if (wi::gt_p (*min, *max, sgn))
> return VR_UNDEFINED;
> +
> + *min = wi::round_up_for_mask (*min, nonzero_bits);
> + gcc_checking_assert (wi::le_p (*min, *max, sgn));
> }
> return vr_type;
> }
> Index: gcc/testsuite/gcc.dg/pr84321.c
> ===================================================================
> *** /dev/null 2018-02-10 09:05:46.714416790 +0000
> --- gcc/testsuite/gcc.dg/pr84321.c 2018-02-12 15:26:13.702500788 +0000
> ***************
> *** 0 ****
> --- 1,16 ----
> + /* { dg-do compile } */
> + /* { dg-options "-O3 -fwrapv" } */
> +
> + int c;
> +
> + void
> + foo (int *a, int b)
> + {
> + int e;
> + if (b == 1)
> + return;
> + for (e = 0; e < (b & ~7); e += 8)
> + ;
> + for (++e; e < b;)
> + c = a[e];
> + }
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321)
2018-02-13 15:26 ` Richard Biener
@ 2018-02-13 15:49 ` Jeff Law
0 siblings, 0 replies; 3+ messages in thread
From: Jeff Law @ 2018-02-13 15:49 UTC (permalink / raw)
To: Richard Biener, GCC Patches, Richard Sandiford
On 02/13/2018 08:26 AM, Richard Biener wrote:
> On Mon, Feb 12, 2018 at 4:29 PM, Richard Sandiford
> <richard.sandiford@linaro.org> wrote:
>> VR_ANTI_RANGE is basically a union of two ranges, and although
>> intersect_range_with_nonzero_bits had code to deal with the upper
>> one being empty, it didn't handle the lower one being empty.
>> There were also some off-by-one errors.
>>
>> This patch rewrites the code in a hopefully clearer way.
>>
>> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install?
>
> Ok.
And committed.
jeff
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2018-02-13 15:49 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-02-12 15:30 Fix VR_ANTI_RANGE handling in intersect_range_with_nonzero_bits (PR 84321) Richard Sandiford
2018-02-13 15:26 ` Richard Biener
2018-02-13 15:49 ` Jeff Law
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).