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

[Tobias Grosser]

On 01/08/2011 06:52 PM, Renato Golin wrote:
> 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).
Not at all. It was just soo much easier to create vector instructions 
right inside of Polly that I did not start another large project.

>> 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.

I believe LLVM already has lowering of wide LLVM-IR vectors to a set of 
operations of vectors of target specific wide. This is done in the back 
end and works correct for all cases I tested. The problem with this is 
just performance. They fastest loop nest is different on architectures 
with different vector width and size of vector registers. A generic 
polyhedral optimizer will therefore not generate incorrect code, however 
the proposed transformations are wrong. If Polly e.g. always generates 
vector operations to be 32 floats width, this would result in not very 
pleasant code, but might still be lowered to something well performing 
on cpus supporting AVX. Matching the target vector width in our 
heuristics will obviously give the best performance. So to get optimal 
performance Polly needs to take target data into account.

Talking about OpenCL. The lowering you described for the large vector 
instructions sounds reasonable. Optimal code would however probably 
produced by revisiting the whole loop structure and generating one that 
is performance wise optimal for the target architecture.

>> 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...

Yes. I have seen this also for powerpc and hope we can soon use the AVX 
multiply and add instruction too.

Cheers
Tobi