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

[Richard Biener <richard.guenther@gmail.com>]

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.