RFR: 8263006: Add optimization for Max(*)Node and Min(*)Node [v2]

[Vladimir Kozlov]

On Fri, 16 Apr 2021 01:40:01 GMT, Wang Huang <whuang at openjdk.org> wrote:

>> * I optimize `max` and `min` by using these identities 
>>     - op (max(a,b) , min(a,b))=== op(a,b)
>>     - if op is commutable
>>     - example : 
>>       - max(a,b) + min(a,b))=== a + b // op = add
>>       - max(a,b) * min(a,b))=== a * b  // op = mul
>>       -  max( max(a,b) , min(a,b)))=== max(a,b) // op = max()
>>       - min( max(a,b) , min(a,b)))=== max(a,b) // op = min()
>> * Test case 
>>   ```java
>>   /*
>>    * Copyright (c) 2021, Huawei Technologies Co. Ltd. All rights reserved.
>>    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
>>    *
>>    * This code is free software; you can redistribute it and/or modify it
>>    * under the terms of the GNU General Public License version 2 only, as
>>    * published by the Free Software Foundation.
>>    *
>>    * This code is distributed in the hope that it will be useful, but WITHOUT
>>    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
>>    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
>>    * version 2 for more details (a copy is included in the LICENSE file that
>>    * accompanied this code).
>>    *
>>    * You should have received a copy of the GNU General Public License version
>>    * 2 along with this work; if not, write to the Free Software Foundation,
>>    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
>>    *
>>    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
>>    * or visit www.oracle.com if you need additional information or have any
>>    * questions.
>>    */
>>   package org.sample;
>>   
>>   import org.openjdk.jmh.annotations.Benchmark;
>>   import org.openjdk.jmh.annotations.*;
>>   
>>   import java.util.Random;
>>   import java.util.concurrent.TimeUnit;
>>   import org.openjdk.jmh.infra.Blackhole;
>>   
>>   @BenchmarkMode({Mode.AverageTime})
>>   @OutputTimeUnit(TimeUnit.MICROSECONDS)
>>   public class MyBenchmark {
>>   
>>       static int length = 100000;
>>       static double[] data1 = new double[length];
>>       static double[] data2 = new double[length];
>>       static Random random = new Random();
>>   
>>       static {
>>           for(int i = 0; i < length; ++i) {
>>             data1[i] = random.nextDouble();
>>             data2[i] = random.nextDouble();
>>           }
>>       }
>>   
>>       @Benchmark
>>       public void testAdd(Blackhole bh) {
>>         double sum = 0;
>>         for (int i = 0; i < length; i++) {
>>             sum += Math.max(data1[i], data2[i]) + Math.min(data1[i], data2[i]);
>>         }
>>         bh.consume(sum);
>>       }
>>   
>>       @Benchmark
>>       public void testMax(Blackhole bh) {
>>           double sum = 0;
>>           for (int i = 0; i < length; i++) {
>>               sum += Math.max(Math.max(data1[i], data2[i]), Math.min(data1[i], data2[i]));
>>           }
>>           bh.consume(sum);
>>       }
>>   
>>       @Benchmark
>>       public void testMin(Blackhole bh) {
>>           double sum = 0;
>>           for (int i = 0; i < length; i++) {
>>               sum += Math.min(Math.max(data1[i], data2[i]), Math.min(data1[i], data2[i]));
>>           }
>>           bh.consume(sum);
>>       }
>>   
>>       @Benchmark
>>       public void testMul(Blackhole bh) {
>>           double sum = 0;
>>           for (int i = 0; i < length; i++) {
>>               sum += (Math.max(data1[i], data2[i]) * Math.min(data1[i], data2[i]));
>>           }
>>           bh.consume(sum);
>>       }
>>   }
>>   ```
>> 
>> *  The result is listed here (aarch64):
>> 
>>   before:
>> 
>>   |Benchmark|                           Mode|  Samples|    Score|  Score error| Units|
>>   |---|                           ---|  ---|    ---|  --- | ---|
>>    |o.s.MyBenchmark.testAdd     |avgt     |   10  | 556.048     |   32.368       |  us/op |
>>  |  o.s.MyBenchmark.testMax  |   avgt     |   10   |543.065    |    54.221    |     us/op |
>>  |  o.s.MyBenchmark.testMin    | avgt        |10   |570.731 |       37.630   |      us/op |
>>   | o.s.MyBenchmark.testMul   |  avgt    |    10 |  531.906     |   20.518    |     us/op |
>>  
>>   after:
>> 
>>    |Benchmark|                           Mode|  Samples|    Score|  Score error| Units|
>>   |---|                           ---|  ---|    ---|  --- | ---|
>>    |  o.s.MyBenchmark.testAdd |      avgt     |     10   |  319.350  |         9.248     |      us/op |  
>>  |    o.s.MyBenchmark.testMax     |  avgt    |      10 |    356.138      |    10.736 |          us/op |  
>>  |    o.s.MyBenchmark.testMin  |     avgt      |    10 |    323.731  |        16.621     |      us/op |  
>>  |    o.s.MyBenchmark.testMul    |   avgt     |     10  |   338.458      |    23.755  |        us/op |
>> 
>> *  I have tested `NaN`  ` INFINITY` and `-INFINITY` and got same result (before/after)
>
> Wang Huang has updated the pull request incrementally with one additional commit since the last revision:
> 
>   adjust code style

Do you have a real example in Java applications which benefit from this optimization?
We should not add and **support** code which would never be used in real world.

Optimization will not work for Integer because of `_min` and `_max` intrinsic which generates `cmove`:
https://github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/library_call.cpp#L1806

I am not sure if this optimization will always work for float/double because of NaN values.

You need to verify results for all edge cases.

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

PR: https://git.openjdk.java.net/jdk/pull/3513