RFR: 8325674: Constant fold across compares
Tobias Hartmann
thartmann at openjdk.org
Fri Feb 23 06:19:53 UTC 2024
On Wed, 14 Feb 2024 19:35:34 GMT, Joshua Cao <duke at openjdk.org> wrote:
> For example, `x + 1 < 2` -> `x < 2 - 1` iff we can prove that `x + 1` does not overflow and `2 - 1` does not overflow. We can always fold if it is an `==` or `!=` since overflow will not affect the result of the comparison.
>
> Consider this more practical example:
>
>
> public void foo(int[] arr) {
> for (i = arr.length - 1; i >= 0; --i) {
> blackhole(arr[i]);
> }
> }
>
>
> C2 emits a loop guard that looks `arr.length - 1 < 0`. We know `arr.length - 1` does not overflow because `arr.length` is positive. We can fold the comparison into `arr.length < 1`. We have to compute `arr.length - 1` computation if we enter the loop anyway, but we can avoid the subtraction computation if we never enter the loop. I believe the simplification can also help with stronger integer range analysis in https://bugs.openjdk.org/browse/JDK-8275202.
>
> Some additional notes:
> * there is various overflow checking code across `src/hotspot/share/opto`. I separated about the functions from convertnode.cpp into `type.hpp`. Maybe the functions belong somewhere else?
> * there is a change in Parse::do_if() to repeatedly apply GVN until the test is canonical. We need multiple iterations in the case of `C1 > C2 - X` -> `C2 - X < C1` -> `C2 < X` -> `X > C2`. This fails the assertion if `BoolTest(btest).is_canonical()`. We can avoid this by applying GVN one more time to get `C2 < X`.
> * we should not transform loop backedge conditions. For example, if we have `for (i = 0; i < 10; ++i) {}`, the backedge condition is `i + 1 < 10`. If we transform it into `i < 9`, it messes with CountedLoop's recognition of induction variables and strides.r
> * this change optimizes some of the equality checks in `TestUnsignedComparison.java` and breaks the IR checks. I removed those tests.
I executed some quick testing and `TestConstantFoldCompares::foldAddLtLong` fails with `-ea -esa -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation`:
1) Compilation of "public boolean compiler.c2.TestConstantFoldCompares.foldAddLtLong(int)":
> Phase "PrintIdeal":
AFTER: print_ideal
0 Root === 0 69 70 [[ 0 1 3 23 25 54 56 65 ]] inner
1 Con === 0 [[ ]] #top
3 Start === 3 0 [[ 3 5 6 7 8 9 11 ]] #{0:control, 1:abIO, 2:memory, 3:rawptr:BotPTR, 4:return_address, 5:compiler/c2/TestConstantFoldCompares:NotNull *, 6:int}
5 Parm === 3 [[ 36 ]] Control !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:-1 (line 242)
6 Parm === 3 [[ 36 ]] I_O !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:-1 (line 242)
7 Parm === 3 [[ 36 ]] Memory Memory: @BotPTR *+bot, idx=Bot; !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:-1 (line 242)
8 Parm === 3 [[ 70 69 36 ]] FramePtr !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:-1 (line 242)
9 Parm === 3 [[ 70 69 ]] ReturnAdr !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:-1 (line 242)
11 Parm === 3 [[ 24 ]] Parm1: int !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:-1 (line 242)
23 ConL === 0 [[ 36 53 ]] #long:42
24 ConvI2L === _ 11 [[ 36 ]] #long:minint..maxint:www !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:4 (line 242)
25 ConL === 0 [[ 36 ]] #long:1000
36 CallStaticJava === 5 6 7 8 1 (24 1 25 1 1 1 23 1 1 1 1 1 ) [[ 37 38 39 41 ]] # Static java.lang.Math::min long/half ( long, half, long, half ) Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242) !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
37 Proj === 36 [[ 43 ]] #0 !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
38 Proj === 36 [[ 70 43 69 48 ]] #1 !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
39 Proj === 36 [[ 70 69 ]] #2 Memory: @BotPTR *+bot, idx=Bot; !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
41 Proj === 36 [[ 53 ]] #5 !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
43 Catch === 37 38 [[ 44 45 ]] !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
44 CatchProj === 43 [[ 69 ]] #0 at bci -1 !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
45 CatchProj === 43 [[ 70 48 ]] #1 at bci -1 !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
48 CreateEx === 45 38 [[ 70 ]] #java/lang/Throwable (java/io/Serializable):NotNull * Oop:java/lang/Throwable (java/io/Serializable):NotNull * !jvms: Long::min @ bci:2 (line 2031) TestConstantFoldCompares::foldAddLtLong @ bci:8 (line 242)
53 AddL === _ 41 23 [[ 58 ]] !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:11 (line 242)
54 ConL === 0 [[ 58 ]] #long:100
56 ConI === 0 [[ 73 ]] #int:0
58 CmpL === _ 53 54 [[ 72 ]] !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:16 (line 242)
65 ConI === 0 [[ 73 ]] #int:1
69 Return === 44 38 39 8 9 returns 73 [[ 0 ]]
70 Rethrow === 45 38 39 8 9 exception 48 [[ 0 ]]
72 Bool === _ 58 [[ 73 ]] [ge]
73 CMoveI === _ 72 65 56 [[ 69 ]] #bool !orig=[71],[67] !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:24 (line 242)
1) Method "public boolean compiler.c2.TestConstantFoldCompares.foldAddLtLong(int)" - [Failed IR rules: 1]:
* @IR rule 1: "@compiler.lib.ir_framework.IR(phase={DEFAULT}, applyIfPlatformAnd={}, applyIfCPUFeatureOr={}, counts={}, applyIfPlatform={}, applyIfPlatformOr={}, failOn={"_#ADD#_"}, applyIfOr={}, applyIfCPUFeatureAnd={}, applyIf={}, applyIfCPUFeature={}, applyIfAnd={}, applyIfNot={})"
> Phase "PrintIdeal":
- failOn: Graph contains forbidden nodes:
* Constraint 1: "(\\d+(\\s){2}(Add(I|L|F|D|P).*)+(\\s){2}===.*)"
- Matched forbidden node:
* 53 AddL === _ 41 23 [[ 58 ]] !jvms: TestConstantFoldCompares::foldAddLtLong @ bci:11 (line 242)
-------------
PR Comment: https://git.openjdk.org/jdk/pull/17853#issuecomment-1960787614
More information about the hotspot-compiler-dev
mailing list