[LLVMdev] Array Dependence Analysis

[Wojciech Matyjewicz]

Hi,

> As part of the advanced compilers course semester project (at UIUC), we
> are starting to implement array dependence analysis for LLVM.  

I'm currently working on a similar project and hoping to finish it in
about two weeks. I am going to share the code when it's ready.  I've
spent some time analyzing LLVM code for scientific and "ordinary"
programs to find out what is necessary to make the IR-level array
dependence analysis usable. I've designed techniques that I know will
work for chosen programs, but the general precision of the pass
implementation is still a mystery to me. If it appears acceptable, you
may find some concepts useful for your project. Otherwise, you'll at
least know what isn't useful:)

As for now, I'm focusing on the dependency analysis engine and publish
only a simplistic interface (it only allows to check whether a loop
carries a memory dependence). However, the engine is quite
self-contained and should be easy to attach to a different interface.
For instance, the engine will be able to find dependence direction
vectors for an instruction pair.

> Any suggestion on features, tests and/or interface are welcome.

>From my experience I can say it's essential to use a precise alias
analysis as the base for the array dependence analysis. Fortunately,
using Data Structure or Andersen's AA for the whole program can provide
really good results.

Also, on this list I was advised some time ago to look at
the Omega test:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2008-January/012185.html
Having taken a look at the Omega library interface I think it shouldn't
be a complex task to use it for dependence testing. I'm thinking of
adding it to my implementation in the future. It could probably replace
Banerjee test. If you're interested, I advise to use the version patched
by Jerry James: http://jjames.fedorapeople.org/omega/

Wojtek