On 30 September 2011 12:04, Simon Peyton-Jones <[email protected]> wrote: > Why is this an *analysis*? Why can't we simply declare to LLVM that certain > things don't alias?
We already do this to the extent possible - both the SpArg and the HpArg are tagged with "noalias". The problem is that this is only enough to tell LLVM that pointers based on SpArg do not alias with pointers based on *an argument other than SpArg*. It is not enough to tell LLVM that pointers based on SpArg do not alias with e.g. pointers arriving via a "load". My analysis claims to LLVM that SpArg cannot alias with *any other pointer* other than one visibly based on SpArg. The correctness of this crucially depends on the fact that we never store away SpArg and then load it back later on. In fact, the unsimplified LLVM IR generated by GHC **does** store away SpArg and load it back later on! Luckily, LLVM can quickly remove these stores of Sp even without good alias information. But for safety, my alias analysis does an escape check that turns off its more precise alias information if SpArg seems to escape, as it does in these early programs. I think it might be possible to reuse LLVM's type based alias analysis to express the heap-does-not-alias-with-stack property, rather than writing our own custom one. However: 1. We will have to decorate all pointer variables in our LLVM IR with some metadata (SpArg-based pointers will need to get different metadata to all other pointers, so we will need to do some dataflow analysis here) 2. There is no guarantee this metadata is preserved by LLVM's existing IR passes 3. LLVM will not use this metadata to tag any new pointer variables it synthesises in the course of optimisation 4. It would not benefit from the escape analysis I have implemented, so LLVM could potentially do unsafe optimisations So I *really* think a custom alias analyser is the way to go. Furthermore, it is a really modular solution - we don't need to change the rest of LLVM or the code generator at all! > At the moment we print out ascii stuff which LLVM parses. Would it be easier > to call LLVM directly via an API? I guess what are getting at is if we were using the LLVM API we might be able to avoid this business about installing a shared library, and just supply the LLVM API with a pointer to our analysis pass. I think this is right, though of course we would still need to be able to compile that one file containing the pass with a C++ compiler. Changing LLVM to use the API would be a reasonably major undertaking though. > And if it is an analysis, how are the results expressed to LLVM? LLVM's interface to the analysis is roughly a function "bool alias(Location&, Location&)" that is meant to return whether two "locations" (roughly, LLVM variables) can alias. Whenever the correctness of an analysis depends on alias information, it makes use of this function to check safety. Does that answer your question? Max _______________________________________________ Cvs-ghc mailing list [email protected] http://www.haskell.org/mailman/listinfo/cvs-ghc
