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. -Chris -- http://nondot.org/sabre/ http://llvm.org/
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
>> 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.> > > Sebastian > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev--Vikram http://www.cs.uiuc.edu/~vadve http://llvm.org