On 22.06.2011, at 17:03, John Criswell wrote:> On 6/22/11 5:34 AM, Andreas Wilhelm wrote: >> >> 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: > > 1) DSA works with LLVM 2.7; I don't believe it works with LLVM mainline yet. > 2) 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> >> Thanks in advance, >> Andreas >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110624/2d546171/attachment.html>
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.
On 6/24/11 5:20 AM, Andreas Wilhelm wrote:> > 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: http://llvm.org/doxygen/classllvm_1_1MemoryDependenceAnalysis.html. 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 (http://llvm.org/pubs/2007-06-10-PLDI-DSA.html) and Chris Lattner's thesis (http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html). 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.> > Andreas >
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 Am 24.06.2011 um 17:45 schrieb John Criswell:> 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 (http://llvm.org/pubs/2007-06-10-PLDI-DSA.html) and Chris Lattner's thesis (http://llvm.org/pubs/2005-05-04-LattnerPHDThesis.html). > > 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.-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110625/caa4fb7e/attachment.html>