RFR: 8325252: C2 SuperWord: refactor the packset

[Emanuel Peter]

On Mon, 25 Mar 2024 08:30:07 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 1038:
> 
>> 1036: 
>> 1037: // Extend pairset by following use->def and def->use links from pair members.
>> 1038: void SuperWord::extend_pairset_with_more_pairs_by_following_use_and_def() {
> 
> Could this method (and possibly other methods only called in the context of this method) also be part of the new `PairSet` class?

Not really. Inside we need lots of access to the SuperWord components (check `alignment`, `stmts_can_pack`, etc). You could always pass in a `SuperWord` reference, but that is not really nicer.
Maybe it would be easier in the future, once I make some other changes. But we will always need to have other information available (dependency graph, types, etc - these are all VLoopAnalyzer submodules), but for now we also rely on `alignment`, which I plan to remove, and lives in SuperWord.

> src/hotspot/share/opto/superword.cpp line 1144:
> 
>> 1142:   }
>> 1143: #endif
>> 1144:   bool changed = false;
> 
> I think you could directly return true or false at the very end of the method where you set the flag.

Good point!

> src/hotspot/share/opto/superword.cpp line 1230:
> 
>> 1228: // 2: Inputs of (use1, use2) already match (def1, def2), i.e. for all input indices i:
>> 1229: //
>> 1230: //    use1->in(i) == def1 || use2->in(def2)   ->    use1->in(i) == def1 && use2->in(def2)
> 
> Should this be `use2->in(i) == def2`?

Yes!

> src/hotspot/share/opto/superword.cpp line 1248:
> 
>> 1246: //          Therefore, extend_pairset_with_more_pairs_by_following_use cannot extend to MulAddS2I,
>> 1247: //          but there is a chance that extend_pairset_with_more_pairs_by_following_def can do it.
>> 1248: //
> 
> Nice summary :-) Just a suggestion, should we move the second case (already ordered) last to match the order in the code below? Then you could say that in all other cases, we're good, i.e.

Sounds good :)

> src/hotspot/share/opto/superword.cpp line 1254:
> 
>> 1252:   // 1. Reduction
>> 1253:   if (is_marked_reduction(use1) && is_marked_reduction(use2)) {
>> 1254:     Node* first = use1->in(2);
> 
> Was like that before but shouldn't this be named `second` or `second_input` instead of `first`? It's gonna be the first input only after the swap.

I agree, it already was like that, and it disturbed it me too. I thought I'd leave it since I'll probably overhaul this whole code soon anyway. But I'll fix it already since it disturbs you too.

> src/hotspot/share/opto/superword.cpp line 1282:
> 
>> 1280:           use2->swap_edges(3, 4);
>> 1281:         }
>> 1282:         if (i1 == 3 - i2 || i1 == 7 - i2) { // ((i1 == 1 && i2 == 2) || (i1 == 2 && i2 == 1) || (i1 == 3 && i2 == 4) || (i1 == 4 && i2 == 3))
> 
> Both comments are a bit long, should we wrap them? Maybe like that:
> 
> // (i1 == 3 && i2 == 2)
> // (i1 == 2 && i2 == 3) or
> // (i1 == 1 && i2 == 4) or 
> // (i1 == 4 && i2 == 1) or
> if (i1 == 5 - i2) {
> ...

I'd rather not spend too much time on this, since I'll overhaul it soon even more. I'm not touching the comments anyway ;)

> src/hotspot/share/opto/superword.cpp line 1307:
> 
>> 1305:   int save_in = 2 - 1; // 2 operations per instruction in packed form
>> 1306: 
>> 1307:   auto adjacent_profit = [&] (Node* s1, Node* s2) { return 2; };
> 
> You can remove `s1` and `s2` since you always return 2.

Sure

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

PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537412950
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537416655
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537419417
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537418777
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537415805
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537418452
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537416752