Improve VRP range intersection for partly symbolic ranges

The following makes intersecting [-INF, +10] and [a + -1, +INF]
to [10, a + -1] possible with the chance that for a <= 10 the
resulting range will be empty (but not trivially visible as so).

Bootstrap / regtest running on x86_64-unknown-linux-gnu.

I'll add a testcase later.

Richard.

2017-04-27  Richard Biener  <rguenther@suse.de>

	* tree-vrp.c (intersect_ranges): Better handle partly
	symbolic ranges.

On Thu, Apr 27, 2017 at 2:49 PM, Richard Biener <rguenther@suse.de> wrote:
>
> The following makes intersecting [-INF, +10] and [a + -1, +INF]
> to [10, a + -1] possible with the chance that for a <= 10 the
> resulting range will be empty (but not trivially visible as so).
Hi,
I noticed operand_less_p is quite simple, so does
fold_binary_to_constant take range information into consideration?  In
this case, it is a's range information to be considered.  Otherwise it
can't tell between "a + -1" and 10.  It is good to have [10, a+-1] in
this case if we can do it (by using compare_values or similar
interface), but I remember there are quite lots of fallouts in
handling symbolic ranges, which could result in worse range
information overall in the end.  It is PR71437 when I found out this
in VRP.  I had some patches improving symbolic range handling, but
gave up last time because keep running into new cases.

Thanks,
bin
>
> Bootstrap / regtest running on x86_64-unknown-linux-gnu.
>
> I'll add a testcase later.
>
> Richard.
>
> 2017-04-27  Richard Biener  <rguenther@suse.de>
>
>         * tree-vrp.c (intersect_ranges): Better handle partly
>         symbolic ranges.
>
> Index: gcc/tree-vrp.c
> ===================================================================
> --- gcc/tree-vrp.c      (revision 247334)
> +++ gcc/tree-vrp.c      (working copy)
> @@ -8989,6 +8989,28 @@ intersect_ranges (enum value_range_type
>        else
>         gcc_unreachable ();
>      }
> +  else if (operand_less_p (*vr0min, vr1max) == 1
> +          && operand_less_p (*vr0min, vr1min) == 1
> +          && operand_less_p (*vr0max, vr1max) == 1
> +          && operand_less_p (vr1min, *vr0max) == -2)
> +    {
> +      /* [ (] )  with ] and ( being unordered as (partly) symbolic.
> +         This can result in ranges that are effectively empty.  */
> +      if (*vr0type == VR_RANGE
> +         && vr1type == VR_RANGE)
> +       *vr0min = vr1min;
> +    }
> +  else if (operand_less_p (vr1min, *vr0max) == 1
> +          && operand_less_p (vr1min, *vr0min) == 1
> +          && operand_less_p (vr1max, *vr0max) == 1
> +          && operand_less_p (*vr0min, vr1max) == -2)
> +    {
> +      /* ( [) ]  with ] and ( being unordered as (partly) symbolic.
> +         This can result in ranges that are effectively empty.  */
> +      if (*vr0type == VR_RANGE
> +         && vr1type == VR_RANGE)
> +       *vr0max = vr1max;
> +    }
>
>    /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
>       result for the intersection.  That's always a conservative

On April 27, 2017 4:06:48 PM GMT+02:00, "Bin.Cheng" <amker.cheng@gmail.com> wrote:
>On Thu, Apr 27, 2017 at 2:49 PM, Richard Biener <rguenther@suse.de>
>wrote:
>>
>> The following makes intersecting [-INF, +10] and [a + -1, +INF]
>> to [10, a + -1] possible with the chance that for a <= 10 the
>> resulting range will be empty (but not trivially visible as so).
>Hi,
>I noticed operand_less_p is quite simple, so does
>fold_binary_to_constant take range information into consideration?  In
>this case, it is a's range information to be considered.  Otherwise it
>can't tell between "a + -1" and 10. 

I think we can get away without knowing
Given the constraints on the other ends of the ranges.  So it's really just a special case that came up with testing another patch.

Richard.

 It is good to have [10, a+-1] in
>this case if we can do it (by using compare_values or similar
>interface), but I remember there are quite lots of fallouts in
>handling symbolic ranges, which could result in worse range
>information overall in the end.  It is PR71437 when I found out this
>in VRP.  I had some patches improving symbolic range handling, but
>gave up last time because keep running into new cases.
>
>Thanks,
>bin
>>
>> Bootstrap / regtest running on x86_64-unknown-linux-gnu.
>>
>> I'll add a testcase later.
>>
>> Richard.
>>
>> 2017-04-27  Richard Biener  <rguenther@suse.de>
>>
>>         * tree-vrp.c (intersect_ranges): Better handle partly
>>         symbolic ranges.
>>
>> Index: gcc/tree-vrp.c
>> ===================================================================
>> --- gcc/tree-vrp.c      (revision 247334)
>> +++ gcc/tree-vrp.c      (working copy)
>> @@ -8989,6 +8989,28 @@ intersect_ranges (enum value_range_type
>>        else
>>         gcc_unreachable ();
>>      }
>> +  else if (operand_less_p (*vr0min, vr1max) == 1
>> +          && operand_less_p (*vr0min, vr1min) == 1
>> +          && operand_less_p (*vr0max, vr1max) == 1
>> +          && operand_less_p (vr1min, *vr0max) == -2)
>> +    {
>> +      /* [ (] )  with ] and ( being unordered as (partly) symbolic.
>> +         This can result in ranges that are effectively empty.  */
>> +      if (*vr0type == VR_RANGE
>> +         && vr1type == VR_RANGE)
>> +       *vr0min = vr1min;
>> +    }
>> +  else if (operand_less_p (vr1min, *vr0max) == 1
>> +          && operand_less_p (vr1min, *vr0min) == 1
>> +          && operand_less_p (vr1max, *vr0max) == 1
>> +          && operand_less_p (*vr0min, vr1max) == -2)
>> +    {
>> +      /* ( [) ]  with ] and ( being unordered as (partly) symbolic.
>> +         This can result in ranges that are effectively empty.  */
>> +      if (*vr0type == VR_RANGE
>> +         && vr1type == VR_RANGE)
>> +       *vr0max = vr1max;
>> +    }
>>
>>    /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
>>       result for the intersection.  That's always a conservative

On Thu, 27 Apr 2017, Richard Biener wrote:

> On April 27, 2017 4:06:48 PM GMT+02:00, "Bin.Cheng" <amker.cheng@gmail.com> wrote:
> >On Thu, Apr 27, 2017 at 2:49 PM, Richard Biener <rguenther@suse.de>
> >wrote:
> >>
> >> The following makes intersecting [-INF, +10] and [a + -1, +INF]
> >> to [10, a + -1] possible with the chance that for a <= 10 the
> >> resulting range will be empty (but not trivially visible as so).
> >Hi,
> >I noticed operand_less_p is quite simple, so does
> >fold_binary_to_constant take range information into consideration?  In
> >this case, it is a's range information to be considered.  Otherwise it
> >can't tell between "a + -1" and 10. 
> 
> I think we can get away without knowing
> Given the constraints on the other ends of the ranges.  So it's really just a special case that came up with testing another patch.

So actually the patch causes [k_3(D), +INF] intersected with
[10, +INF] to become [k_3(D), +INF].  That's not a win IMHO.

Thus retracted for now.

Richard.

> Richard.
> 
>  It is good to have [10, a+-1] in
> >this case if we can do it (by using compare_values or similar
> >interface), but I remember there are quite lots of fallouts in
> >handling symbolic ranges, which could result in worse range
> >information overall in the end.  It is PR71437 when I found out this
> >in VRP.  I had some patches improving symbolic range handling, but
> >gave up last time because keep running into new cases.
> >
> >Thanks,
> >bin
> >>
> >> Bootstrap / regtest running on x86_64-unknown-linux-gnu.
> >>
> >> I'll add a testcase later.
> >>
> >> Richard.
> >>
> >> 2017-04-27  Richard Biener  <rguenther@suse.de>
> >>
> >>         * tree-vrp.c (intersect_ranges): Better handle partly
> >>         symbolic ranges.
> >>
> >> Index: gcc/tree-vrp.c
> >> ===================================================================
> >> --- gcc/tree-vrp.c      (revision 247334)
> >> +++ gcc/tree-vrp.c      (working copy)
> >> @@ -8989,6 +8989,28 @@ intersect_ranges (enum value_range_type
> >>        else
> >>         gcc_unreachable ();
> >>      }
> >> +  else if (operand_less_p (*vr0min, vr1max) == 1
> >> +          && operand_less_p (*vr0min, vr1min) == 1
> >> +          && operand_less_p (*vr0max, vr1max) == 1
> >> +          && operand_less_p (vr1min, *vr0max) == -2)
> >> +    {
> >> +      /* [ (] )  with ] and ( being unordered as (partly) symbolic.
> >> +         This can result in ranges that are effectively empty.  */
> >> +      if (*vr0type == VR_RANGE
> >> +         && vr1type == VR_RANGE)
> >> +       *vr0min = vr1min;
> >> +    }
> >> +  else if (operand_less_p (vr1min, *vr0max) == 1
> >> +          && operand_less_p (vr1min, *vr0min) == 1
> >> +          && operand_less_p (vr1max, *vr0max) == 1
> >> +          && operand_less_p (*vr0min, vr1max) == -2)
> >> +    {
> >> +      /* ( [) ]  with ] and ( being unordered as (partly) symbolic.
> >> +         This can result in ranges that are effectively empty.  */
> >> +      if (*vr0type == VR_RANGE
> >> +         && vr1type == VR_RANGE)
> >> +       *vr0max = vr1max;
> >> +    }
> >>
> >>    /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
> >>       result for the intersection.  That's always a conservative
> 
>