Data dependence analysis

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

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

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

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

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