Re: [PATCH] Teach VRP to register assertions along default switch labels (PR 18046)

[Patrick Palka <patrick at parcs dot ath dot cx>]

On Mon, Jul 25, 2016 at 6:00 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jul 25, 2016 at 5:38 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
>> On Fri, 22 Jul 2016, Patrick Palka wrote:
>>
>>> On Fri, 22 Jul 2016, Patrick Palka wrote:
>>>
>>> > On Fri, 22 Jul 2016, Patrick Palka wrote:
>>> >
>>> > > This patch teaches VRP to register along a default switch label
>>> > > assertions that corresponds to the anti range of each case label.
>>> > >
>>> > > Does this look OK to commit after bootstrap + regtest on
>>> > > x86_64-pc-linux-gnu?
>>> >
>>> > Forgot the changelog:
>>> >
>>> > gcc/ChangeLog:
>>> >
>>> >     PR tree-optimization/18046
>>> >     * tree-vrp.c (find_switch_asserts): Register edge assertions
>>> >     for the default label which correspond to the anti-ranges
>>> >     of each non-case label.
>>> >
>>> > gcc/testsuite/ChangeLog:
>>> >
>>> >     PR tree-optimization/18046
>>> >     * gcc.dg/tree-ssa/ssa-dom-thread-6.c: Bump FSM count to 5.
>>> >     * gcc.dg/tree-ssa/vrp103.c: New test.
>>> >     * gcc.dg/tree-ssa/vrp104.c: New test.
>>> >
>>>
>>> The patch failed to bootstrap due to a number -Warray-bounds warnings
>>> getting emitted for the autogenerated header file insn-modes.h:
>>>
>>> In file included from /home/patrick/code/gcc/gcc/machmode.h:24:0,
>>>                  from /home/patrick/code/gcc/gcc/coretypes.h:391,
>>>                  from /home/patrick/code/gcc/gcc/lto-streamer-out.c:25:
>>> ./insn-modes.h: In function ‘void produce_asm_for_decls()’:
>>> ./insn-modes.h:638:36: warning: array subscript is outside array bounds [-Warray-bounds]
>>>      default: return mode_inner[mode];
>>>                      ~~~~~~~~~~~~~~~^
>>>
>>> These new warnings seem legitimate.  From what I can tell, this array
>>> access along the default switch label will always be out of bounds.  The
>>> code it's warning about basically looks like this:
>>>
>>>   enum A { a, b, c };
>>>   int foo (A i)
>>>   {
>>>     int array[3];
>>>     switch (i)
>>>     {
>>>       case a: return x;
>>>       case b: return y;
>>>       case c: return z;
>>>       default: return array[i];
>>>     }
>>>   }
>>>
>>> and while the switch does exhaust every possible enumeration value of A,
>>> there's nothing stopping the user from passing an arbitrary int to
>>> foo() thus triggering the default case.  So this patch suppresses these
>>> warnings by making genemit emit an assertion that verifies that mode is
>>> within the bounds of the array.  This assertion won't affect performance
>>> because the mode_*_inline functions are always called with constant
>>> arguments.
>>>
>>> This version of the patch has the following changes:
>>>
>>> 1. Fixes the bootstrap failure as mentioned above.
>>> 2. Checks if the switch operand is live along the default edge before
>>> registering assertions.
>>> 3. Combines contiguous case ranges to reduce the number of assert
>>> expressions to insert.
>>>
>>> Bootstrap + regtesting in progress on x86_64-pc-linux-gnu.
>>>
>>> gcc/ChangeLog:
>>>
>>>       PR tree-optimization/18046
>>>       * genmodes.c (emit_mode_size_inline): Emit an assert that
>>>       verifies that mode is a valid array index.
>>>       (emit_mode_nuinits_inline): Likewise.
>>>       (emit_mode_inner_inline): Likewise.
>>>       (emit_mode_unit_size_inline): Likewise.
>>>       (emit_mode_unit_precision_inline): Likewise.
>>>       * tree-vrp.c (compare_case_label_values): New qsort callback.
>>>       (find_switch_asserts): Register edge assertions for
>>>       the default label, which correspond to the anti-range of each
>>>       non-case label.
>>>
>>> gcc/testsuite/ChangeLog:
>>>
>>>       PR tree-optimization/18046
>>>       * gcc.dg/tree-ssa/ssa-dom-thread-6.c: Bump FSM count to 5.
>>>       * gcc.dg/tree-ssa/vrp103.c: New test.
>>>       * gcc.dg/tree-ssa/vrp104.c: New test.
>>
>> Here's another version of the patch, which has the following changes:
>>
>> 1. Use wide-int arithmetic directly instead of tree arithmetic.
>> 2. Don't bother re-sorting and re-using the ci vector.  Instead just
>> inspect gimple_switch_label() directly since cases are already sorted
>> there by CASE_LOW.
>> 3. Add an insertion limit of 10 and a tunable param.
>>
>> Bootstrapped + regtested on x86_64-pc-linux-gnu.
>
> Ok.
>
> The only thing I wonder is whether VRP does a good job combining
> non-adjacent anti-ranges or if the result is sth non-sensible.  ISTR
> VRP simply chooses A when combining A and B which would mean
> inserting asserts will only provide better ranges for more than one
> asserts via equivalences (which might be good enough, of course).

Yeah, the shadowed asserts remain useful via equivalences.

> I think the anti-range merge behavior is good but I for example wonder
> about the behavior for ~[0, n] which will end up as [n, +INF] for
> unsigned.

Yes but that's fine right? (If you meant [n+1, +INF])

> Also the combining limitation will make ranges derived
> from the switch parameter less useful, like
>
>   switch (x)
>   {
> ....
>   default:
>      x++;
> ....
>
> where x++ will only be derived from the merged anti-range.

Yeah that's pretty unfortunate..  BTW, when looking at what VRP does
with such code I noticed another deficiency for which I filed PR
72443.

Thanks for reviewing!