[LLVMdev] 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