RFR: 8325252: C2 SuperWord: refactor the packset

[Emanuel Peter]

On Mon, 25 Mar 2024 10:04:13 GMT, Christian Hagedorn <chagedorn at openjdk.org> wrote:

>> I'm refactoring the packset, separating the details of packset-manupulation from the SuperWord algorithm.
>> 
>> Most importantly: I split it into two classes: `PairSet` and `PackSet`.
>> `combine_pairs_to_longer_packs` converts the first into the second.
>> 
>> I was able to simplify the combining, and remove the pack-sorting.
>> I now walk "pair-chains" directly with `PairSetIterator`. One such pair-chain is equivalent to a pack.
>> 
>> I moved all the `filter / split` functionality to the `PackSet`, which allows hiding a lot of packset-manipulation from the SuperWord algorithm.
>> 
>> I ran into some issues when I was extending the pairset in `extend_pairset_with_more_pairs_by_following_use_and_def`:
>> Using the PairSetIterator changed the order of extension, and that messed with the packing heuristic, and quite a few examples did not vectorize, because we would pack up the wrong 2 nodes out of a choice of 4 (e.g. we would pack `ac bd` instead of `ab cd`). Hence, I now still have to keep the insertion order for the pairs, and this basically means we are extending with a BFS order. Maybe this issue can be removed, if I improve the packing heuristic with some look-ahead expansion approach (but that is for another day [JDK-8309908](https://bugs.openjdk.org/browse/JDK-8309908)).
>> 
>> But since I already spent some time on some of the packing heuristic (reordering and cost estimate), I did a light refactoring, and added extra tests for MulAddS2I.
>> 
>> More details are described in the annotations in the code.
>
> src/hotspot/share/opto/superword.cpp line 1232:
> 
>> 1230: //    use1->in(i) == def1 || use2->in(def2)   ->    use1->in(i) == def1 && use2->in(def2)
>> 1231: //
>> 1232: // 3: Add/Mul (use1, use2): we can try to swap edges:
> 
> Is it not required for other nodes?

We can only do it for associative nodes like `Mul / Add`, and of course all the nodes that are subclasses of those (e.g. Max, Min, Or, etc). I can improve the comment, since that may not be immediately clear to the reader.

> src/hotspot/share/opto/superword.cpp line 1363:
> 
>> 1361:   for (PairSetIterator pair(_pairset); !pair.done(); pair.next()) {
>> 1362:     Node* s1 = pair.left();
>> 1363:     Node* s2 = pair.right();
> 
> Maybe you also want to name them `left` and `right` instead of `s1` and `s2`.

Just specifically here, or everywhere in the code?

> src/hotspot/share/opto/superword.cpp line 1364:
> 
>> 1362:     Node* s1 = pair.left();
>> 1363:     Node* s2 = pair.right();
>> 1364:     if (_pairset.is_left_in_a_left_most_pair(s1)) {
> 
> Should we also assert here that `pack == nullptr` before creating the new list?

Good idea!

> src/hotspot/share/opto/superword.cpp line 1368:
> 
>> 1366:       pack->push(s1);
>> 1367:     }
>> 1368:     pack->push(s2);
> 
> We should also assert that at this point, `pack != nullptr`.

Can do that, but I think it would just result in a nullptr exception anyway.
I always wonder if an assert makes the code more cluttered, so less readable, or if it states expectations more explicitly, which makes the code more readable 😅

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

PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537423998
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537425184
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537425986
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537427794