RFR: 8335392: C2 MergeStores: enhanced pointer parsing [v11]

Fri Nov 1 10:04:35 UTC 2024

On Tue, 29 Oct 2024 18:29:04 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

>> **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-check...
>
> Emanuel Peter has updated the pull request incrementally with one additional commit since the last revision:
> 
>   fix distance assert

src/hotspot/share/opto/mempointer.cpp line 44:

> 42:   int traversal_count = 0;
> 43:   while (_worklist.is_nonempty()) {
> 44:     if (traversal_count++ > 1000) { return MemPointerDecomposedForm(pointer); }

Maybe also add a comment as below that we bail out if the graph is too complex.

src/hotspot/share/opto/mempointer.cpp line 48:

> 46:   }
> 47: 
> 48:   // Check for constant overflow.

To match bail out message below for scale:
Suggestion:

  // Bail out if there is a constant overflow.

src/hotspot/share/opto/mempointer.cpp line 52:

> 50: 
> 51:   // Sort summands by variable->_idx
> 52:   _summands.sort(MemPointerSummand::cmp_for_sort);

When you name the method something like `cmp_by_variable_idx`, then you could remove the comment.

src/hotspot/share/opto/mempointer.cpp line 58:

> 56:   int pos_get = 0;
> 57:   while (pos_get < _summands.length()) {
> 58:     MemPointerSummand summand = _summands.at(pos_get++);

Won't this create a new local object? So, if you were to change `summand`, then the `MemPointerSummand` inside `_summand` won't be updated (not the case here, though). Since you only are about to read from the object, I suggest to use a reference instead to avoid creation of a new local object.
Suggestion:

    const MemPointerSummand& summand = _summands.at(pos_get++);

src/hotspot/share/opto/mempointer.cpp line 304:

> 302: // Pre-Condition:
> 303: //   We assume that both pointers are in-bounds of their respective memory object.
> 304: //

Suggestion:

// Pre-Condition:
//   We assume that both pointers are in-bounds of their respective memory object. If this does
//   not hold, for example, with the use of Unsafe, then we would already have undefined behavior,
//   and we are allowed to do anything.

src/hotspot/share/opto/mempointer.hpp line 39:

> 37: //   We parse / decompose pointers into a linear form:
> 38: //
> 39: //     pointer = sum_i(scale_i * variable_i) + con

Maybe also change this to `SUM()` with a short explanation. Some like that:

Suggestion:

//   We parse / decompose pointers into a linear form:
//
//     pointer = SUM(scale_i * variable_i) + con
//
//   where SUM() adds all "scale_i * variable_i" for each i together.

src/hotspot/share/opto/mempointer.hpp line 403:

> 401: //
> 402: //   summand = scale * variable
> 403: //

For completness:
Suggestion:

// Summand of a MemPointerDecomposedForm:
//
//   summand = scale * variable
//
// where variable is a C2 node.

src/hotspot/share/opto/mempointer.hpp line 458:

> 456: // Decomposed form of the pointer sub-expression of "pointer".
> 457: //
> 458: //   pointer = sum(summands) + con

Suggestion:

//   pointer = SUM(summands) + con

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

PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825550519
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825551652
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825556318
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825570996
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825650181
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1824667743
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825554063
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825543969