"dataflow rewriting engine"

[Manuel M T Chakravarty]

Deborah Goldsmith:
> Has there been any thought about working with the LLVM project? I  
> didn't find anything on the wiki along those lines.

I have only had a rather brief look at LLVM, but my understanding at  
the moment is that LLVM would not be able to support one of GHC's  
current code layout optimisations.  More precisely, with LLVM, it  
would not be possible to enforce that the meta data for a closure is  
placed right before (in terms of layout in the address space) the code  
executing the "eval" method of that same closure.  GHC uses that to  
have the closure code pointer point directly to the "eval" code (and  
hence also by an appropriate offset) to the various fields of the meta  
data.  If that layout cannot be ensured, GHC needs to take one more  
indirection to execute "evals" (which is a very frequent operation) -  
this is what an unregistered build does btw.

However, I am not convinced that this layout optimisation is really  
gaining that much extra performance these days.  In particular, since  
dynamic pointer tagging, very short running "evals" (for which the  
extra indirection incurs the largest overhead) have become less  
frequent.  Even if there is a slight performance regression, I think,  
it would be worthwhile to consider giving up on the described layout  
constraint.  It is the Last Quirk that keeps GHC from using standard  
compiler back-ends (such as LLVM), and I suspect, it is not worth it  
anymore.

When we discussed this last, Simon Marlow planned to run benchmarks to  
determine how much performance the layout optimisation gains us these  
days.  Simon, did you ever get around to that?

Manuel


> On Aug 26, 2008, at 10:57 AM, Don Stewart wrote:
>
>> I think we're all rather excited about seeing this stuff land.
>> What's the expected timeline, wrt. ghc 6.10's release?
>>
>> -- Don
>>
>> t-jodias:
>>> I've added some text and links to point the reader in the right
>>> direction. Here's the new text, cribbed from the Wiki:
>>>
>>> Dataflow optimization: We can define a new optimization simply by
>>> defining a lattice of dataflow facts (akin to a specialized logic)  
>>> and
>>> then writing the dataflow-transfer functions found in compiler
>>> textbooks. Handing these functions to the dataflow engine produces a
>>> new optimization that is not only useful on its own, but that can
>>> easily be composed with other optimizations to create an integrated
>>> "superoptimization" that is strictly more powerful than any sequence
>>> of individual optimizations, no matter how many times they are re- 
>>> run.
>>> The dataflow engine is based on (Lerner, Grove, and Chambers 2002
>>> http://citeseer.ist.psu.edu/old/lerner01composing.html); you can  
>>> find
>>> a functional implementation of the dataflow engine presented in
>>> (Ramsey and Dias 2005
>>> http://www.cs.tufts.edu/~nr/pubs/zipcfg-abstract.html).
>>>
>>> Let me know how I can further clarify the text,
>>> -j
>>>
>>>> -----Original Message-----
>>>> From: Simon Peyton-Jones
>>>> Sent: Tuesday, August 26, 2008 1:32 PM
>>>> To: Norman Ramsey; John Dias
>>>> Cc: Chad Scherrer; GHC Users
>>>> Subject: RE: "dataflow rewriting engine"
>>>>
>>>> Norman, John
>>>>
>>>> Would you care to respond to this? (Perhaps by amplifying the wiki
>>>> page?)  A good starting point is perhaps Craig's paper.
>>>>
>>>> Simon
>>>>
>>>> | -----Original Message-----
>>>> | From: glasgow-haskell-users-bounces at haskell.org [mailto:glasgow-
>>>> haskell-users-bounces at haskell.org] On
>>>> | Behalf Of Chad Scherrer
>>>> | Sent: 22 August 2008 22:21
>>>> | To: GHC Users
>>>> | Subject: "dataflow rewriting engine"
>>>> |
>>>> | Hello GHC,
>>>> |
>>>> | This page
>>>> |
>>>> http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/Integrated
>>>> CodeGen
>>>> | mentions a to-be-developed "dataflow rewriting engine". Can  
>>>> someone
>>>> | please send a description of what this will do?
>>>> |
>>>> | Thanks!
>>>> | --
>>>> |
>>>> | Chad Scherrer
>>>> |
>>>> | "Time flies like an arrow; fruit flies like a banana" --  
>>>> Groucho Marx
>>>> | _______________________________________________
>>>> | Glasgow-haskell-users mailing list
>>>> | Glasgow-haskell-users at haskell.org
>>>> | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>>>
>>> _______________________________________________
>>> Glasgow-haskell-users mailing list
>>> Glasgow-haskell-users at haskell.org
>>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>>>
>> _______________________________________________
>> Glasgow-haskell-users mailing list
>> Glasgow-haskell-users at haskell.org
>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users