[llvm-dev] Vectorizing multiple exit loops

[Zaks, Ayal (Mobileye) via llvm-dev]

> -----Original Message-----
> From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of Renato
> Golin via llvm-dev
> Sent: Thursday, September 19, 2019 13:16
> To: Philip Reames <listmail at philipreames.com>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>
> Subject: Re: [llvm-dev] Vectorizing multiple exit loops
> 
> On Thu, 19 Sep 2019 at 00:19, Philip Reames <listmail at philipreames.com>
> wrote:
> > If M < N (provably), SCEV would return an exit count for the loop
> > which reflects this.  If not, we'd get umin(M,N).  We can still
> > generate the vector body at the cost of inserting the umin computation
> > above the loop body.  Both cases can be handled by running the vector
> > loop up to the minimum trip count (well, one less to handle mid-loop
> > exits and side effects).  The M < N case is falls out of the more general one.
> 
> Yup.
> 
> > I don't know of any plans to incorporate iteration space splitting
> > w/VPLan.  I don't have any plans to go that far; if I had such test
> > cases - I don't - I'd want to start with separately factored
> > transforms if we could.  Doing everything within one transform is
> > undesirable.  :)
> 
> AFAIK this isn't strictly in the immediate plans, but loop splitting was one of
> the aims for doing outer-loop vectorisation.

The aim being to vectorize an outer-loop when an inner-loop is difficult / requires loop splitting to vectorize?

> My point was that if we want to do that, vplan would be a good place, because
> we could add this as its own plan, which would expose other vectorisation
> opportunities (including fusion with other loops).

VPlan is designed to support the tentative decisions and alternatives when vectorizing. E.g., when different types of instructions are to be generated for different VF's. Loop index splitting, and turning a multiple exit loop into a (countable) single exit loop, seem like preparatory transformations that can enable vectorization and/or interleaving for any VF/UF, similar to loop distribution.

VPlan currently models the instructions inside the vector loop. If a "while" or multiple exit loop has stores above the "break point", it may be possible to sink them in order to avoid issuing speculative stores. LV applies similar "SinkAfter" code motion when needed to facilitate 1st order recurrence. Loads may indeed be handled speculatively by dereferencability, which may in turn require peeling the first iterations to reach an  aligned address. Such peeling may be folded into the vector loop by masking, if desired, analogous to LV's foldTailByMasking.

Perhaps a simplest example is an str[n]len() loop. "Exploiting the AltiVec Unit for Commercial Applications", CAECW-9, 2006 demonstrated the speedups and slowdowns of vectorizing it on PowerPC970.
---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.