[LLVMdev] Data dependence analysis

[Dan Gohman]

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