Dependence Analysis

Hi, everyone. I've been examining llvm for a while and been duly impressed. I'd like to contribute in the area of dependence analysis, and a good place to start seems to be in the transformation of pointers to explicit array accesses. Is anyone else working on this? If not, does this seem a plausible place to start and how would be the best way to go about it?

Thanks,
Naftali

LLVM already includes this: the -indvars pass. It turns things like this:

int *P = for (...; ... ; ++P)
    *P

to:

int *P = ...
for (int i = 0; ... ; ++i)
   P[i]

If you're interested in dependence analysis, the next important step is to start analyzing distance and direction vectors.

-Chris

LLVM already includes this: the -indvars pass. It turns things like this:

int *P = for (...; ... ; ++P)
  *P

to:

int *P = ...
for (int i = 0; ... ; ++i)
P[i]

If you're interested in dependence analysis, the next important step is to start analyzing distance and direction vectors.

You can check out lib/Target/SparcV9/ModuloScheduling/DependenceAnalyzer.cpp

It uses Alias Analysis and Scalar Evolution to figure out dependences and distances for single dimensional arrays. It needs more work, but its a start. Its not used by anyone currently. I wrote it for my ModuloScheduling work.

-Tanya

Naftali,

Tanya Lattner has already made a start on the dependence analysis itself but is not working on it any more. That is a much bigger project than the pointer-to-array-indexing conversion. If you are interested in picking up on that, we should discuss it (probably offline). There are some algorithmic choices that I think are important here, to combine speed and generality.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/

I've been rereading about dependencies and distance and direction
vectors recently and was thinking of giving this a shot in LLVM as
well (in my copious spare time). Naftali, if you're interested in
working on this, perhaps we could coordinate our efforts.

-bw