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

Fri Nov 1 13:21:47 UTC 2024

On Fri, 1 Nov 2024 10:29:10 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:
> 
>   apply more suggestions from Christian

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

> 341: //        This shows that p1 and p2 have a distance greater than the array size, and hence at least one of the two
> 342: //        pointers must be out of bounds. This contradicts our assumption (S1) and we are done.
> 343: //

Maybe add some separation here since this comment does not belong to `TraceMemPointer` but is rather a file header comment.
Suggestion:

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

> 383:     _distance(distance)
> 384:   {
> 385:     assert(_distance != min_jint, "given by condition S3 of MemPointer Lemma");

Suggestion:

    assert(_distance != min_jint, "given by condition (S3) of MemPointer Lemma");

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

> 387: 
> 388: public:
> 389:   MemPointerAliasing() : MemPointerAliasing(Unknown, 0) {}

Does not look like you call this constructor directly. You can therefore make it private as well:
Suggestion:

  MemPointerAliasing() : MemPointerAliasing(Unknown, 0) {}

public:

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

> 391:   static MemPointerAliasing make_unknown() {
> 392:     return MemPointerAliasing();
> 393:   }

Thinking about the comment above again, you can probably just remove the no-arg-constructor and simply do the following which I think is expressive enough:
Suggestion:

  static MemPointerAliasing make_unknown() {
    return MemPointerAliasing(Unknown, 0);
  }

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

> 398: 
> 399:   // Use case: exact aliasing and adjacency.
> 400:   bool is_always_at_distance(const jint distance) const {

The "always" seems to refer to the `Always` but it reads like we are just curious about the distance. Is `is_always_and_at_distance()` more clear?

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

> 427:       _variable(nullptr),
> 428:       _scale(NoOverflowInt::make_NaN()) {}
> 429:   MemPointerSummand(Node* variable, const NoOverflowInt scale) :

Can `scale` be passed as const reference? You will make a copy anyway when assigning it to `_scale`. The compiler would probably optimize this anyway but I guess it does not hurt to use a reference here directly.

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

> 436: 
> 437:   Node* variable() const { return _variable; }
> 438:   NoOverflowInt scale() const { return _scale; }

Not sure if you really require to create a new object here or if you could just pass it by const reference. The usages are only in `parse_decomposed_form()`. There you either add it together, from which you create a new `NoOverFlowInt` anyway, or you use it to create a new `MemPointerSummand` which will create it's own `scale` copy anyway. But maybe I'm also missing something here.

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

> 478:   // We limit the number of summands to 10. Usually, a pointer contains a base pointer
> 479:   // (e.g. array pointer or null for native memory) and a few variables.
> 480:   static const int SUMMANDS_SIZE = 10;

Looks like a best guess. Maybe you can also explicitly mention that here. Otherwise, it's unclear how you came up with the value 10.

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

> 495: 
> 496: private:
> 497:   MemPointerDecomposedForm(Node* pointer, const GrowableArray<MemPointerSummand>& summands, const NoOverflowInt con)

Same here, could `con` be passed by const reference since you create a copy from it anyway?

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

> 496: private:
> 497:   MemPointerDecomposedForm(Node* pointer, const GrowableArray<MemPointerSummand>& summands, const NoOverflowInt con)
> 498:     :_pointer(pointer), _con(con) {

Suggestion:

    : _pointer(pointer), _con(con) {

src/hotspot/share/opto/noOverflowInt.hpp line 28:

> 26: #define SHARE_OPTO_NOOVERFLOWINT_HPP
> 27: 
> 28: #include "utilities/globalDefinitions.hpp"

You do not seem to need this and thus could be removed
Suggestion:

src/hotspot/share/opto/noOverflowInt.hpp line 57:

> 55:   bool is_zero() const { return !is_NaN() && value() == 0; }
> 56: 
> 57:   friend NoOverflowInt operator+(const NoOverflowInt a, const NoOverflowInt b) {

Is it required to pass the arguments by value for the overloaded operators or would it be sufficient to pass them by reference (i.e. `const NoOverflowInt& a, const NoOverflowInt& b`)?

src/hotspot/share/opto/noOverflowInt.hpp line 90:

> 88: 
> 89:   NoOverflowInt abs() const {
> 90:     if (is_NaN()) { return make_NaN(); }

Why do you require a new `NaN` here and not simply return `*this`?

src/hotspot/share/opto/noOverflowInt.hpp line 95:

> 93:   }
> 94: 
> 95:   bool is_multiple_of(const NoOverflowInt other) const {

I think you can also pass `other` here by reference since you only query it:
Suggestion:

  bool is_multiple_of(const NoOverflowInt& other) const {

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

PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825759524
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825760604
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825763396
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825765294
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825768349
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825774196
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825778656
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825779509
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825781796
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825781191
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825758486
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825746670
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825749382
PR Review Comment: https://git.openjdk.org/jdk/pull/19970#discussion_r1825747742