RFR: 8316679: C2 SuperWord: wrong result, load should not be moved before store if not comparable

[Emanuel Peter]

On Fri, 22 Sep 2023 17:58:02 GMT, Vladimir Kozlov <kvn at openjdk.org> wrote:

>> **Context**
>> In `SuperWord::output`, we replace the scalars with vectors, pack by pack.
>> 
>> In [JDK-8052081](https://bugs.openjdk.org/browse/JDK-8052081) ([changeset](https://github.com/openjdk/jdk/commit/7764490363a5963212e040baa2b79946cf4487bf)) we added an optimization to move the memory state of a LoadVector as early as possible. We go up the memory chain, and skip any `StoreVector` that provably can never alias with  the `LoadVector` (provably no overlap).
>> 
>> **Details**
>> 
>> For this, we must understand the following function `VPointer::cmp`:
>> 
>> https://github.com/openjdk/jdk/blob/96781ba33d4717c8df2b9ba4cd5d66858cf5c2d1/src/hotspot/share/opto/vectorization.hpp#L110-L120
>> 
>> We have 4 possible states: `NotComparable` means that we cannot determine the relative offsets between the two memory addresses. We have no guarantee about aliasing at all. `Less` means that one address lies before the other, `Greater` means that it comes after. `Equal` means that the two memory regions have an overlap or are identical. To determine overlap, we must know the position of the pointer, as well as the `memory_size` of each memory reference. `VPointer::not_equal` is true iff we get states `Less` or `Greater` (we know there cannot be overlap). `VPointer::comparable` is true iff the state is `NotComparable`, hence we have no guarantee about aliasing.
>> 
>> **Problem**
>> 
>> Currently, there are 2 bugs in this "move-load-before-store" logic:
>> 1. [JDK-8316679](https://bugs.openjdk.org/browse/JDK-8316679) ([PR](https://github.com/openjdk/jdk/pull/15864)): We do not only skip the `not_equal` but also the `!comparable` case. However, when the two pointers are not comparable, that could be due to different invariants for example (see `TestMovingLoadBeforeStore.java`). The two pointers are not comparable, because we do not know the relative position, due to the invariants. But this exactly means that we cannot know at compile-time that there will not be aliasing. Thus, we cannot allow moving a load before such a store. Otherwise we may get wrong results. (*)
>> 2. [JDK-8316594](https://bugs.openjdk.org/browse/JDK-8316594) ([PR](https://github.com/openjdk/jdk/pull/15866)): Currently, we only compare the first element of the load-pack with the `StoreVector`. This is not correct, we need to compare all elements of the load-pack with the `StoreVector`. Otherwise it may be that the first element lays below/before the memory region of the `StoreVector` (Less), but the last el...
>
> Thank you for detailed explanation.
> What about case if one array is locally allocated and one comes from outside  - compiler knows they are different. But with this change loads will not be moved.  I understand that that if both comes from outside (as arguments or static reference) we can't guarantee that they are different. But if at least one of them is local and did not escape, we know they are different and can move pointers.
> May be it is separate RFE.

@vnkozlov The issue with knowing if different array references can alias (if they are the same) is something that is currently not implemented for SuperWord. But it could theoretically be solved outside of SuperWord, by putting them on separate memory slices. I think this is definately a separate RFE and would not just benefit SuperWord. Alternatively, we could do special logic inside SuperWord, determining if references can be proven not to be the same. Or even specualte / trap. The last one would be powerful, and probably the most beneficial in general. In most cases different array references are actually different arrays, but we cannot know that at compile time, because they are for example two arguments to a method.
What do you think?

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

PR Comment: https://git.openjdk.org/jdk/pull/15864#issuecomment-1732260176