RFR: JDK-8309410: [aarch64] Use pre-computed tables for logical immediates

[Thomas Stuefe]

On Sun, 4 Jun 2023 13:53:21 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> We compute the lookup tables for logical immediates on startup. We should use pre-computed tables instead.
>> 
>> If we do that, we don't even need the encoding->immediate lookup table, since that is only used during generation of the reverse lookup table. Since we hardcode the latter, we don't need to store the former.
>> 
>> I kept the old generator code around to test the hard-coded table (see gtest). To keep reviewing simple, the generator code itself lives still in the same place, mostly unchanged.
>> 
>> Note that we could shave off some more space for the reverse lookup table by storing immediate and encoding in separate arrays, since we now pay 16 bytes per entry due to alignment. We could also reduce the encoding from 32 bits to 16 bits. I did not do this to not overload this RFE.
>> 
>> Tests: manually ran tests on linux aarch64, OsX aarch64
>
> Hi Thomas,
> 
> The idea makes sense, but can't we do this with `constexpr` only? Looking at the intiailization code, this seems doable. Only issue would be sorting, as that'd have to be reimplemented as a contexpr function. No big table, no test that ensures that the table hasn't drifted away from code that's actually dead, seems like a big win!
> 
> Here's a sketch in constexpr which I think serves as a PoC that this could work: https://godbolt.org/z/o3PTbanYY
> 
> And for completeness here's the full source code replicated in this comment:
> 
> ```c++
> #include <cstdio>
> struct LITableStruct {
>     // couldn't bother with imports for sized (u)ints
>     static const unsigned int tbl_sz = 1 << 13;
>     int  LITable[tbl_sz];
>     unsigned long InvLITable[tbl_sz];
> 
>     // We can dereference pointers, compare and set them in constexpr
>     // (in other words, we can write a sorting routine)
>     constexpr void comp_and_swap(int* a, int* b) {
>         if (*a < *b) {
>             *a = *b;
>         }
>     }
>     // Magic incantation!
>     constexpr LITableStruct()
>     : LITable(), InvLITable() {
>         // comp and swap compiles
>         int a[2] = {0, 1};
>         comp_and_swap(&a[0], &a[1]);
>         comp_and_swap(&LITable[0], &LITable[255]);
> 
>         // loop and assign no problem
>         for (unsigned int idx = 0; idx < tbl_sz; idx++) {
>             LITable[idx] = LITable[0] + 255;
>             // just an if statement depending on some other state
>             // bit twiddling and other nonsense
>             if (LITable[0] == 1337 || LITable[67] & 5 | 37) {
>                 LITable[2500] = 73;
>             }
>         }
>     }
> };
> 
> static struct LITableStruct my_table{};
> int main() {
>     printf("Wow, an int: %d\n", my_table.LITable[0]);
> }

Hi @jdksjolen,

> The idea makes sense, but can't we do this with constexpr only?

Maybe , but
- I don't have much more time to spend on this; this was a little Sunday thing, but it shouldn't spiral out into a C++ research project (since I would have to babysit every compiler to make sure it generates what I assume it generates)
- I don't see why: we'd try to cajole the C++ compiler into generating a table that we just as well may write out plainly. Easier to understand, faster to compile, less reliance on the abilities of the C++ compiler. The end result is identical - a hard-coded table in the text segment.
- My variant is easy to review, since I did not change the old generator code. We could throw the testing code out at some point in the future.

Cheers, Thomas

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

PR Comment: https://git.openjdk.org/jdk/pull/14304#issuecomment-1575613640