LLVM Loop Vectorizer (Nadav Rotem)

Hi Nadav (and others who are related to this issue) -

I saw some discussions on loop vectorizer that you are planning to write. Do you foresee using Polyhedral Framework (polly project) in some way in that.



I'd like to add that, mostly through Tobi's efforts, we were able to have isl (the integer set library) on which Polly depends relicensed such that it is now distributed under the MIT license, and thus Polly should be eligible for inclusion as some of LLVM's core analysis and transformation passes.


Yes, that will be very useful. One way to think of Polly is as a "gateway into the polyhedral model". The core functionality is to take a region and provide a polyhedral model for its memory accesses. This is separate from the fact that Polly also provides an optimization driver over a handful of different polyhedral implementations.

Besides that, ISL, through Polly, provides a pretty good dependence analysis. There should be an abstract dependence API similar to AliasAnalysis, so that Polly can be used as an analysis option.


Hi Javed,

Developing a good loop vectorizer takes several years. The work on the GCC vectorizer began in 2004, and they spent several years improving and optimizing their vectorizer. They started by vectorizing simple loops, and added features that they needed in order to vectorize additional loops that were important for them. They started with a single-block loops, and later they added "if-conversion", support for reductions and induction variables, etc. This approach was effective because it allowed them to stay focused.

It is important to stay focused on today's problems, but at the same time provide the right abstraction even for problems that we decide not to solve today. We've started discussing the details of exposing target information to IR-level passes because it will allow the loop vectorizer, as well as other optimizations, to do a better job. Once we finish the design of the "Target" interface, we need to start working on a general loop-vectorizer design. I think that any design that we choose must take Polly into consideration. But I don't think that we need to start with loops that require polyhedral optimizer. I think that we should start with the examples from the gcc vectorizer page[1].


[1] - http://gcc.gnu.org/projects/tree-ssa/vectorization.html

First, we need to check and see if Polly is the solution to the problems that we have.

It would be great to get "accurate" dependence analysis from polyhedral framework. Anyone working on making polly into analysis+Transforms framework?


Polly/isl/Pluto already provide SCoP detection, polyhedral analysis, loop transform framework (e.g. to do fusion, tiling etc).

Polly is already divided into analysis and transformation passes. However, the interface is currently specific to the needs of polyhedral optimizers. If there is interest to use e.g. the analyzer
part of Polly within core LLVM, we could adapt the interface to our needs. We could e.g. think of an interface similar to Preston's dependency analysis.


Hi Nadav, Javad,

yes, I think the path you are taking is great. The 'Target' interface was one of immediate problems for vectorization. Solving it will help any pass working in that area.

Regarding the use of Polly as a loop vectorizer. Polly is definitely a tool that may help in the area of loop vectorization, but as Nadav said, its use must be carefully evaluated. I see Polly rather as a piece of a bigger picture, then the one and only solution to vectorization in LLVM.

I think Pollys strengths are definitely in the area of loop transformations. In case we want to do outer loop vectorization, require interchange, strip-mining, ... to enable vectorization or want to create cleanup loops, Polly can be of great value. However, vectorization is also a lot of pattern matching on IR level. I am not sure if all this pattern matching really needs to be part of a polyhedral optimizer. My personal feeling is that we would be better of keeping this separate.

Also, as Nadav pointed out, as a first step a vectorizer will probably focus on very simple loops. Polly can obviously also help to vectorize them, but Polly may or may not be too much overhead for such simple cases. I think Sebastian Pop actually tested Polly on the gcc vectorizer test cases. He might be on vacaction now, but it would be interesting to get his results.

As the design of the vectorizer is a very hot topic, I was wondering if there will be a BoF session on the LLVM conference? Nadav, you have not proposed one by accident?


I proposed a BoF, and (if accepted) we can start discussing the design of the llvm loop vectorizer and the infrastructure that we need for implementing it.



Hi Tobias-

Let me relook at Preston's patch and think of what I need in a similar analysis for dependence. I will get back to you once I am comfortable.



As Tobias and Nadav pointed out, this is not about replacing what's
available, but creating a framework for all vectorization techniques
to work out together, and not against each other.

So far, there has been some inclusions of vectorization, talks about
openmp and Polly, all very valid, but ultimately with little results
to the rest of us. The framework is not good enough, yet.

The TargetData discussion is an important step, and seems people are
very eager to finally do the big change. I generally agree with the
model that is being discussed, and am very happy that someone
(especially Nadav) is taking the long road.