RFR: 8325252: C2 SuperWord: refactor the packset

[Emanuel Peter]

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.

src/hotspot/share/opto/superword.hpp line 101:

> 99:   int length() const { return _lefts_in_insertion_order.length(); }
> 100:   Node* left_at(int i)  const { return _body.body().at(_lefts_in_insertion_order.at(i)); }
> 101:   Node* right_at(int i) const { return _body.body().at(get_right_for(_lefts_in_insertion_order.at(i))); }

Note: I hope to get rid of `_lefts_in_insertion_order` eventually, and then these accessors will disappear too. But for now I need them to iterate in insertion order, doing something similar to a DFS in the pair extension.

src/hotspot/share/opto/superword.hpp line 250:

> 248:   Node_List* my_pack(const Node* n)     const { return !in_bb(n) ? nullptr : _node_info.adr_at(bb_idx(n))->_my_pack; }
> 249:  private:
> 250:   void set_my_pack(Node* n, Node_List* p)     { int i = bb_idx(n); grow_node_info(i); _node_info.adr_at(i)->_my_pack = p; }

Note: replaced with `PackSet.pack` and `PackSet.set_pack`.

src/hotspot/share/opto/superword.hpp line 271:

> 269:   bool stmts_can_pack(Node* s1, Node* s2, int align);
> 270:   // Does s exist in a pack at position pos?
> 271:   bool exists_at(Node* s, uint pos);

Note: replaced with `PairSet.has_left/right`.

src/hotspot/share/opto/superword.hpp line 293:

> 291:   void set_pack(const Node* n, Node_List* pack) { _node_to_pack.at_put(_body.bb_idx(n), pack); }
> 292: public:
> 293:   Node_List* pack(const Node* n) const { return !_vloop.in_bb(n) ? nullptr : _node_to_pack.at(_body.bb_idx(n)); }

Note: replacement for `my_pack`.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1533416428
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1533420534
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1533421120
PR Review Comment: https://git.openjdk.org/jdk/pull/18276#discussion_r1533418322