[LLVMdev] Vectorization: Next Steps
hfinkel at anl.gov
Mon Feb 6 13:56:11 PST 2012
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
> 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
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
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
> Qualcomm Innovation Center, Inc is a member of Code Aurora Forum
Leadership Computing Facility
Argonne National Laboratory
More information about the llvm-dev