[LLVMdev] Data dependence analysis

[Chris Lattner]

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