RFR (S): 8067014: LinearScan::is_sorted significantly slows down fastdebug builds' performance

[Filipp Zhinkin]

Hi all,

please review a fix for 8067014.

In certain cases (like -client -Xcomp) C1 compilation is very slow w/
fastdebug builds.
A place where we spent enormous amount of time is LinearScan::is_sorted method,
which simply verifies that a list that should be sorted is actually
sorted and that
both sorted and unsorted lists contains same intervals.

Unfortunately, to perform that check is_sorted iterates over a sorted
list for each
interval from an unsorted list and then iterates the unsorted list for
each interval
from then sorted one.

However, the sorted list may not contain NULL values [1][2], so we have to check
only that the sorted list contains all intervals from the unsorted
list and that sorted list's
length equals to count of non-NULL elements in unsorted list.
And as long as the sorted list does not contain NULLs we can use
binary search to
speed up LinearScan::is_sorted.

I've executed CTW with different JVM configs (-client -Xcomp, -server -Xcomp,
-server -Xcomp -XX:TieredStopAtLevel=3) to check that the fix will
actually speed up
LinearScan::is_sorted and linear scan time reduced twice, while total
C1 comp time
reduced by ~ 30%.

// I've also checked the case w/o a loop in lines 1462-1470, but also
w/ linear search
// and performance was somewhere between current implementation's
performance and
// performance of suggested fix.

Bug id: https://bugs.openjdk.java.net/browse/JDK-8067014
Webrev: http://cr.openjdk.java.net/~fzhinkin/8067014/webrev.00/
Testing: JTreg hotspot/test and jdk/test/java/lang/invoke tests, CTW

[1] http://hg.openjdk.java.net/jdk9/hs-comp/hotspot/file/d63ee67dbc90/src/share/vm/c1/c1_LinearScan.cpp#l1532
[2] http://hg.openjdk.java.net/jdk9/hs-comp/hotspot/file/d63ee67dbc90/src/share/vm/c1/c1_LinearScan.cpp#l286