[LLVMdev] Array Dependence Analysis

[Wojciech Matyjewicz]

Vikram,

> If you like, I can help guide this SoC project.

Unfortunately, I am not eligible for the SoC programme as I will be
graduating in April. In fact, data dependence analysis (in basic version
at least) is one of my master thesis' parts. I should get the basic
version working in a few days. Internally, it is more or less the
algorithm described in the textbook by Allen and Kennedy, but externally
it has very limited interface. I was planning to improve it after the
graduation, if my time allows. But now, as there is more people to work
on the issue it may be more interesting to develop something better.

> I would also like to see if we can coordinate with Alex and Albert, who are 
> doing the class project here.

Although I'm willing to help, I suppose Alex and Albert would feel more
comfortable if the schedule of their course project was independent of a
guy living on another hemisphere:) My intention was to signalize that
some efforts towards implementing dependence analysis have already been
made. I will try to post my first prototype in the beginning of April.
I'll also try to write down some thoughts about the pass interface, its
internal structure and, also, problems I've encountered during my
"research". Some of the problems aren't directly connected to dependence
analysis but block it from being precise. For example, in codes coming
from translating Fortran programs, arrays that are declared in COMMON
blocks and passed as function arguments become a problem for alias
analysis. Often a conservative "there is a dependence" answer must be
returned without, even, checking indices. But returning to the main
subject, maybe some parts of my prototype and some thoughts would be
useful for the "next generation" implementation...

As for my role, I'm ready to share the experience I've gained while
implementing the prototype. Also, if there is a self-contained part that
can be written independently I may try to do it. I'd be happy to take
advantage of your guidance then.

> As a first comment, your 3 layers are a good organization but two comments:
> 
> 1. Layer 1 shd also look at loop bounds and array bounds: those can be used 
> to disprove some deps.

Currently, I do use loop bounds to disprove deps. However I don't take
into account trapezoidal or triangular loops.

> 2. The interface will also need to compute direction and perhaps distance 
> vectors.  Those may or may not be easy to put in one of your layers (say, 
> layer 3, where they belong).

Yes. "The layers" is only a concept describing which other analysis
queries the given query depends on. Internally, the analysis can be one
class so propagating direction vector from the lowest layer (where they
are computed) to the highest (where they are given to the client) is not
a problem.

Wojtek