Re: [RFC][PATCH 2/3] Propagate and save value ranges wrapped information

[Kugan <kugan dot vivekanandarajah at linaro dot org>]

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