Hi all! I have recently finished the first prototype of data dependence analysis for LLVM. Now that I have some more time I would like to prepare a "production" version. In this post I'll try to describe the current state and propose a work plan. Currently, the analysis has a very simplified interface (it allows to query for dependence between two given instructions or whether a given loop carries any dependence). Also, loop independent dependencies aren't supported yet. I focused on the main part - an algorithm that checks for dependence given two instructions. It uses alias analysis info and some techniques from the Allen & Kennedy book (ZIV test, strong SIV test, Banerjee test, simpler form of the Delta test). Alexandre X. Duchateau and Albert Sibelnik added the Omega test based on the Omega library. I am going to go the Developer Policy's way and work incrementally with your feedback. What do you think of the following work plan? 1. Think of possible clients of the analysis and gather their requirements. 2. Design analysis interface. 3. Implement the simplest client for testing purposes. (In the optimistic scenario others starts to implement more clients at this stage and give better feedback about the interface;) ) 4. Design the analysis internals in a way that make future extensions (ie. adding different dependence tests) possible. 5. Implement the analysis and the initial set of dependence tests. While working on a prototype I gathered some thought on all the above steps. Also, when I write 'implement' I don't mean starting from scratch but using the current code as a base. -Wojtek
On Jun 6, 2008, at 8:43 AM, Wojciech Matyjewicz wrote:> Hi all! > > I have recently finished the first prototype of data dependence > analysis > for LLVM. Now that I have some more time I would like to prepare a > "production" version. In this post I'll try to describe the current > state and propose a work plan.> > > Currently, the analysis has a very simplified interface (it allows to > query for dependence between two given instructions or whether a given > loop carries any dependence). Also, loop independent dependencies > aren't > supported yet. I focused on the main part - an algorithm that checks > for > dependence given two instructions. It uses alias analysis info and > some > techniques from the Allen & Kennedy book (ZIV test, strong SIV test, > Banerjee test, simpler form of the Delta test). Alexandre X. Duchateau > and Albert Sibelnik added the Omega test based on the Omega library.Cool! Thanks for posting your status.> > > I am going to go the Developer Policy's way and work incrementally > with > your feedback. What do you think of the following work plan? > 1. Think of possible clients of the analysis and gather their > requirements. > 2. Design analysis interface. > 3. Implement the simplest client for testing purposes. (In the > optimistic scenario others starts to implement more clients at this > stage and give better feedback about the interface;) ) > 4. Design the analysis internals in a way that make future extensions > (ie. adding different dependence tests) possible. > 5. Implement the analysis and the initial set of dependence tests. > > > While working on a prototype I gathered some thought on all the above > steps. Also, when I write 'implement' I don't mean starting from > scratch > but using the current code as a base.This sounds like a reasonable plan to me. I look forward to seeing your design ideas. Dan
On Jun 6, 2008, at 8:43 AM, Wojciech Matyjewicz wrote:> Hi all!Hi Wojciech, sorry for the delay.> I have recently finished the first prototype of data dependence > analysis > for LLVM. Now that I have some more time I would like to prepare a > "production" version. In this post I'll try to describe the current > state and propose a work plan.Nice! This is a huge gap in LLVM, I would love to see some progress being made here.> Currently, the analysis has a very simplified interface (it allows to > query for dependence between two given instructions or whether a given > loop carries any dependence). Also, loop independent dependencies > aren't > supported yet. I focused on the main part - an algorithm that checks > for > dependence given two instructions. It uses alias analysis info and > some > techniques from the Allen & Kennedy book (ZIV test, strong SIV test, > Banerjee test, simpler form of the Delta test). Alexandre X. Duchateau > and Albert Sibelnik added the Omega test based on the Omega library.That makes sense.> I am going to go the Developer Policy's way and work incrementally > with > your feedback. What do you think of the following work plan? > 1. Think of possible clients of the analysis and gather their > requirements. > 2. Design analysis interface.Ok.> > 3. Implement the simplest client for testing purposes. (In the > optimistic scenario others starts to implement more clients at this > stage and give better feedback about the interface;) )Sounds good. It would also be useful to have a client that just does an "all pairs" query and prints out the output (e.g. alias analysis has AliasAnalysisCounter.cpp). This is useful for validation as well as precision evaluation of different implementations.> 4. Design the analysis internals in a way that make future extensions > (ie. adding different dependence tests) possible. > 5. Implement the analysis and the initial set of dependence tests. > > While working on a prototype I gathered some thought on all the above > steps. Also, when I write 'implement' I don't mean starting from > scratch > but using the current code as a base.Sounds great to me! -Chris
Hi Chris, Wojciech, Data Dependence Analysis is great. I am sure it would help the loop optimizations effort that Dr. Adve mentioned last month. After we have DDA we can implement software pipelining* (modulo scheduler). Chris, would you accept a software pipelining transformation as a pass or would you want it as part of the different backends ? Nadav Rotem * http://en.wikipedia.org/wiki/Software_pipelining