[LLVMdev] Vectorization: Next Steps

[Hal Finkel]

On Mon, 2012-02-06 at 14:13 -0600, Sebastian Pop wrote:
> On Sat, Feb 4, 2012 at 2:27 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> > On Fri, 2012-02-03 at 20:59 -0800, Preston Briggs wrote:
> >> so are building a dependence graph for a complete function.  Of
> >> course, such a thing is useful for vectorization and all sorts of
> >> other dependence-based loop transforms.
> >>
> >> I'm looking at the problem in two parts:
> >>      1. a dependence test that, given two memory references, decides
> >>         if a dependence exists between them, and
> 
> Would you consider using Polly http://polly.grosser.es to avoid
> writing this code? 

I agree, we should use the (self-contained) passes developed in Polly
where possible.

>  If you do not want to use polly, you could use ISL
> http://freecode.com/projects/isl to set up the dependence problem and
> use ISL's ILP to solve it.

isl is an LGPL project. It is not clear to me what the general consensus
would be on having a core analysis pass carry an LGPL dependency.

> 
> These would be my preferred choices to implement the dependence test:
> on the GCC side I have implemented a stand alone dependence tester
> that does not use ILP (i.e., sets the dependence test as a Diophantine
> equation and then solves it) and I can say that it was quite painful
> to write it and to clean the code of bugs.
> 
> >>      2. the dependence-graph builder that looks over the complete
> >>         function and finds pairs of memory references to pass to the
> >>         dependence test, using the results to build a dependence
> >>         graph, with edges labeled as to the kind of dependence and
> >>         direction vectors.
> >> Currently I'm focused on (2), the simpler task I think, as a way to
> >> lean my way around infrastructure. The idea, roughly, is to find all
> >> the alias sets associated with each load and store and compute what
> >> Wolfe calls factored redef-use chains for each alias set (similar to
> >> SSA, but supporting computation of all 4 kinds of dependences). By
> >> exploring these chains, we can find the right pairs to test,
> >> accounting for control flow and the confusion caused by procedure
> >> calls, etc.
> >>
> >
> > This sounds very useful.
> >
> >>
> >> I'm not yet sure how I'll proceed for (1).  It's seems natural and
> >> wise to take advantage of the scalar evolutions, but they're new to me
> >> and I'll need to study them more.  I'd like to provide an interface
> >> that's independent of (2), so that it can be used independently, e.g.,
> >> by a software pipeliner.
> >
> > This makes sense.
> >
> >> I'd also like to provide a caching interface, so we can avoid
> >> re-testing pairs of references with identical subscript forms.  It
> >> also seems desirable to start with relatively simple tests, and expand
> >> the coverage over time.  We'll see how it goes.
> >
> > For both (1) and (2), if you'd like to sketch out the interface you have
> > in mind, I'd be happy to provide some feedback.
> >
> > On a practical note, I think that it is important that the mechanisms
> > developed for this support both direct multidimensional indexing
> > (a[i][j][k]) and also manually-expanded indexing (a[n*(j+n*i) + k]).
> 
> It would be good to have multidimensional arrays in LLVM: note that
> "recognizing" the multidimensional access from a linearized access is
> not trivial.  This was the original reason why I have started working
> on the gimple representation in GCC: the RTL has all the memory
> accesses linearized as in gep http://llvm.org/docs/GetElementPtr.html
> and so you have lost the type info about the array shape for memory
> accesses.

I agree, to some extent, but an analysis pass would also be quite
useful. There is a lot of real C/C++ code that uses linearized access,
and it will be very important to handle those cases.

> 
> > Recognizing the latter may require some specific idiom-recognition code
> > (and scalar evolution analysis should be very useful for this).
> 
> Unfortunately the SCEV does not help much in recognizing a multi-dim
> access.

I've not thought this through in detail, but it would seem helpful.
Let's say that I have a loop with two induction variables, i and j, and
I want to see if an expression looks like i*n+j for some constant n (and
I also need to determine n). Then I would take the expression, subtract
j (SE->getMinusSCEV) and divide by i. If the result is a SCEVConstant,
then I have n and I'm done. Otherwise, I can try something else, (or
fail). Maybe, for example, n is not a constant, but is a loop-invariant
scalar, etc.

 -Hal

> 
> Sebastian
> --
> Qualcomm Innovation Center, Inc is a member of Code Aurora Forum

-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory