RFR: 8325252: C2 SuperWord: refactor the packset [v4]
Christian Hagedorn
chagedorn at openjdk.org
Wed Mar 27 09:14:36 UTC 2024
On Mon, 25 Mar 2024 12:58:55 GMT, Emanuel Peter <epeter 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.
>
> Emanuel Peter has updated the pull request incrementally with one additional commit since the last revision:
>
> use left/right instead of s1/s2 in some obvious simple places
Thanks for the updates. The PR generally looks good! I now fully reviewed it and left some more comments.
src/hotspot/share/opto/superword.cpp line 1088:
> 1086: }
> 1087:
> 1088: bool SuperWord::extend_pairset_with_more_pairs_by_following_def(Node* s1, Node* s2) {
Small detail: Here you seem to possibly add multiple pairs while the `following_use` version can only add one pair. Maybe you want to state that in a method comment or adapt the name for the `following_use` version to make that distinction clear.
src/hotspot/share/opto/superword.cpp line 1188:
> 1186: }
> 1187:
> 1188: // For a pair (def1. def2), find all use packs (use1, use2), and ensure that their inputs have an order
Suggestion:
// For a pair (def1, def2), find all use packs (use1, use2), and ensure that their inputs have an order
src/hotspot/share/opto/superword.cpp line 1306:
> 1304: int save_in = 2 - 1; // 2 operations per instruction in packed form
> 1305:
> 1306: auto adjacent_profit = [&] () { return 2; };
Thinking about this again, you might also just transform this into a constant and use it instead of a local lambda.
src/hotspot/share/opto/superword.cpp line 1326:
> 1324:
> 1325: // uses of result
> 1326: uint ct = 0;
Should we rename `ct` to something more descriptive like `number_of_matched_pairs` or something similar?
src/hotspot/share/opto/superword.cpp line 1394:
> 1392:
> 1393: SplitStatus PackSet::split_pack(const char* split_name,
> 1394: Node_List* pack,
Just wondering if you also plan to have a separate `Pack` class at some point instead of using `Node_List`? If it's not worth we might still want to use a typedef to better show what the intent is. But that's something for another day.
src/hotspot/share/opto/superword.cpp line 1414:
> 1412: Node* n = pack->at(i);
> 1413: set_pack(n, nullptr);
> 1414: }
Should we have a `remove_pack()` method that performs this operation? Then you could also call that just below at L1446 as well.
src/hotspot/share/opto/superword.cpp line 1539:
> 1537:
> 1538: // Split packs at boundaries where left and right have different use or def packs.
> 1539: void SuperWord::split_packs_at_use_def_boundaries() {
As above with `PairSet`, I'm also wondering here if these `split` methods could be part of `PackSet`? But I have not checked all the method calls and it could very well be that you would need to pass a reference to `SuperWord` to `PackSet`. From a high-level view, "split packs" feels like an operation you perform on a pack set. Same, for example, as `SuperWord::verify_packs()`.
Either way, I think the patch is already quite big and I think we should do that - if wanted - separately
src/hotspot/share/opto/superword.cpp line 1764:
> 1762:
> 1763: // Can code be generated for the pack, restricted to size nodes?
> 1764: bool SuperWord::implemented(const Node_List* pack, uint size) const {
While fixing `const` you could also add `const` for `size` (same for parameters of the methods below where you fixed `const`). But could also be done separately.
src/hotspot/share/opto/superword.cpp line 2084:
> 2082: // Create nodes (from packs and scalar-nodes), and add edges, based on the dependency graph.
> 2083: void build() {
> 2084: const PackSet& packset = _slp->packset();
You could also store the pack set as field since you access it several times.
src/hotspot/share/opto/superword.cpp line 2404:
> 2402: for (int i = 0; i < body().length(); i++) {
> 2403: Node* n = body().at(i);
> 2404: Node_List* p = _packset.pack(n);
Since you use this pattern a lot, you could also think about having a `SuperWord::pack()` method that delegates to `_packset.pack()`.
src/hotspot/share/opto/superword.cpp line 3754:
> 3752: }
> 3753:
> 3754: void PackSet::print_pack(Node_List* pack) const {
Could also be made static since you don't access any fields.
src/hotspot/share/opto/superword.hpp line 69:
> 67: // Doubly-linked pairs. If not linked: -1
> 68: GrowableArray<int> _left_to_right; // bb_idx -> bb_idx
> 69: GrowableArray<int> _right_to_left; // bb_idx -> bb_idx
I think it's a good solution but still found myself revisiting this several times while looking at the methods below how it works. Would it maybe help to give a visual example? For example:
left_to_right:
index: 0 1 2 3
value: | -1 | 3 | -1 | -1 | ...
=> Node with bb_idx 1 is left in a pair with bb_idx 3.
right_to_left:
index: 0 1 2 3
value: | -1 | -1 | -1 | 1 | ...
=> Node with bb_idx 3 is right in a pair with bb_idx 1.
```
src/hotspot/share/opto/superword.hpp line 88:
> 86: bool has_right(int i) const { return _right_to_left.at(i) != -1; }
> 87: bool has_left(const Node* n) const { return _vloop.in_bb(n) && has_left( _body.bb_idx(n)); }
> 88: bool has_right(const Node* n) const { return _vloop.in_bb(n) && has_right(_body.bb_idx(n)); }
What about naming these `is_left/right()` as in `is_left_in_a_left/right_most_pair()`? I think it's more intuitive.
src/hotspot/share/opto/superword.hpp line 96:
> 94: int get_right_for(int i) const { return _left_to_right.at(i); }
> 95: Node* get_right_for(const Node* n) const { return _body.body().at(get_right_for(_body.bb_idx(n))); }
> 96: Node* get_right_or_null_for(const Node* n) const { return has_left(n) ? get_right_for(n) : nullptr; }
Just a visual comment: These methods are very densely packed here and somewhat hard to read. Could we somehow group them better together? For example, `body()` is unrelated and could be separated by a new line.
src/hotspot/share/opto/superword.hpp line 134:
> 132: PairSetIterator(const PairSet& pairset) :
> 133: _pairset(pairset), _body(pairset.body()),
> 134: _chain_start_bb_idx(-1), _current_bb_idx(-1),
Not sure if our style guide says anything about multi-line inits but I think we often put them on separate lines.
src/hotspot/share/opto/superword.hpp line 140:
> 138: }
> 139:
> 140: bool done() const { return _chain_start_bb_idx >= _end_bb_idx; }
I suggest to follow the style of `left()` and add line breaks.
src/hotspot/share/opto/superword.hpp line 263:
> 261: const VLoopBody& _body;
> 262:
> 263: // The "packset" proper: an array of "packs"
What do you mean by " The "packset" proper"?
src/hotspot/share/opto/superword.hpp line 488:
> 486: bool do_vector_loop() { return _do_vector_loop; }
> 487:
> 488: const PackSet& packset() const { return _packset; }
Somehow a strange alignment. You might want to fix that.
test/hotspot/jtreg/compiler/loopopts/superword/TestMulAddS2I.java line 38:
> 36: import jdk.test.lib.Platform;
> 37:
> 38: public class TestMulAddS2I {
Might be worth to add 8325252 as `@bug` number as well since you added quite a few tests.
-------------
PR Review: https://git.openjdk.org/jdk/pull/18276#pullrequestreview-1960798902
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1539487611
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1539490177
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1539495230
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1539500944
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1539506632
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1539515844
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1539538019
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540640224
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540644383
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540645771
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540651158
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540664022
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540670242
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540685021
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540689508
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540690674
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540704583
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540708517
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1540711897
More information about the hotspot-compiler-dev
mailing list