[12] RFR(M): 8210215: C2 should optimize trichotomy calculations

[John Rose]

On Sep 26, 2018, at 1:25 AM, Tobias Hartmann <tobias.hartmann at oracle.com> wrote:
> 
> Hi John,
> 
> thanks for looking at this again!
> 
> On 26.09.2018 01:57, John Rose wrote:
>> `res[9][9]` should be `res[illegal+1][illegal+1]` and should have rows and columns for `never`
>> (code smell:  `9` is a naked constant; makes it hard to tell your table is out of date)
> 
> Right, I've updated the table.

Thanks.  I went over the table item by item and couldn't find a bug.

> 
>> In the test cases `compare1` has `(a < b) ? -1 : (a == b) ? 0 : 1`.
>> Shouldn’t you also test `(a < b) ? -1 : (a <= b) ? 0 : 1`?
>> And similarly, for other cases where the second test overlaps
>> with the first.
> 
> I did not add tests for all the 6² operator combinations but I think more overlapping tests won't
> hurt. I've added
> 
> (a < b)  ? -1 : (a <= b) ?  0 :  1;
> (a > b)  ?  1 : (a >= b) ?  0 : -1;
> (a == b) ?  0 : (a <= b) ? -1 :  1;
> (a == b) ?  0 : (a >= b) ?  1 : -1;
> 
> and verified that all inlined comparisons fold.

That's better.  There aren't really 36 combinations that test trichotomy,
since some of them are just broken, like (x == y ? 0 : x == y ? 0 : 1).
Your compare11 to compare14 are like that.

The cases which truly do compute trichotomy are:

x == y ? 0 : x op y ? * : *  where op is one of < > <= >= (4 cases)
x < y ? -1 : x op y ? * : *  where op is one of > <= == != (4 cases)
x > y ? 1 : x op y ? * : *  where op is one of < >= == != (4 cases)

And that's 12 cases, which is a bit more than the 10 you have now.

The basic rule is that the first operator must be strict, and the
second operator may be anything other than the first operator
or its exact negative.

In addition, I think you should test a few more, to mix up the
order of the phi/region inputs.  There are two predicates, and
either can be inverted, but the second is already inverted in
the above cases.  So invert first predicate to get another 12
cases:

x != y ? (x op y ? * : *) : 0  where op is one of < > <= >= (4 cases)
x >= y ? (x op y ? * : *) : -1  where op is one of > <= == != (4 cases)
x <= y ? (x op y ? * : *) : 1  where op is one of < >= == != (4 cases)

Also, while you are at it, you could reverse the order of the
operands of the second comparison, so that the optimizer
sees "skewed" operand order when it must consider the first
and second comparisons.

x != y ? (y op x ? * : *) : 0  where op is one of < > <= >= (4 cases)
x >= y ? (y op x ? * : *) : -1  where op is one of < >= == != (4 cases)
x <= y ? (y op x ? * : *) : 1  where op is one of > <= == != (4 cases)

You could complete the square and add another 12 by combining
the two variations, but that's probably overkill.

I think that's good coverage, plus whatever negative tests you
want to add.

> 
> Here's the new webrev:
> http://cr.openjdk.java.net/~thartmann/8210215/webrev.01/
> 
> Thanks,
> Tobias