Data dependence analysis

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Data dependence analysis

Wojciech Matyjewicz
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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Data dependence analysis

Dan Gohman-2

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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Data dependence analysis

Chris Lattner
In reply to this post by Wojciech Matyjewicz

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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Data dependence analysis

nadav256
In reply to this post by Wojciech Matyjewicz
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


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Data dependence analysis

Tanya Lattner-2

> 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 ?

For my masters thesis I implemented Modulo Scheduling in the original LLVM
Sparc backend (since removed though). To me, its seems very specific to a
certain target and should be part of specific backend as machine function
pass (ie. sparc). How do you plan to make it target independent?

-Tanya


>
> Nadav Rotem
>
> * http://en.wikipedia.org/wiki/Software_pipelining
>
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Data dependence analysis

Chris Lattner
In reply to this post by nadav256
On Mon, 14 Jul 2008, Nadav Rotem wrote:
> 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 ?

Hi Nadav,

I'm not sure what you mean by being a pass vs being a part of the
different backends.

Ideally it would be a code generator pass that could be used by any
target.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev