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
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
David, I agree with all of what you said here except for one point:
<snip>
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.
That may not be the case because the compiler may need dependence "breaking conditions" to generate this code. For example, such a condition might say [a particular instruction pair does not have a dependence if] "N > sizeof(A)" or "i + j < 10". The dependence *test* usually has to generate this condition, e.g., polyhedral analyses like Omega can do this.
The same functionality could also be useful for interactive porting tools helping users port programs to a parallel language, one of the target projects for the dependence analyzer here at Illinois.
Having said that ...
I think the
interface you've outlined above is sufficient for now. We'll gain experience
and add to it later if necessary.
<snip>
... I agree: let's do the basic Yes/No/Maybe and Direction/Distance vectors for now, and add more sophisticated queries as clients emerge for them.
--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve