Richard Biener <[email protected]> writes:
> On Mon, 10 Oct 2022, Andrew Stubbs wrote:
>> On 10/10/2022 12:03, Richard Biener wrote:
>> > The following picks up the prototype by Ju-Zhe Zhong for vectorizing
>> > first order recurrences. That solves two TSVC missed optimization PRs.
>> >
>> > There's a new scalar cycle def kind, vect_first_order_recurrence
>> > and it's handling of the backedge value vectorization is complicated
>> > by the fact that the vectorized value isn't the PHI but instead
>> > a (series of) permute(s) shifting in the recurring value from the
>> > previous iteration. I've implemented this by creating both the
>> > single vectorized PHI and the series of permutes when vectorizing
>> > the scalar PHI but leave the backedge values in both unassigned.
>> > The backedge values are (for the testcases) computed by a load
>> > which is also the place after which the permutes are inserted.
>> > That placement also restricts the cases we can handle (without
>> > resorting to code motion).
>> >
>> > I added both costing and SLP handling though SLP handling is
>> > restricted to the case where a single vectorized PHI is enough.
>> >
>> > Missing is epilogue handling - while prologue peeling would
>> > be handled transparently by adjusting iv_phi_p the epilogue
>> > case doesn't work with just inserting a scalar LC PHI since
>> > that a) keeps the scalar load live and b) that loads is the
>> > wrong one, it has to be the last, much like when we'd vectorize
>> > the LC PHI as live operation. Unfortunately LIVE
>> > compute/analysis happens too early before we decide on
>> > peeling. When using fully masked loop vectorization the
>> > vect-recurr-6.c works as expected though.
>> >
>> > I have tested this on x86_64 for now, but since epilogue
>> > handling is missing there's probably no practical cases.
>> > My prototype WHILE_ULT AVX512 patch can handle vect-recurr-6.c
>> > just fine but I didn't feel like running SPEC within SDE nor
>> > is the WHILE_ULT patch complete enough. Builds of SPEC 2k7
>> > with fully masked loops succeed (minus three cases of
>> > PR107096, caused by my WHILE_ULT prototype).
>> >
>> > Bootstrapped and tested on x86_64-unknown-linux-gnu.
>> >
>> > Testing with SVE, GCN or RVV appreciated, ideas how to cleanly
>> > handle epilogues welcome.
>>
>> The testcases all produce correct code on GCN and pass the execution tests.
>>
>> The code isn't terribly optimal because we don't have a two-input permutation
>> instruction, so we permute each half separately and vec_merge the results. In
>> this case the first vector is always a no-op permutation so that's wasted
>> cycles. We'd really want a vector rotate and write-lane (or the other way
>> around). I think the special-case permutations can be recognised and coded
>> into the backend, but I don't know if we can easily tell that the first
>> vector
>> is just a bunch of duplicates, when it's not constant.
>
> It's not actually a bunch of duplicates in all but the first iteration.
> But what you can recognize is that we're only using lane N - 1 of the
> first vector, so you could model the permute as extract last
> + shift in scalar (the extracted lane). IIRC VLA vector targets usually
> have something like shift the vector and set the low lane from a
> scalar?
Yeah.
> The extract lane N - 1 might be more difficult but then
> a rotate plus extracting lane 0 might work as well.
I guess for SVE we should probably use SPLICE, which joins two vectors
and uses a predicate to select the first element that should be extracted.
Unfortunately we don't have a way of representing "last bit set, all other
bits clear" as a constant though, so I guess it'll have to be hidden
behind unspecs.
I meant to start SVE tests running once I'd finished for the day yesterday,
but forgot, sorry. Will try to test today.
On the patch:
+ /* This is the second phase of vectorizing first-order rececurrences. An
+ overview of the transformation is described below. Suppose we have the
+ following loop.
+
+ int32_t t = 0;
+ for (int i = 0; i < n; ++i)
+ {
+ b[i] = a[i] - t;
+ t = a[i];
+ }
+
+ There is a first-order recurrence on "a". For this loop, the shorthand
+ scalar IR looks like:
+
+ scalar.preheader:
+ init = a[-1]
+ br loop.body
+
+ scalar.body:
+ i = PHI <0(scalar.preheader), i+1(scalar.body)>
+ _2 = PHI <(init(scalar.preheader), <_1(scalar.body)>
+ _1 = a[i]
+ b[i] = _1 - _2
+ br cond, scalar.body, ...
+
+ In this example, _2 is a recurrence because it's value depends on the
+ previous iteration. In the first phase of vectorization, we created a
+ temporary value for _2. We now complete the vectorization and produce the
+ shorthand vector IR shown below (VF = 4).
+
+ vector.preheader:
+ vect_init = vect_cst(..., ..., ..., a[-1])
+ br vector.body
+
+ vector.body
+ i = PHI <0(vector.preheader), i+4(vector.body)>
+ vect_1 = PHI <vect_init(vector.preheader), v2(vector.body)>
+ vect_2 = a[i, i+1, i+2, i+3];
+ vect_3 = vector(vect_1(3), vect_2(0, 1, 2))
+ b[i, i+1, i+2, i+3] = vect_2 - vect_3
+ br cond, vector.body, middle.block
+
+ middle.block:
+ x = vect_2(3)
+ br scalar.preheader
+
+ scalar.ph:
+ s_init = PHI <x(middle.block), a[-1], otherwise>
+ br scalar.body
+
+ After execution completes the vector loop, we extract the next value of
+ the recurrence (x) to use as the initial value in the scalar loop. */
Looks like a[-1] should be zero in the example (or t should be initialised
to a[-1]).
Thanks,
Richard
