[LLVMdev] Proposal: Generic auto-vectorization and parallelization approach for LLVM and Polly

[Renato Golin]

On 8 January 2011 18:27, Tobias Grosser <grosser at fim.uni-passau.de> wrote:
> OK. First of all to agree on a name, we decided to call the Polyhedral
> analysis we develop PoLLy, as in Polly the parrot. ;-) Maybe it was a
> misleading choice?

I never realised... ;) Polly it is!


> In general as I explained I agree that a three stage approach is useful,
> for the reasons you explained, however it is more overhead (and just
> implementation work) than the one we use now. I currently do not have the
> time to implement the proposed approach. In case anybody is interested to
> work on patches, I am happy to support this.

Good. If it's just a matter of time (not design), things can be left
ready for future implementation without breaking the current model. I
thought there was a fundamental flaw with the three-stage design (and
was eager to learn it).


> the only change
> in polly is, that it either generates N scalar instructions per original
> instruction or one vector instruction (if N is the number of loop iterations
> which is equivalent to the vector width). So vectorization in Polly was very
> easy to implement and already works reasonable well.

Ok, this comes with another current change in LLVM: OpenCL. I explain.

OpenCL has very large (and odd) vector sizes, that if implemented to
vectorized units (like SSE or NEON), need to be legalised.

Such a pass should be target specific and polly could make use of
that. If polly always generate vector code (instead of reason if the
number of unrolled operations are the same as the current target being
compiled into), the later legalisation pass can deal with the odd
sized vectors and transform into multiples of legal vector + some
surplus of the module as normal instructions.

Also, if the target doesn't have vector units, there could be a
generic (or not) transformation to cpu instructions (if there isn't
one already), so that makes your polly pass completely target
agnostic.


> Why are target specific vectorization passes needed to generate vector
> instructions from Polly? The only target specific information I currently
> see is the vector width, which a generic vectorization pass can obtain from
> the target data information. Could you explain for which features target
> specific vectorization would be needed?

Not target specific, generic vectors. See above.


> I have read this and the look interesting. I suppose they are created out of
> the box, if a pass generates LLVM-IR vector instructions?

Yup. It's pretty neat. SSE is probably similar, but with NEON, a
pattern-match is done when the variable type is a vector.

So, a multiplication followed by an addition in the right way is
transformed into a multiply-and-add NEON instruction.

An example (in a completely wrong IR, just to make a point):

%a = <4 x i32>
%b = <4 x i32>
%c = <4 x i32>
%mul = mul %b, %c
%acc = add %mul, %a

gets transformed into:

VMLA.I32 q0, q1, q2

Multiplying vectors (of the correct size) gets into VMUL, adding gets
to VADD and so on...

cheers,
--renato