Loop vectorizer

I'd start by making a plan (a design!) with goals and stuff.
Publish it so we can see what you mean by "vectorization".
I.e., do you mean for real vector machines, a la Cray, or for
the packed media instructions that are currently so popular?

What's your idea for finding vectorizable loops?
Do you have a plan for xforms to increase the amount of vectorization?
What books, papers, theses are you looking at
(so we can get on the same page)?

I've written a dependence analyzer that ought to be suitable
(if it isn't, we should fix it).

Thanks,
Preston

Hi Preston!

I'd start by making a plan (a design!) with goals and stuff.
Publish it so we can see what you mean by "vectorization".

I will send a separate email later, but here is a quick overview. I see the vectorizer having four main components:

1. Preparation passes: If-conversion, loop transformations, etc.

2. Cost model - This unit decides on the best vectorization factor (could be 1).

3. Legality check - This unit checks if it is *legal* (from a correctness point of view) to vectorize the program. This is target independent. Also, this unit needs to describe which transformation are needed to make this loop vectorizeable. For example: if-conversion is required if the control flow is not uniform for all iterations of the loop.

4. Vectorization - This is where the actual widening of the instructions happen. Every time we improve #3 by detecting more vectorizeable loops, we need to add the mechanism for actually generating code for it. For example, we can detect reduction variables, but we also need to be able to generate code for them.

I.e., do you mean for real vector machines, a la Cray, or for
the packed media instructions that are currently so popular?

I am mostly interested in generating code for the popular SIMD cpus (X86, ARM, PPC, etc).

What's your idea for finding vectorizable loops?

I started with a very very basic check because I needed to start somewhere. We will need to design a mode advanced check.

Do you have a plan for xforms to increase the amount of vectorization?

Yes. We will need to implement a predication phase and to design the interaction with other loop transformations. Also, this will have to work well with the cost model. We also need to think of a good way to detect early on if the transformations are likely to be effective, because we currently don't have a good way of undoing compiler transformations.

I think that a simple if-converter will be a good place to start. What do you think ?

I've written a dependence analyzer that ought to be suitable
(if it isn't, we should fix it).

I know :slight_smile: Yes, this is really good. Any serious loop transformation and multi-dimentional array vectorization will need this. I am glad that you are working on this and I do want to use it.

In the near future, I plan to work on the code generation cost-model aspects.

The vectorization legality check that I wrote is very simple and very conservative. It will be great if you could contribute in that area.

Thanks,
Nadav

Hi Preston!

>
> I'd start by making a plan (a design!) with goals and stuff.
> Publish it so we can see what you mean by "vectorization".

I will send a separate email later, but here is a quick overview. I
see the vectorizer having four main components:

1. Preparation passes: If-conversion, loop transformations, etc.

2. Cost model - This unit decides on the best vectorization factor
(could be 1).

3. Legality check - This unit checks if it is *legal* (from a
correctness point of view) to vectorize the program. This is target
independent. Also, this unit needs to describe which transformation
are needed to make this loop vectorizeable. For example: if-conversion
is required if the control flow is not uniform for all iterations of
the loop.

4. Vectorization - This is where the actual widening of the
instructions happen. Every time we improve #3 by detecting more
vectorizeable loops, we need to add the mechanism for actually
generating code for it. For example, we can detect reduction
variables, but we also need to be able to generate code for them.

> I.e., do you mean for real vector machines, a la Cray, or for
> the packed media instructions that are currently so popular?

I am mostly interested in generating code for the popular SIMD cpus
(X86, ARM, PPC, etc).

> What's your idea for finding vectorizable loops?

I started with a very very basic check because I needed to start
somewhere. We will need to design a mode advanced check.

> Do you have a plan for xforms to increase the amount of
> vectorization?

Yes. We will need to implement a predication phase and to design the
interaction with other loop transformations. Also, this will have to
work well with the cost model. We also need to think of a good way to
detect early on if the transformations are likely to be effective,
because we currently don't have a good way of undoing compiler
transformations.

I think that a simple if-converter will be a good place to start. What
do you think ?

Quick comment: IIRC, Ralf Karrenberg has already implemented this (as part of his WVF project: https://github.com/karrenberg/wfv/tree/llvm_30). It might be worthwhile to work on cleaning up his implementation instead of starting from scratch.

-Hal

Hi Nadav,

Do you have any small write-up of current design of loop vectorizer?. If so, can you please send it across?. I want to see if there are dependencies such as unrolling for the vectorization.

In the design we may also have to consider BB vectorizer and loop vectorizer working well together with no ambiguous requirements/dependencies.

Regards,
Shivaram

Hi Nadav,

   I went through the patch and understood the design and implementation. It's well documented :slight_smile:

Thanks,
Shivaram

Hi everybody,

Do you have a plan for xforms to increase the amount of
vectorization?

Yes. We will need to implement a predication phase and to design the
interaction with other loop transformations. Also, this will have to
work well with the cost model. We also need to think of a good way to
detect early on if the transformations are likely to be effective,
because we currently don't have a good way of undoing compiler
transformations.

I think that a simple if-converter will be a good place to start. What
do you think ?

Quick comment: IIRC, Ralf Karrenberg has already implemented this (as part of his WVF project: https://github.com/karrenberg/wfv/tree/llvm_30). It might be worthwhile to work on cleaning up his implementation instead of starting from scratch.

  -Hal

WFV [1] does indeed include phases that correspond to full control-flow to data-flow conversion (not just if-conversion, it can flatten all kinds of control flow including nested loops with multiple exits etc.).

I am currently working on a full re-implementation of the WFV algorithm on top of the latest trunk.
One part of it that is basically finished is an analysis pass that I call "vectorization analysis", which annotates a function (WFV works on entire functions) with metadata used during control-flow to data-flow conversion and instruction vectorization.
To give you a broad idea, this includes information like:
- uniform/varying operation
- same/consecutive/random index vector (for load/store)
- aligned/unaligned index vector (for load/store)
- operations that can not be vectorized (marked as "split", e.g. non-vectorizable types etc.)
- operations that need to be split and guarded (e.g. unknown calls, stores)
- mandatory/optional blocks (renamed from "divergent"/"non-divergent" in [2])
- divergent/non-divergent loops

Generally, it would be possible to implement a loop vectorizer on top of WFV simply by running a loop dependency analysis to determine if the loop in question is vectorizable, extracting the loop body into a function, running WFV on it, and inlining the call again.

I am willing to provide all of my implementation as soon as required.
I hope to have mostly finished the rewrite at that point.

Cheers,
Ralf

[1] "Whole-Function Vectorization", Karrenberg and Hack, CGO'11
[2] "Improving Performance of OpenCL on CPUs", Karrenberg and Hack, CC'12

From: "Ralf Karrenberg" <Chareos@gmx.de>
To: llvmdev@cs.uiuc.edu
Sent: Wednesday, October 17, 2012 2:13:08 AM
Subject: Re: [LLVMdev] Loop vectorizer

Hi everybody,

>>> Do you have a plan for xforms to increase the amount of
>>> vectorization?
>>
>> Yes. We will need to implement a predication phase and to design
>> the
>> interaction with other loop transformations. Also, this will have
>> to
>> work well with the cost model. We also need to think of a good way
>> to
>> detect early on if the transformations are likely to be effective,
>> because we currently don't have a good way of undoing compiler
>> transformations.
>>
>> I think that a simple if-converter will be a good place to start.
>> What
>> do you think ?
>
> Quick comment: IIRC, Ralf Karrenberg has already implemented this
> (as part of his WVF project:
> https://github.com/karrenberg/wfv/tree/llvm_30). It might be
> worthwhile to work on cleaning up his implementation instead of
> starting from scratch.
>
> -Hal

WFV [1] does indeed include phases that correspond to full
control-flow
to data-flow conversion (not just if-conversion, it can flatten all
kinds of control flow including nested loops with multiple exits
etc.).

I am currently working on a full re-implementation of the WFV
algorithm
on top of the latest trunk.
One part of it that is basically finished is an analysis pass that I
call "vectorization analysis", which annotates a function (WFV works
on
entire functions) with metadata used during control-flow to data-flow
conversion and instruction vectorization.

Is there a reason to use metadata here as opposed to just keeping state in the analysis pass?

To give you a broad idea, this includes information like:
- uniform/varying operation
- same/consecutive/random index vector (for load/store)
- aligned/unaligned index vector (for load/store)
- operations that can not be vectorized (marked as "split", e.g.
non-vectorizable types etc.)
- operations that need to be split and guarded (e.g. unknown calls,
stores)
- mandatory/optional blocks (renamed from "divergent"/"non-divergent"
in
[2])
- divergent/non-divergent loops

Sounds great!

Generally, it would be possible to implement a loop vectorizer on top
of
WFV simply by running a loop dependency analysis to determine if the
loop in question is vectorizable, extracting the loop body into a
function, running WFV on it, and inlining the call again.

I presume that we could refactor your code in combination with Nadav's work to directly vectorize loop bodies as well. Do you disagree?

I am willing to provide all of my implementation as soon as required.
I hope to have mostly finished the rewrite at that point.

I encourage you to do this as soon as possible, otherwise I think that we might miss the opportunity to take advantage of your work in current development.

Thanks again,
Hal

Hi Hal,

I am currently working on a full re-implementation of the WFV
algorithm
on top of the latest trunk.
One part of it that is basically finished is an analysis pass that I
call "vectorization analysis", which annotates a function (WFV works
on
entire functions) with metadata used during control-flow to data-flow
conversion and instruction vectorization.

Is there a reason to use metadata here as opposed to just keeping state in the analysis pass?

Yes, two practical ones:
1) I don't need to to maintain an additional instruction->properties mapping and I don't need a map lookup every time I want to check if a block/instruction has a certain property (which happens quite often).
2) For debugging purposes, I don't need to write my own AssemblyAnnotationWriter but all information is directly visible in the IR.

However, other approaches may of course be viable. My last implementation kept its own state, but the metadata approach feels a lot more convenient (even though my block and argument metadata patch was refused :wink: ).

Generally, it would be possible to implement a loop vectorizer on top
of
WFV simply by running a loop dependency analysis to determine if the
loop in question is vectorizable, extracting the loop body into a
function, running WFV on it, and inlining the call again.

I presume that we could refactor your code in combination with Nadav's work to directly vectorize loop bodies as well. Do you disagree?

I only meant to describe one way of using the code. Due to its complexity, I think that moving forward step by step is the right approach to include all that functionality in LLVM.

I am willing to provide all of my implementation as soon as required.
I hope to have mostly finished the rewrite at that point.

I encourage you to do this as soon as possible, otherwise I think that we might miss the opportunity to take advantage of your work in current development.

I'll do my best :).

Cheers,
Ralf

Hi Ralf,