jdk 8335392: C2 MergeStores: enhanced pointer parsing

Background I am introducing the MemPointer, for enhanced pointer parsing. For now, it replaces the much more limited ArrayPointer in MergeStores (see https://github.com/openjdk/jdk/pull/16245), but eventually it is supposed to be used widely in optimizations for pointer analysis: adjacency, aliasing, etc. I also plan to refactor the VPointer from auto-vectorization with it, and unlock more pointer patterns that way - possibly including scatter/gather.

Details

The MemPointer decomposes a pointer into the form pointer = con + sum_i(scale_i * variable_i) - a linear form with a sum of variables and scale-coefficients, plus some constant offset.

This form allows us to perform aliasing checks - basically we can check if two pointers are always at a constant offset. This allows us to answer many questions, including if two pointers are adjacent. MergeStores needs to know if two stores are adjacent, so that we can safely merge them.

More details can be found in the description in mempointer.hpp. Please read them when reviewing!

MemPointer is more powerful than the previous ArrayPointer: the latter only allows arrays, the former also allows native memory accesses, Unsafe and MemorySegement.

What this change enables

Before this change, we only allowed merging stores to arrays, where the store had to have the same type as the array element (StoreB on byte[], StoreI on int[]).

Now we can do:

Merging Unsafe stores to array. Including "mismatched size": e.g. putChar to byte[].
Merging Unsafe stores to native memory.
Merging MemorySegment: with array, native, ByteBuffer backing types.
- However: there is still some problem with RangeCheck smearing (a type of RC elimination) for the examples I have tried. Without RC's smeared, we can only ever merge 2 neighbouring stores. I hope we can improve this with better RangeCheck smearing. MemorySegment introduce checkIndexL, the long-variant of the RangeCheck. Normal array accesses only use the equivalent of checkIndex, the int-variant that we already optimize away much better.

Dealing with Overflows

We have to be very careful with overflows when dealing with pointers. For this, I introduced a NoOverflowInt. It allows us to do "normal" int operations on it, and tracks if there was ever an overflow. This way, we can do all overflow checks implicitly, and do not clutter the code with overflow-checks or - God forbid - forget overflow-checks.

Benchmarks

I added a few new benchmarks, to show the merging of Unsafe and native stores. We an see that 8 byte stores are now merged, and have the same performance as a long store. The same for 4 char stores that are merged into a single long store.

And here the whole MergeStores benchmark, master and with patch:

All old benchmarks remain in the level of noise. A few have heavy errors - the benchmark ran on my laptop and maybe something slowed down for a bit. We can see the significant speedup with all the unsafe benchmarks at the bottom.

This is great, now we can perform putChar even on byte[]. This was an issue we discovered in this PR https://github.com/openjdk/jdk/pull/19626.

Progress

[x] Change must be properly reviewed (1 review required, with at least 1 Reviewer)
[x] Change must not contain extraneous whitespace
[x] Commit message must refer to an issue

Issue

JDK-8335392: C2 MergeStores: enhanced pointer parsing (Enhancement - P4)

Reviewers

Vladimir Kozlov (@vnkozlov - Reviewer)

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/jdk.git pull/19970/head:pull/19970
$ git checkout pull/19970

Update a local copy of the PR:
$ git checkout pull/19970
$ git pull https://git.openjdk.org/jdk.git pull/19970/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 19970

View PR using the GUI difftool:
$ git pr show -t 19970

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/jdk/pull/19970.diff

Webrev

Link to Webrev Comment

Jul 01 '24 13:07 eme64

:wave: Welcome back epeter! A progress list of the required criteria for merging this PR into master will be added to the body of your pull request. There are additional pull request commands available for use with this pull request.

Jul 01 '24 13:07 bridgekeeper[bot]

@eme64 This change now passes all automated pre-integration checks.

ℹ️ This project also has non-automated pre-integration requirements. Please see the file CONTRIBUTING.md for details.

After integration, the commit message for the final commit will be:

8335392: C2 MergeStores: enhanced pointer parsing

Co-authored-by: Christian Hagedorn <[email protected]>
Reviewed-by: kvn, chagedorn

You can use pull request commands such as /summary, /contributor and /issue to adjust it as needed.

At the time when this comment was updated there had been 32 new commits pushed to the master branch:

7f8450cc511e22e3183092edfa3a37b39f133cff: 8343473: Update copyright year of AddmodsOption.java
b74652b5f4424419b36888514730ac7550f42a6b: 8343167: Unnecessary define checks in InterpreterRuntime after JDK-8199809
646d64e88003ef2a2e1960cef0cc59d1a97bb912: 8340307: Add explanation around MemorySegment:reinterpret regarding arenas
8d6cfba37fe641e35886fdba536f5b2f1709e87b: 8336267: Method and Constructor signature parsing can be shared on the root object
1f7d524fd3ecd932deb44b6fafdaa36c6bba4cb4: 8343437: ClassDesc.of incorrectly permitting empty names
895a7b64f01dec7248549b127875edcf006457cf: 8342967: Lambda deduplication fails with non-metafactory BSMs and mismatched local variables names
b41d713ff4157ebfed9da809c2ef970a3d1a6af6: 8343513: Forward declare Thread in mutexLocker.hpp
809030bfb2066805118dcd4326588bc224b78d3f: 8321500: javadoc rejects '@' in multi-line attribute value
7bca0af481e2ab1d9576fdf400079b4e4ca91e89: 8343128: PassFailJFrame.java test result: Error. Bad action for script: build}
f69b6016d6160d7093c32a806c60d85cf9a02222: 8343188: Investigate ways to simplify MemorySegment::ofBuffer
... and 22 more: https://git.openjdk.org/jdk/compare/f77a5144a12fc31bad8b672a3cc9caa688d78e72...master

As there are no conflicts, your changes will automatically be rebased on top of these commits when integrating. If you prefer to avoid this automatic rebasing, please check the documentation for the /integrate command for further details.

➡️ To integrate this PR with the above commit message to the master branch, type /integrate in a new comment.

Jul 01 '24 13:07 openjdk[bot]

@eme64 The following label will be automatically applied to this pull request:

hotspot-compiler

When this pull request is ready to be reviewed, an "RFR" email will be sent to the corresponding mailing list. If you would like to change these labels, use the /label pull request command.

Jul 01 '24 13:07 openjdk[bot]

@eme64 this pull request can not be integrated into master due to one or more merge conflicts. To resolve these merge conflicts and update this pull request you can run the following commands in the local repository for your personal fork:

git checkout JDK-8335392-MemPointer
git fetch https://git.openjdk.org/jdk.git master
git merge FETCH_HEAD
# resolve conflicts and follow the instructions given by git merge
git commit -m "Merge master"
git push

Jul 02 '24 09:07 openjdk[bot]

@eme64 This pull request has been inactive for more than 8 weeks and will be automatically closed if another 8 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!

Oct 10 '24 16:10 bridgekeeper[bot]

Webrevs

Oct 17 '24 11:10 mlbridge[bot]

For me it is confusing to call pointer = con + sum_i(scale_i * variable_i) as "pointer" unless it is Unsafe address which has base address as constant. It misses base address. All out pointer types are correspond to an address of some object in Java heap, out of heap, VM's object or some native (C heap) VM object. This looks like address_offset, displacement, ...

Oct 17 '24 21:10 vnkozlov

@vnkozlov thanks for looking at this!

For me it is confusing to call pointer = con + sum_i(scale_i * variable_i) as "pointer" unless it is Unsafe address which has base address as constant. It misses base address. All out pointer types are correspond to an address of some object in Java heap, out of heap, VM's object or some native (C heap) VM object. This looks like address_offset, displacement, ...

I added some explanations and examples in the code now. But essencially, any base is just another variable, with scale = 1. Just for adjacency, it does not matter if the variable is some offset or a base address. Of course, there may be some other aliasing analysis tasks that do care if it is an array or not. We can add such detection later, if we need it.

Oct 18 '24 08:10 eme64

I added this section to the desctiption above.

Benchmarks

I added a few new benchmarks, to show the merging of Unsafe and native stores. We an see that 8 byte stores are now merged, and have the same performance as a long store. The same for 4 char stores that are merged into a single long store.

Oct 18 '24 10:10 eme64

I added this to the desciption:

What this change enables

Before this change, we only allowed merging stores to arrays, where the store had to have the same type as the array element (StoreB on byte[], StoreI on int[]).

Now we can do:

Merging Unsafe stores to array. Including "mismatched size": e.g. putChar to byte[]. Merging Unsafe stores to native memory. Merging MemorySegment: with array, native, ByteBuffer backing types.

Oct 18 '24 13:10 eme64

@vnkozlov thanks for the review! @dean-long thanks for the comments. I addressed all your comments.

Oct 22 '24 07:10 eme64

OverflowInt updates look good. (That's the only part I reviewed.)

Oct 23 '24 09:10 dean-long

@dean-long ok, thanks for the NoOverflowInt review :blush:

In that case, I think we need yet another reviewer @vnkozlov , right?

Oct 23 '24 13:10 eme64

BTW, another place where a user-defined class like NoOverflowInt might be useful is compiler invocation counters. We store them as integers in various places, increment and scale them, check for saturation, and convert them to floating point for comparison. The last time I tried to fix a bug in that area, I was wishing for a better way to propagate integer saturation through multiple operations (like how NoOverflowInt uses NaN), and was tempted to change everything to floating point so I could use infinity.

Oct 25 '24 00:10 dean-long

@chhagedorn thanks for all your comments. I addressed all now. I had to fix that one assert in MemPointerAliasing constructor - it was wrong and I added regression tests for it now :blush:

Looking forward to the next part of your review!

Oct 29 '24 18:10 eme64

FYI: I ran performance testing, with no significant changes detected. That was expected (this is a niche optimization, that probably does not feature prominently in the benchmarks - especially Unsafe stores are not that prevalent). Still, this change is justified by my added micro-benchmarks.

Oct 31 '24 09:10 eme64

In the toString scenario of Integer/Long and the StringBuilder.appendNull/appendBoolean scenario, we can refactor the code to optimize based on unsafe mergestore. I am waiting for this PR to be merged, and then continue to complete PR #19626

Nov 01 '24 04:11 wenshao

@wenshao Thanks for your patience. @chhagedorn is doing a thorough review right now, so I hope we are only a few days away from integration ;)

Nov 01 '24 07:11 eme64

/contributor add chhagedorn

You spent enough time on this already ;)

Nov 04 '24 10:11 eme64

@eme64 chhagedorn was not found in the census.

Syntax: /contributor (add|remove) [@user | openjdk-user | Full Name <email@address>]. For example:

/contributor add @openjdk-bot
/contributor add duke
/contributor add J. Duke <[email protected]>

User names can only be used for users in the census associated with this repository. For other contributors you need to supply the full name and email address.

Nov 04 '24 10:11 openjdk[bot]

/contributor add @chhagedorn

Nov 04 '24 10:11 eme64

@eme64 Contributor Christian Hagedorn <[email protected]> successfully added.

Nov 04 '24 10:11 openjdk[bot]

/contributor add chhagedorn

You spent enough time on this already ;)

Thanks Emanuel, I highly appreciate that :-)

Nov 04 '24 11:11 chhagedorn

@chhagedorn I filed https://bugs.openjdk.org/browse/JDK-8343536 to track the cases in TestMergeStoresMemorySegment.java that do not optimize as hoped for.

Nov 04 '24 11:11 eme64

@chhagedorn I addressed all your review suggestions. Thank you very much for the in-depth review :)

Nov 04 '24 11:11 eme64

@vnkozlov Would you like to re-review? If I don't hear anything then I'll integrate tomorrow.

Nov 04 '24 12:11 eme64

Thanks @chhagedorn for the extensive reviews and collaboration on improving the proofs :blush: Thanks @vnkozlov for the approval.

I did an offline merge and testing (to avoid requiring a re-approval) - all looks good.

/integrate

Nov 05 '24 11:11 eme64

Going to push as commit f3671beefb3ff07441a905e25619f0d1a0a2fe15. Since your change was applied there have been 47 commits pushed to the master branch:

4fc6d4135e795d18a024a6035908f380b81082d1: 8341194: [REDO] Implement C2 VectorizedHashCode on AArch64
abf2dc7128fc0644e85bca32d8f3beacc876cecb: 8343298: Improve stability of runtime/cds/DeterministicDump.java test
dafa2e55adb6b054c342d5e723e51087d771e6d6: 8343124: Tests fails with java.lang.IllegalAccessException: class com.sun.javatest.regtest.agent.MainWrapper$MainTask cannot access
0f7dd98d9d546e0fc2c7b1df779cef35e5b5852c: 8251926: PPC: Remove an unused variable in assembler_ppc.cpp
cd91a44500e83f84e8e9ecc2760552dd18860842: 8343549: SeededSecureRandomTest needn't be in a package
20f3aaff4470745ff082bc562f4e4e72044090b2: 8343471: RISC-V: compiler/cpuflags/TestAESIntrinsicsOnUnsupportedConfig.java fails after JDK-8334999
67907d5e8985ee47ddadb51dae1220404a18dd47: 8343500: Optimize ArrayClassDescImpl computeDescriptor
714472d8a5b3d16b870bc272ce8664cd62733857: 8341798: Fix ExceptionOccurred in jdk.jdwp.agent
825ceb16b2e2347a4d9c1977d9a3a2da1296d5fe: 8341796: Fix ExceptionOccurred in jdk.hotspot.agent
8b4749713c63a08e502845ed5d0a0236822018cd: 8331682: Slow networks/Impatient clients can potentially send unencrypted TLSv1.3 alerts that won't parse on the server
... and 37 more: https://git.openjdk.org/jdk/compare/f77a5144a12fc31bad8b672a3cc9caa688d78e72...master

Your commit was automatically rebased without conflicts.

Nov 05 '24 11:11 openjdk[bot]

@eme64 Pushed as commit f3671beefb3ff07441a905e25619f0d1a0a2fe15.

:bulb: You may see a message that your pull request was closed with unmerged commits. This can be safely ignored.

Nov 05 '24 11:11 openjdk[bot]

@eme64 How do I use the TraceMergeStores option? It worked before, but now it gives an error.

build/macosx-aarch64-server-fastdebug/jdk/bin/java -Dtest=appendNullLatin1 -XX:+TraceMergeStores

output

Unrecognized VM option 'TraceMergeStores'
Did you mean '(+/-)MergeStores'?
Error: Could not create the Java Virtual Machine.
Error: A fatal exception has occurred. Program will exit.

Nov 05 '24 16:11 wenshao

jdk jdk copied to clipboard

8335392: C2 MergeStores: enhanced pointer parsing

Progress

Issue

Reviewers

Reviewing

Webrev

Webrevs

jdk
jdk copied to clipboard