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

[John Rose]

Reviewed.  I *think* you could actually allow floats, because your optimization
doesn't use all properties of trichotomy.  Specifically, you don't utilize the
"excluded middle" property:  If !(x<y) and !(x>y), you don't conclude x==y,
which is what NaNs would break.  Likewise, if !(x>=y) you don't conclude
x<y, and if !(x<=y) you don't conclude x>y.  (Um, am I right about all this?)

Excluded middles are deduced from the negations of related conditions,
but you don't actually work with negations; everything is normalized to
a positive condition, and then "merged" (logical-and-ed) to produce a
further positive condition.  This is why I think NaNs are probably OK.

If you do exclude floats, please add a comment like:
  // Floats don't exactly obey trichotomy.  To be on the safe side, don't transform their tests.
Of course, if you know a case where they actually break the logic,
document that, instead.  I have a feeling there is no such case.

Pointers don’t exactly obey trichotomy either; IIRC CmpP only produces NE and EQ states.
I think we use GT to encode NE, since we don’t have a proper NE (which is unfortunate).
If you see two pointers where !(p>q) and !(p==q) you can't conclude !(p<q),
because you are actually in a paradoxical state (not reached).  Well, I guess
that means it would be OK to conclude (p<q) but you'll confuse later phases
of the optimizer.

Bottom line:  Double-check the logic on pointers and floats, and do the right thing.

Either way, I'm very happy with what you have made here.  Thanks
for polishing the test to use non-constant test values.

— John

On Oct 9, 2018, at 10:29 AM, Tobias Hartmann <tobias.hartmann at oracle.com> wrote:
> 
> Hi,
> 
> I had an off thread discussion with John and he suggested the following changes in addition:
> - Use randomization for integer values in the test
> - Add some asserts and comments to improve readability
> - Don't apply optimization to floating point compares because they don't obey trichotomy laws (for
> example, NaN always compares to false)
> - Handle the case where the merge result is BoolTest::illegal (just for robustness, I haven't seen
> this ever during testing but it might show up when overflow tests mix with "normal" other tests)
> - While testing, I found that we also have to add a call to add_users_to_worklist(iff1) to make sure
> that the dead if is removed (otherwise we hit failures like JDK-8075922).
> 
> Incremental webrev:
> http://cr.openjdk.java.net/~thartmann/8210215/webrev.04_inc/
> 
> Full webrev:
> http://cr.openjdk.java.net/~thartmann/8210215/webrev.04/
> 
> Best regards,
> Tobias