jdk 8319822: Use a linear-time algorithm for assert_different

At the present time, assert_different_registers() uses an O(N**2) algorithm in assert_different_registers(). We can utilize RegSet to do it in O(N) time. This would be a useful optimization for all builds with assertions enabled.

In addition, it would be useful to be able to static_assert different registers.

Also, I've taken the opportunity to expand the maximum size of a RegSet to 64 on 64-bit platforms.

I also fixed a bug: sometimes noreg is passed to assert_different_registers(), but it may only be passed once or a spurious assertion is triggered.

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-8319822: Use a linear-time algorithm for assert_different_registers() (Enhancement - P4)

Reviewers

Stefan Karlsson (@stefank - Reviewer)

Reviewing

Using git

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

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

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 16617

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

Using diff file

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

Webrev

Link to Webrev Comment

Nov 10 '23 15:11 theRealAph

:wave: Welcome back aph! 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.

Nov 10 '23 15:11 bridgekeeper[bot]

@theRealAph 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.

Nov 10 '23 15:11 openjdk[bot]

Webrevs

Nov 10 '23 15:11 mlbridge[bot]

The build fails on Windows:

[2023-11-13T08:04:09,465Z] c:\sb\prod\1699862498\workspace\open\src\hotspot\cpu\x86\register_x86.hpp(402): error C2220: the following warning is treated as an error
[2023-11-13T08:04:09,465Z] c:\sb\prod\1699862498\workspace\open\src\hotspot\cpu\x86\register_x86.hpp(402): warning C4267: 'argument': conversion from 'size_t' to 'int', possible loss of data
[2023-11-13T08:04:09,465Z] c:\sb\prod\1699862498\workspace\open\src\hotspot\cpu\x86\register_x86.hpp(415): warning C4267: 'argument': conversion from 'size_t' to 'int', possible loss of data
[2023-11-13T08:04:09,465Z] lib/CompileGtest.gmk:94: recipe for target '/cygdrive/c/sb/prod/1699862498/workspace/build/windows-x64-open/hotspot/variant-server/libjvm/gtest/objs/static/BUILD_GTEST_LIBJVM_pch.obj' failed
[2023-11-13T08:04:09,465Z] make[3]: *** [/cygdrive/c/sb/prod/1699862498/workspace/build/windows-x64-open/hotspot/variant-server/libjvm/gtest/objs/static/BUILD_GTEST_LIBJVM_pch.obj] Error 1

Nov 13 '23 08:11 TobiHartmann

The build fails on Windows:

Argh! Thanks.

Nov 13 '23 09:11 theRealAph

I started to review the patch and was wondering if this could be simplify to something like this?: https://github.com/stefank/jdk/commit/f38c791793440b899ce6c4c9723470a5d4b18050

I tested this with this small section of temporary static_asserts: https://github.com/stefank/jdk/commit/30da4d6abeee14e4e4f44034295f1bb0ad2e3016

Unfortunately, that didn't compile and I had make this change to get it to work: https://github.com/stefank/jdk/commit/d6bda1a25e297865fd6b5da21184273d8825b922

Nov 13 '23 10:11 stefank

I started to review the patch and was wondering if this could be simplify to something like this?: stefank@f38c791

Sure, it could be done. This is a minor efficiency tweak.

Nov 15 '23 16:11 theRealAph

I ran into a case where I was doing assert_different_registers() on base() and index() from an Address. How hard would it be to have assert_different_registers() support an Address as an argument?

Nov 15 '23 22:11 dean-long

The build fails on Windows:

Argh! Thanks.

I'm afraid the compiler warnings on Windows still exist. See the GHA test results. Besides, the copyright year of register.hpp file should be updated to 2023.

Nov 16 '23 02:11 shqking

I ran into a case where I was doing assert_different_registers() on base() and index() from an Address. How hard would it be to have assert_different_registers() support an Address as an argument?

Quite tricky, partly because Address isn't a shared type. I would have thought it best to make it explicit anyway, with something like different_registers(a.base(), a.index(), rsi, ...); We'd need to make sure that base() and index() return noreg whenever the Address is wrong, e.g. a literal.

Nov 17 '23 15:11 theRealAph

I started to review the patch and was wondering if this could be simplify to something like this?: stefank@f38c791

Sure, it could be done. This is a minor efficiency tweak.

It tested the build performance before this PR, with the patch in this PR, and my simplified version. I can't see any performance difference on my MacBook M1. Is there any platform where this makes a bigger difference?

Edit: I realize that since this doesn't always boil down to a constexpr, then the run time might be more interesting than the build time.

Nov 20 '23 10:11 stefank

From the summary:

In addition, it would be useful to be able to static_assert different registers.

As mentioned in https://github.com/openjdk/jdk/pull/16617#issuecomment-1807933886 this doesn't work unless we make the proposed small tweak. Do you want to make it in this PR, or should I propose that in a separate PR?

Nov 20 '23 10:11 stefank

I started to review the patch and was wondering if this could be simplify to something like this?: stefank@f38c791

Sure, it could be done. This is a minor efficiency tweak.

It tested the build performance before this PR, with the patch in this PR, and my simplified version. I can't see any performance difference on my MacBook M1. Is there any platform where this makes a bigger difference?

Edit: I realize that since this doesn't always boil down to a constexpr, then the run time might be more interesting than the build time.

I don't think you'll be able to measure such a tiny difference in build performance, especially given all the other thiungs that are going on, and especially on a Great Big Out-Of-Order machine. But at runtime, the three-operand check can be performed with just three comparisons. I'm not fixated on this, though, and I can take the special cases out.

Nov 27 '23 10:11 theRealAph

Unfortunately, that didn't compile and I had make this change to get it to work: stefank@d6bda1a

Done, thanks and sorry for the delay.

Nov 27 '23 12:11 theRealAph

@theRealAph This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 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!

Dec 25 '23 18:12 bridgekeeper[bot]

@theRealAph This pull request has been inactive for more than 8 weeks and will now be automatically closed. If you would like to continue working on this pull request in the future, feel free to reopen it! This can be done using the /open pull request command.

Feb 14 '24 08:02 bridgekeeper[bot]

/open

May 10 '24 13:05 theRealAph

@theRealAph This pull request is now open

May 10 '24 14:05 openjdk[bot]

@theRealAph 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:

8319822: Use a linear-time algorithm for assert_different_registers()

Reviewed-by: kbarrett, stefank, stuefe

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 228 new commits pushed to the master branch:

8d3de45f4dfd60dc4e2f210cb0c085fcf6efb8e2: 8325168: JShell should support Markdown comments
9ee741d1e55c2520b28a5e3ca0604073d81d0059: 8332015: since-checker - Add @ since tags to jdk.httpserver
0f4154a9e9805534595feccc53a4a1abf20f99ae: 8331193: Return references when possible in GrowableArray
64bbae75121ccf80c02a0960e2db62eb558052e6: 8333394: C2: assert(bol->is_Opaque4() || bol->is_OpaqueInitializedAssertionPredicate()) failed: Opaque node of non-null-check or of Initialized Assertion Predicate
c7495fb35d7736815d5777ab776ace013f9d50b5: 8333444: Parallel: Inline PSParallelCompact::mark_obj
454660d361e39f362ff0e10a5c2389af910cca23: 8332900: RISC-V: refactor nativeInst_riscv.cpp and macroAssembler_riscv.cpp
67d6f3ca9e8d1312c9e3a85dbe19903619f59064: 8332905: C2 SuperWord: bad AD file, with RotateRightV and first operand not a pack
ca3072635215755766575b4eb70dc6267969a550: 8332866: Crash in ImageIO JPEG decoding when MEM_STATS in enabled
29e10e4582c1a844a6db4c42ba01bd1d6d4dfd52: 8332547: Unloaded signature classes in DirectMethodHandles
c7d2a5c1c4e86955100f4c40170dc25222abd07f: 8314070: javax.print: Support IPP output-bin attribute extension
... and 218 more: https://git.openjdk.org/jdk/compare/39a55e97799b5328da85aaa66c8d23175b305691...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.

May 10 '24 14:05 openjdk[bot]

I started to review the patch and was wondering if this could be simplify to something like this?: stefank@f38c791

I tested this with this small section of temporary static_asserts: stefank@30da4d6

Unfortunately, that didn't compile and I had make this change to get it to work: stefank@d6bda1a

OK, so I'm not going to do that, then.

May 10 '24 14:05 theRealAph

⚠️ @theRealAph This pull request contains merges that bring in commits not present in the target repository. Since this is not a "merge style" pull request, these changes will be squashed when this pull request in integrated. If this is your intention, then please ignore this message. If you want to preserve the commit structure, you must change the title of this pull request to Merge <project>:<branch> where <project> is the name of another project in the OpenJDK organization (for example Merge jdk:master).

May 10 '24 14:05 openjdk[bot]

From the summary:

In addition, it would be useful to be able to static_assert different registers.

As mentioned in #16617 (comment) this doesn't work unless we make the proposed small tweak. Do you want to make it in this PR, or should I propose that in a separate PR?

Let's do it separately. I would, but GCC has a very relaxed attitude to static_assert which means I can't test anything here. Everything to do with static_assert just seems to work.

May 10 '24 16:05 theRealAph

Exhuming this one after a long time. Please review, thanks.

May 10 '24 16:05 theRealAph

I started to review the patch and was wondering if this could be simplify to something like this?: stefank@f38c791

Sure, it could be done. This is a minor efficiency tweak.

It tested the build performance before this PR, with the patch in this PR, and my simplified version. I can't see any performance difference on my MacBook M1. Is there any platform where this makes a bigger difference?

Edit: I realize that since this doesn't always boil down to a constexpr, then the run time might be more interesting than the build time.

You won't see very much, if any, because other things dominate. The main advantage, going forward, is that much of this can be constexpr'd, once I find out how to test on Windows.

May 28 '24 15:05 theRealAph

Just a code-style review.

Question: could there be some sort of regression test for this, with different examples and edge cases?

I have no idea, really. assert_different_registers is used all over the place, and I'm going for bootcycle and tier1.

May 31 '24 16:05 theRealAph

Just a code-style review. Question: could there be some sort of regression test for this, with different examples and edge cases?

I have no idea, really. assert_different_registers is used all over the place, and I'm going for bootcycle and tier1.

You could write a death test gtest. Like this:

TEST_VM_ASSERT_MSG(AssemblerAArch64, assert_different_regs, ".*Multiple uses of register: c_rarg0.*") {
  Register reg1 = r0;
  Register reg2 = r0;
  assert_different_registers(reg1, reg2);
}

Jun 01 '24 06:06 tstuefe

Just a code-style review. Question: could there be some sort of regression test for this, with different examples and edge cases?

I have no idea, really. assert_different_registers is used all over the place, and I'm going for bootcycle and tier1.

You could write a death test gtest. Like this:
TEST_VM_ASSERT_MSG(AssemblerAArch64, assert_different_regs, ".*Multiple uses of register: c_rarg0.*") {
  Register reg1 = r0;
  Register reg2 = r0;
  assert_different_registers(reg1, reg2);
}

I could, but I don't think there's much point. assert_different_registers() is used so much that it'll get thoroughly tested in the positive cases, at least. Do you think this is important?

Jun 03 '24 08:06 theRealAph

/integrate

Jun 05 '24 17:06 theRealAph

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

f73922b27d126314fc3127ee25aa40b6258c8a6b: 8333235: vmTestbase/nsk/jdb/kill/kill001/kill001.java fails with C1
5dcb7a627e1cfb360719a25722588180e5de9d09: 8160755: bug6492108.java test fails with exception Image comparison failed at (0, 0) for image 4 in GTK L&F
438121be6bdb085fa13ad14ec53b09ecdbd4757d: 8332785: Replace naked uses of UseSharedSpaces with CDSConfig::is_using_archive
d7d1afb0a84e771870e9f43e08c4a63c8fdccdd9: 8206447: InflaterInputStream.skip receives long but it's limited to Integer.MAX_VALUE
7acfba288ff4d1f43cc36506b2bd2d32107b00c2: 8327650: Test java/nio/channels/DatagramChannel/StressNativeSignal.java timed out
c5c0867881a43c81e88453274ac12e45454685a4: 8333252: C2: assert(assertion_predicate_has_loop_opaque_node(iff)) failed: must find OpaqueLoop* nodes
d85b0ca5cdc1820a886c46bf555b2051fed7f167: 8332457: Examine startup overheads from JDK-8294961
326dbb1b139dd1ec1b8605339b91697cdf49da9a: 8312436: CompletableFuture never completes when 'Throwable.toString()' method throws Exception
9a8096feb82991784cabede823f0248fe2f41e53: 8330047: ASAN build error with gcc 13
6882b381e8662b5c134d3a1868c357eeb3523ea8: 8333590: UnmodifiableHeaders.toString() returns a value that represents empty headers
... and 251 more: https://git.openjdk.org/jdk/compare/39a55e97799b5328da85aaa66c8d23175b305691...master

Your commit was automatically rebased without conflicts.

Jun 05 '24 17:06 openjdk[bot]

@theRealAph Pushed as commit 9b3694c4fcc3cf46c0d827427ae8aadb477e8e22.

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

Jun 05 '24 17:06 openjdk[bot]