RFR: 8318306: java/util/Arrays/Sorting.java fails with "Array is not sorted at 8228-th position: 8251.0 and 8153.0"

[Srinivas Vamsi Parasa]

The goal of this PR is to address the failure of AVX512 sort test when the following JVM options are enabled (particularly `-XX:+DeoptimizeALot`) : 
`-Xcomp -ea -esa -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation -XX:+DeoptimizeALot`

### Description of the error: 
The sorting test (test/jdk/java/util/Arrays/Sorting.java) usually fails as shown below (from JBS bug report):

[Arrays.parallelSort] 'Test with check sum' length = 10000, random = C0FFEE, m = 128, CHAR STAGGER
[Arrays.parallelSort] 'Test with check sum' length = 10000, random = C0FFEE, m = 128, SHORT STAGGER
[Arrays.parallelSort] 'Test with check sum' length = 10000, random = C0FFEE, m = 128, FLOAT STAGGER
----------System.err:(25/1026)----------

*** TEST FAILED ***

Array is not sorted at 8228-th position: 8251.0 and 8153.0

java.lang.RuntimeException: Test failed
at Sorting.fail(Sorting.java:644)
at Sorting.checkSorted(Sorting.java:892)
at Sorting.checkSorted(Sorting.java:841)
at Sorting.checkWithCheckSum(Sorting.java:638)
at Sorting.testWithCheckSum(Sorting.java:438)
at Sorting.testBasic(Sorting.java:109)
at Sorting.testCore(Sorting.java:122)
at Sorting.testAll(Sorting.java:140)
at Sorting.testAll(Sorting.java:135)
at Sorting.main(Sorting.java:85)
at java.base/jdk.internal.reflect.DirectMethodHandleAccessor.invoke(DirectMethodHandleAccessor.java:103)
at java.base/java.lang.reflect.Method.invoke(Method.java:580)
at com.sun.javatest.regtest.agent.MainWrapper$MainTask.run(MainWrapper.java:138)
at java.base/java.lang.Thread.run(Thread.java:1570)

JavaTest Message: Test threw exception: java.lang.RuntimeException: Test failed
JavaTest Message: shutting down test

STATUS:Failed.`main' threw exception: java.lang.RuntimeException: Test failed

---------------------------------
### Reproducing the error:
#### (1) Using test/jdk/java/util/Arrays/Sorting.java:  
`jtreg -jdk:$JDK_HOME/build/linux-x86_64-server-slowdebug/jdk/ -Xcomp -ea -esa -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation -XX:+DeoptimizeALot -timeoutFactor:100 -verbose:all test/jdk/java/util/Arrays/Sorting.java`

This failure was also reproduced independently by the author of this PR as follows:
**example 1:**


[Arrays.parallelSort] 'Test with check sum' length = 10000, random = C0FFEE, m = 2048, DOUBLE REPEATED
[Arrays.parallelSort] 'Test with check sum' length = 10000, random = C0FFEE, m = 2048, INT    DUPLICATED
STDERR:
*** TEST FAILED ***
Array is not sorted at 3536-th position: 1007 and 715


**example 2:** 

[Arrays.parallelSort] 'Test with check sum' length = 10000, random = C0FFEE, m = 16, DOUBLE EQUAL
[Arrays.parallelSort] 'Test with check sum' length = 10000, random = C0FFEE, m = 16, INT    SAW
STDERR:
*** TEST FAILED ***
Array is not sorted at 1787-th position: 1788 and 670

#### (2) Using a micro: 
`java -Xcomp -ea -esa -XX:CompileThreshold=25 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation -XX:+DeoptimizeALot TestDeopt 1e-2 1000 250`


import java.util.Arrays;
import java.util.Random;

public class TestDeopt {

    public static void main(String[] args) throws Exception {
        int MAX = 2147483647; // 2^32 - 1
        float fraction = Float.parseFloat(args[0]);
        int size = (int) (fraction * MAX); // size is a fraction of the MAX size
        int iters = Integer.parseInt(args[1]); // number of iterations
        int max = args.length > 2 ? Integer.parseInt(args[2]) : -1 ; // max value for the array elements

        for (int i = 0; i < iters; i++) {
            boolean isSorted = runSort(size, max);
            System.out.println("Iteration " + i + ": is sorted? -> "+ isSorted);
            if (!isSorted) throw new Exception("Test Failed: Array is not properly sorted!");
        }
    }

    static boolean runSort(int size, int max) {
        int[] a = new int[size];
        int[] a_copy = new int[a.length];
        Random rand = new Random();
        for (int i=0; i< a.length; i++) a[i] =  max > 0 ? rand.nextInt(max) : rand.nextInt();
        // call parallel sort
        Arrays.parallelSort(a);
        // check if sorted
        boolean isSorted = true;
        for (int i = 0; i < (a.length -1); i++) isSorted = isSorted && (a[i] <= a[i+1]);
        return isSorted;
    }
}

----------------------------------------
### Suggested Fix: 

This appears to be a timing related issue as it's occuring when `Arrays.parallelSort()` is used along with `-XX:+DeoptimizeALot` VM option.
Also, **when the call to C2 stub happens, there is no guard when deoptimization happens**. The partition intrinsic used in the DualPivotQuicksort algorithm returns the `pivotIndices` (an int[] of size 2). Before the call to the C2 intrinsic stub, the array is being allocated and initialized as shown below:


 // create the pivotIndices array of type int and size = 2
    Node* size = intcon(2);
    Node* klass_node = makecon(TypeKlassPtr::make(ciTypeArrayKlass::make(T_INT)));
    pivotIndices = new_array(klass_node, size, 0);  // no arguments to push
    AllocateArrayNode* alloc = tightly_coupled_allocation(pivotIndices);
    guarantee(alloc != nullptr, "created above");

Thus, the proposed fix is to add the guards for deoptimization. Deoptimization can happen when calling into the runtime to allocate the array and then make sure to re-execute the bytecode if deoptimization happens. 


// src/hotspot/share/opto/library_call.cpp
{ PreserveReexecuteState preexecs(this);
    jvms()->set_should_reexecute(true);

  /*.... C2 intrinsic handling ...*/
}

-------------

Commit messages:
 - fix whitespace
 - add jtreg test to reproduce the failure
 - remove final check
 - 8318306: Fix for AVX512 sort test failure when DeoptimizeALot is enabled

Changes: https://git.openjdk.org/jdk/pull/16230/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=16230&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8318306
  Stats: 126 lines in 2 files changed: 92 ins; 14 del; 20 mod
  Patch: https://git.openjdk.org/jdk/pull/16230.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/16230/head:pull/16230

PR: https://git.openjdk.org/jdk/pull/16230