RFR: 8341781: Improve Min/Max node identities
Christian Hagedorn
chagedorn at openjdk.org
Thu Oct 10 09:06:13 UTC 2024
On Thu, 10 Oct 2024 02:59:14 GMT, Jasmine Karthikeyan <jkarthikeyan at openjdk.org> wrote:
> Hi all,
> This patch implements some missing identities for Min/Max nodes. It adds static type-based operand choosing for MinI/MaxI, such as the ones that MinL/MaxL use. In addition, it adds simplification for patterns such as `Max(A, Max(A, B))` to `Max(A, B)` and `Max(A, Min(A, B))` to `A`. These simplifications stem from the [lattice identity rules](https://en.wikipedia.org/wiki/Lattice_(order)#As_algebraic_structure). The main place I've seen this pattern is with MinL/MaxL nodes created during loop optimizations. Some examples of where this occurs include BigInteger addition/subtraction, and regex code. I've run some of the existing benchmarks and found some nice improvements:
>
> Baseline Patch
> Benchmark Mode Cnt Score Error Units Score Error Units Improvement
> BigIntegers.testAdd avgt 15 25.096 ± 3.936 ns/op 19.214 ± 0.521 ns/op (+ 26.5%)
> PatternBench.charPatternCompile avgt 8 453.727 ± 117.265 ns/op 370.054 ± 26.106 ns/op (+ 20.3%)
> PatternBench.charPatternMatch avgt 8 917.604 ± 121.766 ns/op 810.560 ± 38.437 ns/op (+ 12.3%)
> PatternBench.charPatternMatchWithCompile avgt 8 1477.703 ± 255.783 ns/op 1224.460 ± 28.220 ns/op (+ 18.7%)
> PatternBench.longStringGraphemeMatches avgt 8 860.909 ± 124.661 ns/op 743.729 ± 22.877 ns/op (+ 14.6%)
> PatternBench.splitFlags avgt 8 420.506 ± 76.252 ns/op 321.911 ± 11.661 ns/op (+ 26.6%)
>
> I've added some IR tests, and tier 1 testing passes on my linux machine. Reviews would be appreciated!
Your new test fails on Linux with `-XX:UseAVX=0`:
One or more @IR rules failed:
Failed IR Rules (8) of Methods (8)
----------------------------------
1) Method "public double compiler.c2.irTests.TestMinMaxIdentities.doubleMaxMax(double,double)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={"_#MAX_D#_", "1"}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- counts: Graph contains wrong number of nodes:
* Constraint 1: "(\\d+(\\s){2}(MaxD.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
2) Method "public double compiler.c2.irTests.TestMinMaxIdentities.doubleMaxMin(double,double)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={"_#MIN_D#_", "1", "_#MAX_D#_", "1"}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- counts: Graph contains wrong number of nodes:
* Constraint 1: "(\\d+(\\s){2}(MinD.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
* Constraint 2: "(\\d+(\\s){2}(MaxD.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
3) Method "public double compiler.c2.irTests.TestMinMaxIdentities.doubleMinMax(double,double)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={"_#MIN_D#_", "1", "_#MAX_D#_", "1"}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- counts: Graph contains wrong number of nodes:
* Constraint 1: "(\\d+(\\s){2}(MinD.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
* Constraint 2: "(\\d+(\\s){2}(MaxD.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
4) Method "public double compiler.c2.irTests.TestMinMaxIdentities.doubleMinMin(double,double)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={"_#MIN_D#_", "1"}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- counts: Graph contains wrong number of nodes:
* Constraint 1: "(\\d+(\\s){2}(MinD.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
5) Method "public float compiler.c2.irTests.TestMinMaxIdentities.floatMaxMax(float,float)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={"_#MAX_F#_", "1"}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- counts: Graph contains wrong number of nodes:
* Constraint 1: "(\\d+(\\s){2}(MaxF.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
6) Method "public float compiler.c2.irTests.TestMinMaxIdentities.floatMaxMin(float,float)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={"_#MIN_F#_", "1", "_#MAX_F#_", "1"}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- counts: Graph contains wrong number of nodes:
* Constraint 1: "(\\d+(\\s){2}(MinF.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
* Constraint 2: "(\\d+(\\s){2}(MaxF.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
7) Method "public float compiler.c2.irTests.TestMinMaxIdentities.floatMinMax(float,float)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={"_#MIN_F#_", "1", "_#MAX_F#_", "1"}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- counts: Graph contains wrong number of nodes:
* Constraint 1: "(\\d+(\\s){2}(MinF.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
* Constraint 2: "(\\d+(\\s){2}(MaxF.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
8) Method "public float compiler.c2.irTests.TestMinMaxIdentities.floatMinMin(float,float)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={"_#MIN_F#_", "1"}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- counts: Graph contains wrong number of nodes:
* Constraint 1: "(\\d+(\\s){2}(MinF.*)+(\\s){2}===.*)"
- Failed comparison: [found] 0 = 1 [given]
- No nodes matched!
Looks like we do not emit `Min/MaxF/D` nodes with `UseAVX=0`. I quickly checked the code and indeed, the intrinsics are only enabled if `UseAVX >= 1`:
https://github.com/openjdk/jdk/blob/16042556f394adfa93e54173944198397ad29dea/src/hotspot/cpu/x86/x86.ad#L1542-L1549
You can probably just update your tests to exclude IR matching for this setup. Maybe you also want to double check the other architectures.
-------------
PR Comment: https://git.openjdk.org/jdk/pull/21439#issuecomment-2404520133
More information about the hotspot-compiler-dev
mailing list