As part of the advanced compilers course semester project (at UIUC), we are starting to implement array dependence analysis for LLVM. As of now we are considering GCD and Banerjee tests. Any suggestion on features, tests and/or interface are welcome. Our deadline is at the beginning of may so hopefully by then we will have a working prototype to submit. -- Alexandre X. Duchâteau & Albert Sidelnik -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080315/56316599/attachment.html>
Hi,> As part of the advanced compilers course semester project (at UIUC), we > are starting to implement array dependence analysis for LLVM.I'm currently working on a similar project and hoping to finish it in about two weeks. I am going to share the code when it's ready. I've spent some time analyzing LLVM code for scientific and "ordinary" programs to find out what is necessary to make the IR-level array dependence analysis usable. I've designed techniques that I know will work for chosen programs, but the general precision of the pass implementation is still a mystery to me. If it appears acceptable, you may find some concepts useful for your project. Otherwise, you'll at least know what isn't useful:) As for now, I'm focusing on the dependency analysis engine and publish only a simplistic interface (it only allows to check whether a loop carries a memory dependence). However, the engine is quite self-contained and should be easy to attach to a different interface. For instance, the engine will be able to find dependence direction vectors for an instruction pair.> Any suggestion on features, tests and/or interface are welcome.>From my experience I can say it's essential to use a precise aliasanalysis as the base for the array dependence analysis. Fortunately, using Data Structure or Andersen's AA for the whole program can provide really good results. Also, on this list I was advised some time ago to look at the Omega test: http://lists.cs.uiuc.edu/pipermail/llvmdev/2008-January/012185.html Having taken a look at the Omega library interface I think it shouldn't be a complex task to use it for dependence testing. I'm thinking of adding it to my implementation in the future. It could probably replace Banerjee test. If you're interested, I advise to use the version patched by Jerry James: http://jjames.fedorapeople.org/omega/ Wojtek
>> As part of the advanced compilers course semester project (at >> UIUC), we >> are starting to implement array dependence analysis for LLVM.Great! This is something we've needed for a long time.> I'm currently working on a similar project and hoping to finish it in > about two weeks.Cool! I think the most critical part of this is to get a good interface for dependence analysis. There are lots of interesting implementations that have various time/space tradeoffs. For example, it would be great if Omega was available as an option, even if the compiler didn't use it by default. This argues for making dependence analysis implementations pluggable like alias analyses.> As for now, I'm focusing on the dependency analysis engine and publish > only a simplistic interface (it only allows to check whether a loop > carries a memory dependence). However, the engine is quite > self-contained and should be easy to attach to a different interface. > For instance, the engine will be able to find dependence direction > vectors for an instruction pair.Sounds good. If you have the interface nailed down, it would be good to post what the query interface looks like. Vikram and others have a lot of experience with dependence analysis and know what sorts of queries various clients are interested in. They can help give feedback on the direction you're pursuing independent of the implementation.>> Any suggestion on features, tests and/or interface are welcome.I'd suggest looking at: Using the chains of recurrences algebra for data dependence testing and induction variable substitution MS Thesis, Johnie Birch Array Data Dependence Testing with the Chains of Recurrences Algebra http://citeseer.ist.psu.edu/vanengelen04array.html An empirical evaluation of chains of recurrences for array dependence testing http://doi.acm.org/10.1145/1152154.1152198 etc.>> From my experience I can say it's essential to use a precise alias > analysis as the base for the array dependence analysis. Fortunately, > using Data Structure or Andersen's AA for the whole program can > provide > really good results.Yep, but any particular dep analysis implementation should just require AliasAnalysis instead of a specific implementation. This lets the client (e.g. llvm-gcc) decide what passes to plug together. -Chris
On Mar 15, 2008, at 4:48 PM, Alexandre Duchâteau wrote:> Any suggestion on features, tests and/or interface are welcome.LLVM loop transformer operates at loop level, which is not what many optimizers do in general. So, a loop level interface (i.e. based on LoopPass in llvm) to find loop-carried dependence is preferable to loop optimizer. - Devang
Hi, Devang Patel wrote:> LLVM loop transformer operates at loop level, which is not what many > optimizers do in general. So, a loop level interface (i.e. based on > LoopPass in llvm) to find loop-carried dependence is preferable to > loop optimizer.Do you mean making Array Dependence Analysis a loop-level analysis? Would its results be available for some function-level pass then? Wojtek