[LLVMdev] Vectorization: Next Steps

[Preston Briggs]

On Wed, Feb 8, 2012 at 2:23 AM, Tobias Grosser <tobias at grosser.es> wrote:
> Knowing if Polly would parallelize some code is hard to judge without seeing the code,

Which reminds me...
I think that any compiler that's making non-trivial xforms should have
a feedback
mechanism to show the programmer what's going on, i.e., which loops are
vectorized or parallelized, loops that are fused or distributed,
dependences that
prevent xforms, and so forth.  Sometimes we see a sort of annotated listing,
with notes as to what's going on and why.

Is there support for such a thing with Polly?


> From my point of view reductions are not very special.
> Basically a sequence of statement iterations that work on the same data element.
> If the operation applied is associative some nice optimizations can be performed
> and some dependences can be removed.

Right. The interesting things are that they come up a lot in user code
and they can be
solved in parallel.

> So let me know a little bit more about your dependence graph.
> What is a statement in your graph? An LLVM-IR instruction?
> Or do you group them somehow?

Hal wondered about this too.
I don't have an implementation, only a direction.
That said, here's what I'm thinking...

The dependence graph has nodes and edges.
There's a node for every memory reference (load, store, call)
and edges for dependences between them.
Edges are directed, with a source and a destination.
There are 3 kinds of edge, for True, Anti, and Output dependences,
depending on whether the source and destination are loads and/or stores.
(it may also prove useful to represent input dependences)

An edge has several attributes:
- common, the number of loops around both references (might be 0 if
they are in different loop nests)
- levels, the number of loops around each reference that were analyzed
(might be greater than levels when the loops are candidates for loop
fusion)
- confused, a flag indicating no detailed info is available
- consistent, a flag indicating a simple distance vector (otherwise,
we'll have a direction vector)

There's also a direction/distance vector with an entry for each loop level.
Entries are the usual disjunction of <, =, > plus a few special values:
- scalar, the address expression is invariant at this level
- unknown
and perhaps a couple more.  All pretty classical stuff.
Then, given all this info, we look for opportunities to make a variety
of loop xforms,
focusing on the dependence graph rather than the IR.

> Just keep me up to date.

Will do.

Thanks,
Preston