RFR: 8325252: C2 SuperWord: refactor the packset
Christian Hagedorn
chagedorn at openjdk.org
Mon Mar 25 10:26:36 UTC 2024
On Wed, 13 Mar 2024 14:25:57 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.
Nice refactoring. Here are some first comments about the pair set. Will continue later.
Just a side note: Would it have been possible to split this RFE into a pair set and a pack set refactoring separately without big efforts due to dependencies between them? It might simplify the review.
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?
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.
src/hotspot/share/opto/superword.cpp line 1215:
> 1213: }
> 1214:
> 1215: // For a def-pair (def1. def2), and their use-nodes (use1, use2):
Suggestion:
// For a def-pair (def1, def2), and their use-nodes (use1, use2):
src/hotspot/share/opto/superword.cpp line 1216:
> 1214:
> 1215: // For a def-pair (def1. def2), and their use-nodes (use1, use2):
> 1216: // ensure that the input order of (use1, use2) matches the order of (def1, def2).
Suggestion:
// Ensure that the input order of (use1, use2) matches the order of (def1, def2).
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`?
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?
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.
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.
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) {
...
src/hotspot/share/opto/superword.cpp line 1288:
> 1286: return PairOrderStatus::Unknown;
> 1287: } else {
> 1288: // The inputs are not ordered, and we can not do anything about it.
Suggestion:
// The inputs are not ordered, and we cannot do anything about it.
src/hotspot/share/opto/superword.cpp line 1303:
> 1301: }
> 1302:
> 1303: // Estimate the savings from executing s1 and s2 as a pack
Suggestion:
// Estimate the savings from executing s1 and s2 as a pair.
src/hotspot/share/opto/superword.cpp line 1304:
> 1302:
> 1303: // Estimate the savings from executing s1 and s2 as a pack
> 1304: int SuperWord::estimate_cost_savings_when_packing_pair(const Node* s1, const Node* s2) const {
Nit: Should we add a `as` or `to`?
Suggestion:
int SuperWord::estimate_cost_savings_when_packing_as_pair(const Node* s1, const Node* s2) const {
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.
src/hotspot/share/opto/superword.cpp line 1338:
> 1336: for (DUIterator_Fast kmax, k = s2->fast_outs(kmax); k < kmax; k++) {
> 1337: if (use2 == s2->fast_out(k)) {
> 1338: ct++;
Maybe add the following as a visual aid?
s1 s2
| |
[use1, use2]
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`.
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?
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`.
-------------
PR Review: https://git.openjdk.org/jdk/pull/18276#pullrequestreview-1957111113
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537203711
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537268401
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537243897
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537244514
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537332755
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537338269
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537324987
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537255606
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537323963
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537318162
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537304354
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537305714
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537287795
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537315499
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537351581
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537352946
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1537353730
More information about the hotspot-compiler-dev
mailing list