[LLVMdev] Vectorization: Next Steps

[Sebastian Pop]

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?  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.

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.

> 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.

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