[llvm-dev] [RFC] Polly Status and Integration

[Sebastian Pop via llvm-dev]

On Tue, Sep 26, 2017 at 2:00 AM, Tobias Grosser via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> On Tue, Sep 26, 2017, at 00:03, Johannes Doerfert wrote:
>> It depends on what you want. If you want a polyhedral scheduler right
>> away, integration is the way to go.

I think this is the topic of the thread as the folks who started
this discussion stated that they want to see Polly integrated
in LLVM.

>> However, I don't think reuse of
>> Polly for other purposes is that simple and the changes I argue for are
>> (in this context) quite complicated (see below).

You are just saying that there are difficult to write polyhedral
passes that do not fully rely on the infrastructure that Polly
provides, which in my opinion, is perfectly fine.

Polly's integration will bring to LLVM more than the loop
transforms that Polly implements with isl's schedulers:
there are a set of issues that Polly had to solve and that will
be of use by the other polyhedral analyses and optimizations
that you are mentioning.
Here are a few examples of the more general infrastructure
that Polly enables: license of isl compatible with LLVM, isl's
compute-out, imath, native int computations instead of MP, etc.

>> I do think that changing all the parts I mentioned will require a major
>> rewrite and that it will be more complicated than writing the components
>> "from scratch".

Nobody tries to stop you writing those things from scratch.
However if you want to make those passes useful to the
existing code, for example in value range propagation,
or in some of the redundant code elimination passes,
or in Polly, you would have to deal with the complexities
of transitioning the existing code to the new analysis interfaces.

>> The reason is simple, new components can be developed
>> one by one without the need to worry about the implications for later
>> passes. We can design them for the uses cases at hand while keeping
>> their use in a future polyhedral scheduling pipeline in mind. In Polly,
>> the things I want to change have implicit and explicit ties to various
>> parts in the pipeline. Consequently, it is extremely challenging to
>> change them only in parts of the pipeline e.g., the modeling, at least
>> if we want to keep the original functionality intact all the time.

This is normal operation: work in the compiler is incremental,
it happens by evolution and rarely by revolution.

I will give you an example from another part of the compiler that
we try to extend while keeping the existing pass work at all time:
jump-threading.
The original jump-thread pass was contributed more than
10 years ago, and it does pretty well to optimize the code.
However it still cannot jump-thread across multiple basic blocks
and across loop back-edges: there were several attempts in
extending the existing pass without much traction.
An easy way would be to start from scratch and just implement
a new pass. However that would require to implement more
than half of the analysis and code generation with code that
would mostly look the same. I see no good reason to throw
away that code when we could very well improve over the
existing code in incremental steps:
maintaining the dominators, improve the way we operate on
the CFG, maintaining loops across several jump-threads, etc.,
the sum of which gets us closer to what we want to achieve
while improving the existing code.

> For some of the changes you propose -- e.g. extracting parts of Polly to
> build a polyhedral value analysis -- extracting it out individually is
> clearly the right approach.

I agree: making the infrastructure more general and used in
more code than in isl's polyhedral schedulers can happen
as incremental changes as new functionality is built.
If the current way Polly does things stands in the way,
it should be fixed in incremental steps.

Sebastian