llvm dev - Sep 2008 - [LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]

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.

                                                  -Dave

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

On Wednesday 03 September 2008 12:39, Matthieu Delahaye
wrote:
> 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
Right.
> 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:
So why not have the caller examine the distance vectors?  We don't need
an additional API to ask this question.  The analysis should just do the
analysis, it doesn't need to know every possible use of the results.
> - this can be proved far faster than generating the whole dependencies
> (I have seen 50x speedup figures, but this is implementation dependent)
Just to clarify, are you saying answering the "any distance < 4"
question can
be faster than generating all the distance vectors?  Ok, yeah, I can believe
that, so we probably do want an API for that.  So ignore my previous 
paragraph.  :)
> - could be proved even in some cases where the Omega test cannot.
Ok, I can believe that too.
> So two questions: Is there any other kind of queries? Are they actually
> useful?
If we need more queries later we can always add them.

The way I would approach this is to implement the basic API (yes/no/maybe
and distance/direction vectors) and let clients use that information to derive
their own answers.  After some experience with that we'll have a better
sense
of what other APIs might be useful.  Then we can start adding things like the
"distance < N" query.
> 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... 
Depends what you mean by "known" and "at compile time." 
It's not uncommon
to generate conditional code where there are runtime checks for loop bounds 
and a selection among code generated with different parallelization 
strategies.  So strictly speaking the loop bounds are not statically known but 
the compiler makes them known to itself for special cases by inserting runtime 
tests.

The compiler can also use symbol information to infer minimum and maximum
bounds.  For example, it's reasonable to assume a loop won't iterate
beyond
the bounds of the arrays used in the loop, so if you have symbol information 
you can figure more things out than what you'd get from simply examining the
code.  Range analysis can also play a role here.
> Some analysis handle that well at the cost of potentially generating 
> different results predicated by conditions on these symbolic values.
You read my mind.  :)  Though what do you mean by "different results"
here?
Different code?  I hope you don't mean "different answers."  :)
> The  expression of these predicates might not be  trivial.
Funny story, I've seen literally PAGES of scalar code that attempts to
figure
out whether vectorization applies at runtime and then selects the vector code 
if it does.  Usually vectorization applies and the vector code is so fast it 
more than makes up for the additional computation involved in the checks.
> 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.
But ultimately these "tricks" such as runtime decision-making are not
under
the purvue of the memory dependence analysis.  In these cases the compiler is 
"forcing" an answer it wants by create code paths where it knows
certain
properties.  There's no analysis necessary because the compiler created
those
paths in the first place with very specific goals in mind.  I think the
interface you've outlined above is sufficient for now.  We'll gain
experience
and add to it later if necessary.
> 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].
Right.
> 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.
Possibly, though I don't have a good picture of what "work
together" looks
like.  When I think about alias analysis, for example, I think of cheaper 
analyses chaining to more expensive ones.  The more expensive ones subsume the 
functionality of the cheaper ones.  This property may not always hold for 
memory dependence analysis.  But in those cases, is it really possible to 
combine results and come up with something more precise?  I don't know.
Again, I think it's reasonable to start with a model based on how alias 
analysis works and then enhance the model if we find cases where this kind of 
interaction is beneficial.

The key is not to make the perfect the enemy of the good.  Get something going 
now.  We can always make it better later.
> - What conservative answer to provide when each test failed, but
> different conservative answers are provided from more than two tests?
I would think most of the time it would be pretty clear (you want to take the 
greatest distance, for example).  For those cases where it's not clear, just
pick one for now.  We'll gain experience and tune it later.

                                                       -Dave