Richard Biener <rguent...@suse.de> 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