RFR: 8307084: C2: Vectorized drain loop is not executed for some small trip counts

[Emanuel Peter]

On Tue, 10 Dec 2024 14:17:23 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

>> In C2's loop optimization, for a counted loop, if we have any of these conditions (RCE, unrolling) met, we switch to the
>> `pre-main-post-loop` model. Then a counted loop could be split into `pre-main-post` loops. Meanwhile, C2 inserts minimum trip guards (a.k.a. zero-trip guards) before the main loop and the post loop. These guards test if the remaining trip count is less than the loop stride (after unrolling). If yes, the execution jumps over the loop code to avoid loop over-running. For example, if a main loop is unrolled to `8x`, the main loop guard tests if the loop has less than `8` iterations and then decide which way to go.
>> 
>> Usually, the vectorized main loop will be super-unrolled after vectorization. In such cases, the main loop's stride is going to be further multiplied. After the main loop is super-unrolled, the minimum trip guard test will be updated. Assuming one vector can operate `8` iterations and the super-unrolling count is `4`, the trip guard of the main loop will test if remaining trip is less than `8 * 4 = 32`.
>> 
>> To avoid the scalar post loop running too many iterations after super-unrolling, C2 clones the main loop before super-unrolling to create a vectorized drain loop. The newly inserted post loop also has a minimum trip guard. And, both trip guards of the main loop and the vectorized drain loop jump to the scalar post loop.
>> 
>> The problem here is, if the remaining trip count when exiting from the pre-loop is relatively small but larger than the vector length, the vectorized drain loop will never be executed. Because the minimum trip guard test of main loop fails, the execution will jump over both the main loop and the vectorized drain loop. For example, in the above case, a loop still has `25` iterations after the pre-loop, we may run `3` rounds of the vectorized drain loop but it's impossible. It would be better if the minimum trip guard test of the main loop does not jump over the vectorized drain loop.
>> 
>> This patch is to improve it by modifying the control flow when the minimum trip guard test of the main loop fails. Obviously, we need to sync all data uses and control uses to adjust to the change of control flow.
>> 
>> The whole process is done by the function `insert_post_loop()`.
>> 
>> We introduce a new `CloneLoopMode`, `InsertVectorizedDrain`. When we're cloning the vector main loop to vectorized drain loop with mode `InsertVectorizedDrain`:
>> 
>> 1. The fall-in control flow to the vectorized drain loop comes fr...
>
> src/hotspot/share/opto/loopTransform.cpp line 1690:
> 
>> 1688: 
>> 1689: //------------------------------insert_atomic_post_loop_impl-------------------------------
>> 1690: // The main implementation of inserting atomic post loop after vector main loop.
> 
> I would really appreciate some kind of ascii art here. It should show the pre, main, vectorized-post and post loop.
> And the relevant zero-trip guards, etc.

And maybe you can also draw how the rewiring happens, i.e. where you cut/glue the graph back together.

> src/hotspot/share/opto/predicates.hpp line 369:
> 
>> 367: 
>> 368: public:
>> 369:   explicit CommonAssertionPredicate(IfTrueNode* success_proj)
> 
> Can you explain this change? Also: you may have to change the description about the predicates at the top of this file.

@chhagedorn might have some reservations about this, but I'll let him comment on his own.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/22629#discussion_r1878185472
PR Review Comment: https://git.openjdk.org/jdk/pull/22629#discussion_r1878266793