Hi, On Nov 29, 2007 6:19 PM, Chris Lattner <sabre at nondot.org> wrote:> On Thu, 29 Nov 2007, Wojciech Matyjewicz wrote: > > As for the dependence analysis, I need this piece for my project, and I > > am preparing myself to write it. > > Great! > > > I am currently studying some papers, but haven't yet decided on the > > method. Maybe some of you have experience in the area and would like to > > advise me something? In the next few days I am going to take a look at > > the methods based on chains of recurrences algebra. They seem > > particularly interesting because chrecs are already implemented in the > > scalar evolution pass. > > Yes, I'd strongly suggest implementing one of the approaches based on the > chrec analysis we have in the scev pass. >Yup, just get the array accesses under scev form, and set a constraint system from these. Once you set up the constraint systems for the dependence distance vectors, you're almost done. You can look at how this is set up in gcc trunk tree-data-ref.c, and search for omega. I would recommend the omega test: get the c++ code for omega lib from http://www.cs.umd.edu/projects/omega/ Sebastian
>> Yup, just get the array accesses under scev form, and set a constraint >> system from these. Once you set up the constraint systems for the >> dependence distance vectors, you're almost done. You can look at how >> this is set up in gcc trunk tree-data-ref.c, and search for omega. >> >> I would recommend the omega test: get the c++ code for omega lib from >> http://www.cs.umd.edu/projects/omega/ > > Regardless of which solver you use, you should keep a clean interface > between your constraint representation and the solver. I like Omega a > lot and it is a fine choice for the first solver. Although it is very > powerful, even it cannot handle symbolic loop strides. Perhaps more > importantly for common uses, for many trivial cases (A[x] and A[x+1]), > setting up the Omega data structures to invoke the solver can be too > heavyweight. It could be worthwhile to add one or more simple solvers > (see the Allen and Kennedy textbook for examples) before falling back > on Omega.Sebastian, Vikram, thank you for the advices. My initial plan was to implement the methods from the Allen and Kennedy book. I'll see if I find time to add the Omega solver as a fallback, too. I am not very familiar with GCC internals, but having taken a look at tree-data-ref.c, it seems it would be the same approach as there. Wojtek
On Jan 17, 2008 6:25 PM, Vikram S. Adve <vadve at uiuc.edu> wrote:> >> Yes, I'd strongly suggest implementing one of the approaches based > >> on the > >> chrec analysis we have in the scev pass. > >> > > > > Yup, just get the array accesses under scev form, and set a constraint > > system from these. Once you set up the constraint systems for the > > dependence distance vectors, you're almost done. You can look at how > > this is set up in gcc trunk tree-data-ref.c, and search for omega. > > > > I would recommend the omega test: get the c++ code for omega lib from > > http://www.cs.umd.edu/projects/omega/ > > Regardless of which solver you use, you should keep a clean interface > between your constraint representation and the solver. I like Omega a > lot and it is a fine choice for the first solver. Although it is very > powerful, even it cannot handle symbolic loop strides. Perhaps more > importantly for common uses, for many trivial cases (A[x] and A[x+1]), > setting up the Omega data structures to invoke the solver can be too > heavyweight. It could be worthwhile to add one or more simple solvers > (see the Allen and Kennedy textbook for examples) before falling back > on Omega.Sure, and this is exactly what tree-data-ref does (we use a number of simple solvers, but leave the hard stuff to omega)