[PATCH] Add one more pass_convert_switch late.

[Martin Liška]

On 11/18/19 3:07 PM, Jakub Jelinek wrote:
> On Mon, Nov 18, 2019 at 02:39:12PM +0100, Martin Liška wrote:
>> On 11/18/19 11:06 AM, Jakub Jelinek wrote:
>>> On Mon, Nov 18, 2019 at 10:17:56AM +0100, Martin Liška wrote:
>>>> On 11/14/19 1:15 PM, Richard Biener wrote:
>>>>> Hmm.  I was thinking of moving the pass instead of adding another one.
>>>>> What's the reason to run switch-conversion during early optimization again?
>>>>
>>>> I'm adding CC, as he's the author of cswitch pass and he probably knows
>>>> more about the pass placement. But I bet early conversion to array access
>>>> rapidly simplifies CFG and other passes can benefit from that.
>>>
>>> Yes, I think the early placement is to take it into account in inlining
>>> decisions, on the other side it causes various issues, I think we have
>>> several PRs open where the early cswitch just makes a good decision based on
>>> what it knows at that point, but later on we find better VRP ranges for the
>>> switch condition and it is too late to undo it and handle it differently.
>>
>> I bet we must have multiple similar problems where one transformation makes
>> a transformation that other pass is not happy about.
> 
> This is something that happens quite often.  Typical example is where
> we commit to doing a an constant array load and later the range is narrowed
> and it would be better done either as a bitmask test, or say the constant
> array load with sometimes much shorter needed arrays.

I agree that it can be quite often optimization.

> 
>> I don't like the suggested approach much. There can be optimization in between
>> that can leverage the conversion to a constant array.
> 
> For what exactly?

Dunno :) Well, that said we can move the cswitch pass later in the pipeline..

> 
>>> Another thing is perform the optimizations we do in reassoc (but aren't
>>
>> What kind of optimizations do you mean?
> 
> I believe the cswitch expansion can handle well the case where certain
> range can be expressed as ((unsigned) x - const1) <= const2) conditional,
> but reassoc has also optimize_range_tests_xor, optimize_range_tests_diff,
> both of which can be applied multiple times.  To quote the comments
> explaining what it does:
> /* Optimize X == CST1 || X == CST2
>     if popcount (CST1 ^ CST2) == 1 into
>     (X & ~(CST1 ^ CST2)) == (CST1 & ~(CST1 ^ CST2)).
>     Similarly for ranges.  E.g.
>     X != 2 && X != 3 && X != 10 && X != 11
>     will be transformed by the previous optimization into
>     !((X - 2U) <= 1U || (X - 10U) <= 1U)
>     and this loop can transform that into
>     !(((X & ~8) - 2U) <= 1U).  */
> and
> /* Optimize X == CST1 || X == CST2
>     if popcount (CST2 - CST1) == 1 into
>     ((X - CST1) & ~(CST2 - CST1)) == 0.
>     Similarly for ranges.  E.g.
>     X == 43 || X == 76 || X == 44 || X == 78 || X == 77 || X == 46
>     || X == 75 || X == 45
>     will be transformed by the previous optimization into
>     (X - 43U) <= 3U || (X - 75U) <= 3U
>     and this loop can transform that into
>     ((X - 43U) & ~(75U - 43U)) <= 3U.  */
> Now, I believe with the if to gswitch optimization these will only rarely
> kick in, because the IL will have switches that reassoc doesn't handle,
> instead of series of ifs.

Yes, so my question is whether reassoc can handle gswitch statements similar
to series of if statements? Note that use can write explicitly something like:

switch (a)
    case 0...30:
       return 1;
    case 32:
       return 1;
    case 34:
       return 1;

which won't be optimized by reassoc. While it can handle something 0<=A<=30|A==32|A==34.

> So, I believe cswitch needs to handle these cases
> too and consider it in the decision whether to use const array loads or
> bittest or if tree.

Right now, it differentiates in between const array loads and if tree. Usage of bittest
is probably situation which switch lowering can be taught.

Martin

> 
> 	Jakub
>