Hello,
I’m looking for a way to identify dependencies of function-pairs (memory-dependency, control-dependency…) in order to parallelize them.
For aliasing problems I use the DataStructureAnalysis. To solve simple memory- and control-dependency problems I want to use
memdep. But unfortunately I even fail with following simple C++ example…
int a( int n) { return n; }
int b( int n) { return n; }
int c( int n) { return n; }
int main( int argc, char** argv) {
int x = a( argc);
b( 0);
if ( x)
x = 0;
return ( c( x));
}
… The result of memdep shows a dependency between the callsite of b() and the call of a(). Why?
Moreover I want to get the dependency between the call to c() and the result of a(). How can I obtain this?
Thanks in advance,
Andreas
Hello,
I’m looking for a way to identify dependencies of function-pairs (memory-dependency, control-dependency…) in order to parallelize them.
For aliasing problems I use the DataStructureAnalysis.
I’m assuming that this is the DSA analysis in the poolalloc module. Be forewarned that:
- DSA works with LLVM 2.7; I don’t believe it works with LLVM mainline yet.
- The alias analysis interface to DSA hasn’t been maintained in awhile; you’ll need to examine the DSGraphs directly.
To solve simple memory- and control-dependency problems I want to use
memdep. But unfortunately I even fail with following simple C++ example…
int a( int n) { return n; }
int b( int n) { return n; }
int c( int n) { return n; }
int main( int argc, char** argv) {
int x = a( argc);
b( 0);
if ( x)
x = 0;
return ( c( x));
}
… The result of memdep shows a dependency between the callsite of b() and the call of a(). Why?
Moreover I want to get the dependency between the call to c() and the result of a(). How can I obtain this?
I can’t comment on what memdep does as I’ve never used it; others more knowledgeable will have to comment.
Regarding your last question on following the def of x to the use in c(x), that looks like a simple data-flow analysis problem; just follow the def-use chain of the SSA variables from the call of a() to the call of c() in main().
– John T.
Hello,
I’m looking for a way to identify dependencies of function-pairs (memory-dependency, control-dependency…) in order to parallelize them.
For aliasing problems I use the DataStructureAnalysis.
I’m assuming that this is the DSA analysis in the poolalloc module. Be forewarned that:
- DSA works with LLVM 2.7; I don’t believe it works with LLVM mainline yet.
- The alias analysis interface to DSA hasn’t been maintained in awhile; you’ll need to examine the DSGraphs directly.
To solve simple memory- and control-dependency problems I want to use
memdep. But unfortunately I even fail with following simple C++ example…
int a( int n) { return n; }
int b( int n) { return n; }
int c( int n) { return n; }
int main( int argc, char** argv) {
int x = a( argc);
b( 0);
if ( x)
x = 0;
return ( c( x));
}
… The result of memdep shows a dependency between the callsite of b() and the call of a(). Why?
Moreover I want to get the dependency between the call to c() and the result of a(). How can I obtain this?
I can’t comment on what memdep does as I’ve never used it; others more knowledgeable will have to comment.
Regarding your last question on following the def of x to the use in c(x), that looks like a simple data-flow analysis problem; just follow the def-use chain of the SSA variables from the call of a() to the call of c() in main().
– John T.
Where can I find some information about MemoryDependenceAnalysis and DataStructureAnalysis?
It would be interesting which kinds of dependence they’re able to find and which not.
Andreas
You may want to look at LICM, which in order to pull a call out of a loop has
to prove that the call is independent of loop variables and other calls in the
loop etc.
Ciao, Duncan.
Where can I find some information about MemoryDependenceAnalysis and DataStructureAnalysis?
It would be interesting which kinds of dependence they're able to find and which not.
I haven't used MemoryDependenceAnalysis myself, but I recommend that you read its doxygen documentation:
LLVM: llvm::MemoryDependenceAnalysis Class Reference.
For DSA, you will want to read the documentation in the docs subdirectory of the poolalloc project (if you don't know how to download poolalloc, please feel free to ask on the list). You may also want to read the paper on DSA (Making Context-Sensitive Points-to Analysis with Heap Cloning Practical For The Real World) and Chris Lattner's thesis (Macroscopic Data Structure Analysis and Optimization).
Note that DSA is a unification-based points-to analysis (among other things): it will generate for you a graph in which each node represents an abstract memory object and the edges represent pointers between memory objects (for example, it can tell you that field 5 of abstract memory object A points to the second field of abstract memory object B). You can build things like reaching definitions analysis, alias analysis, etc., etc. using DSA, but it doesn't do these things for you "out of the box."
-- John T.
That looks good, I already got DSA to run. But now there are thousands of possibilities to compare the pointer arguments of two functions in terms of data dependence.
What is the most “elegant” way?
As a first case I have a pair of functions, function A and function B that are both called in function X. Now I want to check if there is a data dependence between them
with DSA. How would your approach look like?
Ciao, Andreas