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

[Tobias Hartmann]

Hi,

please review the following patch:
https://bugs.openjdk.java.net/browse/JDK-8210215
http://cr.openjdk.java.net/~thartmann/8210215/webrev.00/

While analyzing performance results for the Value Types LW1 EA we got back from Doug Lea [1], I've
found that C2 is very bad at optimizing simple "trichotomic" comparisons of the form

 int compare(int a, int b) {
   return (a < b) ? -1 : (a == b) ? 0 : 1;
 }

when being inlined into a caller comparing the result against -1, 0 or 1.

For example, "compare(a, b) == 1" should be folded to "a > b" but currently isn't. Since this is a
very common pattern for sorting algorithms and since it will be even more common with value types,
it's crucial to optimize these. Out of the 66 comparisons in the jtreg test, C2 can optimize only
16. For all the other 50 tests, C2 emits two comparisons. With my patch, all comparisons are
optimized. The optimization improves the performance of Doug's microbenchmark by 5 - 12%.

The basic idea of the optimization is to search for two ifs that compare the same values while one
projection of the first if connects to the second if and all other projections connect to the same
region (potentially through an intermediate region). If two out of three projections to the region
then map to the same result value or control, we can replace the two ifs by a single if. The
implementation does this by first checking for one of the two shapes described in the
RegionNode::optimize_trichotomy comment which ensure that the comparisons have only two result
branches. We then merge the two ifs by computing the logical AND of the two tests (might be a
constant if the result is always false).

Thanks to John for pre-reviewing this change.

Thanks,
Tobias


[1] http://mail.openjdk.java.net/pipermail/valhalla-dev/2018-August/004879.html