Hal wrote:> 3. Loop vectorization - It would be nice to have, in addition to > basic-block vectorization, a more-traditional loop vectorization pass. I > think that we'll need a better loop analysis pass in order for this to > happen. Some of this was started in LoopDependenceAnalysis, but that > pass is not yet finished. We'll need something like this to recognize > affine memory references, etc.I've recently started working on a dependence analyzer for LLVM. We're more interested in parallelization than vectorization, 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 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. 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. 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. Preston -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120203/db3a1f75/attachment.html>
On Fri, 2012-02-03 at 20:59 -0800, Preston Briggs wrote:> Hal wrote: > > 3. Loop vectorization - It would be nice to have, in addition to > > basic-block vectorization, a more-traditional loop vectorization > pass. I > > think that we'll need a better loop analysis pass in order for this > to > > happen. Some of this was started in LoopDependenceAnalysis, but that > > pass is not yet finished. We'll need something like this to > recognize > > affine memory references, etc. > > I've recently started working on a dependence analyzer for LLVM.Great!> We're more interested in parallelization than vectorization,I am also interested in parallalization, but that is another story ;)> 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 > 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]). Recognizing the latter may require some specific idiom-recognition code (and scalar evolution analysis should be very useful for this). -Hal> > > Preston > >-- Hal Finkel Postdoctoral Appointee Leadership Computing Facility Argonne National Laboratory
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, andWould 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