[LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]

[Matthieu Delahaye]

On Wed, 2008-09-03 at 10:50 -0500, David Greene wrote:
> On Friday 29 August 2008 12:15, Matthieu Delahaye wrote:
> 
> > > - DataDependenceAnalysis will select various dependence tests based
> > > on
> > > user selection.  We want a interface similar to AnalysisGroup used
> > > by
> > > Alias Analysis, but we also want to allow the possibility of running
> > > multiple tests at the same time.
> >
> > That will probably be the most difficult part. But with all the people
> > that shows interest on using or adding new analysis here, I am hopeful
> > we will obtain an acceptable stable API.
> 
> Can you elaborate on the complexity here?  Why is this any different from
> the way AliasAnalysis works?  Yes, there will be a different API but the
> concept is the same -- if I can't make a solid decision, hand it off to the
> next analysis in the chain.


I was actually talking about the API itself but I do think the chaining
itself is not as easy either. 

First, note that my knowledge of data dependence analysis is much more
theoretical than practical. Which means that any possibility I am
suggesting needs to be pondered by their actual usefulness and that it
does not necessarily means it can be implemented under reasonable
conditions. Any critic is more than welcome.

API: This is the matter of providing the possibilities to ask useful
questions, and providing useful answers. [in the pow of the passes that
are using the analysis].

The "textbook" version would be: give me the memory dependency(ies)
between these two instructions. With the possibility to select the
"dialect" of the answer:
- There is a dependency, there is not, or maybe
- Direction vectors
- Distance vectors
...

For many of us, including myself, this is all I would need. But if I
would be working on vectorization, another question like "Tell me
whether there is no distance vector with a distance on the last level
less than 4" is more meaningful. And:
- this can be proved far faster than generating the whole dependencies
(I have seen 50x speedup figures, but this is implementation dependent)
- could be proved even in some cases where the Omega test cannot.

So two questions: Is there any other kind of queries? Are they actually
useful?

Now for the "useful" answers: We have to admit that the proportion of
loops whose upper bounds are known constant values at compile-time is
decreasing rapidly... Some analysis handle that well at the cost of
potentially generating different results predicated by conditions on
these symbolic values. The expression of these predicates might not be
trivial.

This is what I had in mind when I talked above the difficulty of having
a good API that do not change every time a new analysis is added. I
doubt this API could be defined without the review of analysis users and
writers.

Now about the chaining: it is a matter of precision. We want either the
exact result or, when it is not possible, we might want the most precise
conservative answer [when we want to know more than yes/no/maybe].

The solution, as you describe it, is ok as long as one can provide an
exact result. However, when no test can: 
- You may have obtained an exact result by making them work together
rather than independently.
- What conservative answer to provide when each test failed, but
different conservative answers are provided from more than two tests?

Matthieu