tag:blogger.com,1999:blog-18628788513031326052011-11-01T09:13:53.207-04:00No, not that Hadron Collider. The Haskell Compiler.SamBhttp://www.blogger.com/profile/06560268240719951351noreply@blogger.comBlogger291100tag:blogger.com,1999:blog-1862878851303132605.post-88886848204322652672010-10-19T16:09:00.005-04:002010-10-19T18:30:02.791-04:00The exact details are constantly changing but here's a rough overview of the LHC pipeline.<div><ol><li>External Core.<br />We've designed our compiler to use GHC as its frontend. This means that GHC will handle the parsing and type-checking of the Haskell code in addition to some of the optimization (GHC particularly excels at high-level local optimizations). LHC benefits greatly by automatically supporting many of the Haskell extensions offered by GHC.<br />Notable characteristics: Non-strict, local functions, complex let-bindings. Pretty much just Haskell code with zero syntactic sugar.<br />Example snippet:<br /><pre><br /> base:Data.Either.$fShowEither :: ghc-prim:GHC.Types.Int =<br /> ghc-prim:GHC.Types.I# (11::ghc-prim:GHC.Prim.Int#);<br /></pre><br /></li><li>Simple Core.<br />Since External Core isn't immediately ready to be processed into GRIN code, we first translate it to Simple Core by removing or simplifying out a couple of features. The most noticeable feature of External Core is locally scoped functions which simply does not fit in with the GRIN model. When translating to Simple Core, we hoist out all local functions to the top-level.<br />Notable characteristics: Non-strict, no local functions, simplified let-bindings.</li><li>Grin Stage 1.<br />Let me start by introducing GRIN: GRIN (Graph Reduction Intermediate Notation) is a first order, strict, (somewhat) functional language.<br />The purpose of this first stage of grin code is to encode the laziness explicitly. It turns out that you can translate a lazy language (like Simple Core) to a strict language (like GRIN) using only two primitives: Eval and apply. The 'eval' primitives takes a closure, evaluates it if need be and returns the resulting object. The 'apply' primitives simply adds an argument to a closure. Haskell compilers such as GHC, JHC and UHC all use this model for implementing laziness.<br />Notable characteristics: Strict, explicit laziness, opaque closures.<br />Example snippet:<br /><pre><br />base:Foreign.C.Types.@lifted_exp@ w ws =<br /> do x2508 <- @eval ws<br /> case x2508 of<br /> (Cbase:GHC.Int.I32# x#)<br /> -> do x2510 <- unit 11<br /> base:GHC.Show.$wshowSignedInt x2510 x# w<br /></pre><br /></li><li>Grin Stage 2.<br />At the time of writing, each of the mentioned compilers stop at the previous stage (or at what would be their equivalent of that stage).[1] LHC follows in the footsteps of the original GRIN compiler and applies a global control-flow analysis to eliminate/inline all eval/apply primitives. In the end, a lazy/suspended function taking, say, two arguments simply becomes a data constructor with two fields.<br />Notable characteristics: Strict, transparent closures.<br />Example snippet:<br /><pre><br />base:Foreign.Marshal.Utils.toBool1_caf =<br /> do [x2422] <- constant 0<br /> [x2423] <- @realWorld#<br /> [x2424 x2425] <- (foreign lhc_mp_from_int) x2422 x2423<br /> [x2426] <- constant Cinteger-gmp:GHC.Integer.Type.Integer<br /> unit [x2426 x2425]<br /></pre><br /></li><li>Grin Stage 3.<br />Things are starting to get fairly low-level already at stage 2. However, stage 2 is still a bit too high-level for some optimizations to be easily implemented. Stage 3 breaks the code into smaller blocks that can easily be moved, inlined and short-circuited. The code is now sufficiently low-level that it can be pretty-printed as C.<br />Notable characteristics: Functions are broken down to functional units. Otherwise same as stage 2.<br />Example snippet:<br /><pre><br />base:GHC.IO.Encoding.Iconv.@lifted@_lvl60swYU38 rb3 rb4 =<br /> do [x21578] <- @-# rb4 rb3<br /> case x21578 of<br /> 0 -> constant Cghc-prim:GHC.Bool.False<br /> () -> constant Cghc-prim:GHC.Bool.True<br /></pre><br /></li><li>Grin--.<br />Grin-- is the latest addition to the heap and not much is known about it for certain. It is even up for debate whether it belongs to the GRIN family at all since it diverge from the SSA style.<br />The purpose of Grin-- is to provide a vessel for expressing stack operations.<br />Notable characteristics: Operates on global virtual registers, enables explicit stack management.<br />Example snippet:<br /><pre><br />base:GHC.IO.Encoding.Iconv.@lifted@_lvl60swYU38:<br /> do x21578 := -# rb4 rb3<br /> case x21578 of<br /> 0 -> do x88175 := Cghc-prim:GHC.Bool.False<br /> ret<br /> () -> do x88175 := Cghc-prim:GHC.Bool.True<br /> ret<br /></pre><br /></li></ol><div><br /></div></div><div>Feel free to ask if you have any questions on the how and why of LHC.</div><div><br /></div><div>[1] UHC does have the mechanics for lowering the eval/apply primitives but it is not enabled by default.</div><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-8888684820432265267?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com2tag:blogger.com,1999:blog-1862878851303132605.post-18183828391703937642010-10-16T13:13:00.004-04:002010-10-18T08:41:57.500-04:00So, let's talk about garbage collection. Garbage collection is a very interesting topic because it is exceedingly simple in theory but very difficult in practice.<br /><br />To support garbage collection, the key thing a language implementor has to do is to provide a way for the GC to find all live heap pointers (called root pointers). This sounds fairly easy to do but can get quite complicated in the presence of aggressive optimizations and register allocation. A tempting (and often used) solution would be to break encapsulation and make the optimizations aware of the GC requirements. This of course becomes harder the more advanced the optimizations are and with LHC it is pretty much impossible. Consider the following GRIN code:<br /><pre><br />-- 'otherFunction' returns an object of type 'Maybe Int' using two virtual registers.<br />-- If 'x' is 'Nothing' then 'y' is undefined.<br />-- If 'x' is 'Just' then 'y' is a root pointer.<br />someFunction<br /> = do x, y <- otherFunction; .... </pre><br />The above function illustrates that it is not always straightforward to figure out if a variable contains a root pointer. Sometimes determining that requires looking at other variables.<br /><br />So how might we get around this hurdle, you might ask. Well, if the code for marking roots resides in user-code instead of in the RTS then it can be as complex as it needs be. This fits well with the GRIN ideology of expressing an much in user-code as possible.<div><br /></div><div>Now that we're familiar with the problem and the general concept of the solution, let's work out some of the details. Here's what happens when a GC event is triggered, described algorithmically:</div><div><ol><li>Save registers to memory.<br />This is to avoid clobbering the registers and to make them accessible from the GC code.</li><li>Save stack pointer.<br /></li><li>Initiate temporary stack.<br />Local variables from the GC code will be placed on this stack.</li><li>Jump to code for marking root pointers.<br />This will peel back each stack frame until the bottom of the call graph has been reached.</li><li>Discard temporary stack.</li><li>Restore stack pointer</li><li>Restore registers.<br /></li></ol><div>Using the approach for exception involves stack cutting and a more advanced transfer of control which will be discussed in a later post.</div></div><div><br /></div><div>In conclusion, these are the advantages native-code stack walking:</div><div><ul><li>Allows for objects to span registers as well as stack slots.</li><li>Separates the concerns of the optimizer, the garbage collector and the code generator.</li><li>Might be a little bit faster than dynamic stack walking since the stack layout is statically encoded.</li></ul></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-1818382839170393764?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com0tag:blogger.com,1999:blog-1862878851303132605.post-62822558105746752962010-10-16T11:55:00.005-04:002010-10-16T14:40:11.621-04:00Not much has been put up on this blog lately but work is still going on under the hood. The most significant changes in the pipeline are proper tail-calls and a copying garbage collector.<br /><br />As it stands now, LHC uses the C stack extensively but this is obviously not ideal as it makes garbage collection, exceptions and tail-calls nigh impossible to implement. Since the ideal solution of using a third party target language isn't available (neither LLVM or C-- supports arbitrary object models), I've decided to slowly inch closer to a native code generator for LHC. It is fortunate that I find <a href="http://code.haskell.org/lhc/papers/Automatically%20Generating%20the%20Backend%20of%20a%20Compiler%20Using%20Declarative%20Machine%20Descriptions.pdf">Joao Dias' dissertation</a> nearly as interesting as the <a href="http://code.haskell.org/lhc/papers/Code%20Optimization%20Techniques%20for%20Lazy%20Functional%20Languages.pdf">GRIN paper</a>.<br /><br />The first step would be to make the stack layout explicit in the GRIN code. This is necessary but not sufficient for tail-calls (some register coalescing is also required. More on this later). More importantly, accurate garbage collection now becomes a possibility. The way I want to implement garbage collection (and exceptions for that matter) is through alternative return points. This is one of three methods discussed in a <a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/c--/c--exn.htm">C-- paper by Norman Ramsey and Simon Peyton Jones</a> for implementing <span style="font-style: italic;">exceptions</span>. I believe this method is versatile enough for garbage collection as well.<br /><br />The concept revolves around using specialized code at each call site that knows enough about the stack layout to mark root pointers and to jump to the next stack frame. I will describe the details in another blog post. An interesting point is that the garbage collectors could be written in user-code instead of in the RTS.<br /><br />So, to recap: Accurate garbage collection is just around the corner and proper tail-calls will follow in its heels. These two missing features are the reason that so many of the benchmarks fail to run for LHC.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-6282255810574675296?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com0tag:blogger.com,1999:blog-1862878851303132605.post-56536668251129786202010-07-25T17:09:00.002-04:002010-07-25T17:19:31.715-04:00David has been working very hard recently on improving LHC and the nobench benchmark suite, in order to actively benchmark LHC against several other haskell compilers: GHC, JHC and UHC.<br /><br />I figured I'd pop in and announce the benchmarks now that the latest HEAD version of LHC can compile many of them and we can get some meaningful numbers. You can see the results <a href="http://mirror.seize.it/report.html">here</a>. Note there are two columns for JHC: one using john's new garbage collector (via `-fjgc`) and one without, because naturally it tends to affect performance characteristics quite a bit. Some of the numbers are quite interesting: in particular, JHC is nearly 400x faster(!) than GHC on the atom benchmark, and UHC dominates the calendar benchmark currently (we haven't investigated why GHC isn't winning here.) There are also some interesting variations in JHC, where the garbage collector wins in some cases, loses in others, but makes the difference in some between actually running and running out of memory (as you would expect.)<br /><br />Perhaps somewhat regrettably, LHC loses in every benchmark. But we're only just beginning to implement real optimizations now that things are somewhat stabilized and the interface isn't arcane - prior to this we had very few optimizations outside of dead code elimination, simplification and a bit of inlining. David's begun implementing some more exotic optimizations recently, so it'll be interesting to see the results soon.<br /><br />Now we'll be able to more actively see the progress of optimizing haskell compilers. Should be fun!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-5653666825112978620?l=lhc-compiler.blogspot.com' alt='' /></div>Austin Seipphttp://www.blogger.com/profile/08003235138924772402noreply@blogger.com3tag:blogger.com,1999:blog-1862878851303132605.post-18401751328921968012010-06-11T11:22:00.004-04:002010-06-11T11:26:20.445-04:00Urban Boquists PhD thesis, Code Optimization Techniques for Lazy Functional Languages, and its accompanying <a href="http://www.cs.chalmers.se/%7Eboquist/">website</a> have gone offline. Because these papers describe GRIN, the intermediate language we use in LHC, I have decided to mirror Boquist's 3 GRIN-related papers on my own server <a href="http://0xff.ath.cx/%7Eas/code/lhc/papers/">here</a>.<br /><br />If someone inside Chalmers could explain where his papers moved and if we could get them back online, that would be great!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-1840175132892196801?l=lhc-compiler.blogspot.com' alt='' /></div>Austin Seipphttp://www.blogger.com/profile/08003235138924772402noreply@blogger.com1tag:blogger.com,1999:blog-1862878851303132605.post-19358429528597534592010-05-29T12:16:00.004-04:002010-06-02T14:39:59.344-04:00After hacking away for a little bit, I've finally gotten the new user interface for LHC working!<br /><pre><code><br />a ~/code/lhc/test $ lhc --help<br />The LHC Haskell Compiler, v0.11, (C) 2009-2010 David Himmelstrup, Austin Seipp<br /><br />lhc [FLAG] [FILE]<br />Compile Haskell code<br /><br />-? --help[=FORMAT] Show usage information (optional format)<br />-V --version Show version information<br />-v --verbose Higher verbosity<br />-q --quiet Lower verbosity<br />--llvm Use LLVM backend<br />--ghc-opts=VALUE Give GHC frontend options<br />-i --install-library Don't compile; install modules under a library<br />-b --build-library Used when compiling a library (cabal only)<br />-O =VALUE Set optimization level (default=1)<br />--numeric-version Raw numeric version output<br />--supported-languages List supported LANGUAGE pragmas<br />-c Do not link, only compile<br />-o =VALUE output file for binary (default=a.out)<br />--src-dir=VALUE source code directory<br />a ~/code/lhc/test $ lhc HelloWorld.hs<br />[1 of 1] Compiling Main ( HelloWorld.hs, HelloWorld.o )<br />.....................<br />Found fixpoint in 7 iterations.<br />Lowering apply primitives... done in 0.09s<br />Heap points-to analysis... ...........................done in 0.95s<br />HPT fixpoint found in 27 iterations.<br />..................................................................................<br />Found fixpoint in 11 iterations.<br />Compiling C code... done in 0.11s<br />a ~/code/lhc/test $ ./HelloWorld<br />Hello, world!<br />a ~/code/lhc/test $<br /></code></pre><br />The changes should be landing shortly. It will require a patch to Cabal. There is also a bug in cabal/cmdargs that I have not yet tracked down which makes installing cabal packages difficult, although still possible, with this new scheme.<br /><br /><span style="font-weight: bold;">Edit 6-2-2010</span>: all of the necessary patches have been pushed to both LHC and Cabal to make the new user interface work. Try it out (install using 'cabal install -fwith-libs' provided you have the darcs HEAD version of Cabal,) and tell us of any corner cases on IRC (#lhc-compiler on freenode)!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-1935842952859753459?l=lhc-compiler.blogspot.com' alt='' /></div>Austin Seipphttp://www.blogger.com/profile/08003235138924772402noreply@blogger.com1tag:blogger.com,1999:blog-1862878851303132605.post-49276592937633057402010-05-27T11:36:00.008-04:002010-05-27T12:05:02.389-04:00The current user interface for LHC is pretty unwieldy - it requires you to invoke lhc twice: once to generate an external core file, and another to generate the executable with LHC itself.<br /><br />There are a couple of problems with this:<br /><ol><li>It requires -you- to keep track of the generated .hcr files, which is a PITA.<br /></li><li>It makes the test suite complicated, as we currently our own regression tool to handle things like #1. I would like to use Simon Michael's excellent <a href="http://hackage.haskell.org/package/shelltestrunner">shelltestrunner</a> library, but the two-step compilation process would make the test files nastier than they would be, and it so we currently maintain our own regression tool.</li><li>It made some of LHC's code very gross: we basically copied GHC's "Main.hs" file and stuck it in our source tree with some modifications, because we need to be able to accept all GHC options, even "insert arbitrary ghc option here" (for general usage, and cabal install support.) This was - as you could guess, incredibly fragile in terms of maintenance and fowards/backwards compatibility. </insert></li></ol>So now I've devised a new approach. We will instead run GHC in the background, twice: the first, we will call GHC to compile your code with your provided options, and we will generally always stick something like '--make -fext-core -c' onto your command line to generate external core. The second time, we will call GHC <span style="font-style: italic;">again</span>, but instead we will call ghc with the '-M' command line flag. This flag calls GHC to generate a Makefile that describes the dependency information between modules. Running it on Tom Hawkin's <a href="http://hackage.haskell.org/package/atom">atom</a> project, you get something like this:<br /><br /><pre><code># DO NOT DELETE: Beginning of Haskell dependencies<br />Language/Atom/Expressions.o : Language/Atom/Expressions.hs<br />Language/Atom/Elaboration.o : Language/Atom/Elaboration.hs<br />Language/Atom/Elaboration.o : Language/Atom/Expressions.hi<br />Language/Atom/Analysis.o : Language/Atom/Analysis.hs<br />Language/Atom/Analysis.o : Language/Atom/Expressions.hi<br />Language/Atom/Analysis.o : Language/Atom/Elaboration.hi<br />Language/Atom/Scheduling.o : Language/Atom/Scheduling.hs<br />Language/Atom/Scheduling.o : Language/Atom/Elaboration.hi<br />Language/Atom/Scheduling.o : Language/Atom/Analysis.hi<br />Language/Atom/Language.o : Language/Atom/Language.hs<br />Language/Atom/Language.o : Language/Atom/Expressions.hi<br />Language/Atom/Language.o : Language/Atom/Elaboration.hi<br />Language/Atom/Language.o : Language/Atom/Elaboration.hi<br />Language/Atom/Common.o : Language/Atom/Common.hs<br />Language/Atom/Common.o : Language/Atom/Language.hi<br />Language/Atom/Code.o : Language/Atom/Code.hs<br />Language/Atom/Code.o : Language/Atom/Scheduling.hi<br />Language/Atom/Code.o : Language/Atom/Expressions.hi<br />Language/Atom/Code.o : Language/Atom/Elaboration.hi<br />Language/Atom/Code.o : Language/Atom/Analysis.hi<br />Language/Atom/Compile.o : Language/Atom/Compile.hs<br />Language/Atom/Compile.o : Language/Atom/Language.hi<br />Language/Atom/Compile.o : Language/Atom/Elaboration.hi<br />Language/Atom/Compile.o : Language/Atom/Scheduling.hi<br />Language/Atom/Compile.o : Language/Atom/Code.hi<br />Language/Atom.o : Language/Atom.hs<br />Language/Atom.o : Language/Atom/Language.hi<br />Language/Atom.o : Language/Atom/Common.hi<br />Language/Atom.o : Language/Atom/Compile.hi<br />Language/Atom.o : Language/Atom/Code.hi<br /># DO NOT DELETE: End of Haskell dependencies<br /></code></pre><br />This tells us the location of where all the generated object files are. GHC will put external core files next to these other object files (in all cases, as you cannot redirect the output location of external core files.) So we can just parse this simple Makefile, remove duplicates, and substitute '.o' files for '.hcr' files. LHC takes care of the rest.<br /><br />This is of course in the event you want to compile an executable. If you want to compile a library, it's mostly the same, only when we parse the files we just store them for later.<br /><br />But what about "obscure ghc option"? No fear! We'll just provide something like a --ghc-options flag which will get passed onto GHC's invocations. LHC can then have it's own, more general command line interface to control various options in the whole-program stages (on this note, Neil Mitchell's <a href="http://hackage.haskell.org/package/cmdargs">cmdargs</a> library is amazing for this stuff!)<br /><br />For default options to GHC, I think we should perhaps stick to the Haskell 2010 standard - that is, by default, LHC will run GHC with language options to enable compilation of compliant Haskell 2010 code without any OPTIONS_GHC or LANGUAGE pragmas. Optimization levels for GHC can be implied by LHC's supplied optimization level or explicitly via --ghc-options.<br /><br />Comments are always welcome.</obscure><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-4927659293763305740?l=lhc-compiler.blogspot.com' alt='' /></div>Austin Seipphttp://www.blogger.com/profile/08003235138924772402noreply@blogger.com0tag:blogger.com,1999:blog-1862878851303132605.post-47840748985981940832010-05-24T09:54:00.003-04:002010-05-24T16:33:42.836-04:00This release of lhc-0.10 marks the move to GHC-6.12 and hopefully a more stable build infrastructure. As it stands, lhc-0.10 still lacks support for several important features, such as floating point values and large parts of the FFI.<br /><br />To install LHC you need the development versions of Cabal and cabal-install. They can be fetched from these darcs repositories:<br /><pre><br /> darcs get --lazy http://darcs.haskell.org/cabal<br /> darcs get --lazy http://darcs.haskell.org/cabal-install<br /></pre><br />Once you've installed both Cabal and cabal-install, lhc-0.10 can be installed with the following command:<br /><pre><br /> cabal install lhc-0.10<br /></pre><br /><br />Here's how to use LHC once it has been successfully installed:<br /><pre><br /> lhc -c SourceFile.hs # This compiles SourceFile.hs to SourceFile.hcr<br /> lhc compile SourceFile.hcr # This compiles SourceFile.hcr to the executable SourceFile.<br /> ./SourceFile<br /></pre><br /><br />Happy Hacking.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-4784074898598194083?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com0tag:blogger.com,1999:blog-1862878851303132605.post-90785850817645147912010-05-18T12:48:00.003-04:002010-05-18T20:39:22.798-04:00This may be obvious to some but I truly didn't grok the relationship between laziness and polymorphism before I started work on LHC.<br /><br />The Haskell language has two very distinguishing features: Laziness and parametric polymorphism. At a glance, these two features may not seem to have that much in common. However, laziness can be seen as a form of implicit polymorphism (and it tends to be implemented as such). Consider the function with the following type signature:<br /><blockquote><br />f :: Integer -> Integer<br /></blockquote><br />One could say this function is polymorphic in the first argument: The argument can either be an actual Integer or it can be something that <span style="font-style:italic;">evaluates</span> to an Integer. When we look at laziness as a form of polymorphism, it becomes clear that eliminating polymorphism will also eliminate laziness.<br />This is largely irrelevant for the average Jane Doe hacker. But if you're working on optimizations aimed at improving the time or space characteristics by eliminating "unwanted" polymorphism, it becomes important to keep laziness in mind. The hint here is for adaptive containers.<br /><br />Well, to make a short story even shorter: Laziness and polymorphism are different sides of the same coin. If you optimize away polymorphism, you will (perhaps inadvertently) also squash laziness.<br /><br />All this is obvious in retrospect but I didn't get it until it was right in front of me.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-9078585081764514791?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com2tag:blogger.com,1999:blog-1862878851303132605.post-9736088894216112302009-09-04T17:16:00.005-04:002009-09-04T17:36:29.609-04:00A lot of things has happened in LHC over the last couple of weeks. With the inclusion of Integer and IEEE float support, LHC is finally usable enough for simple benchmarks.<br /><br />I've excavated the old 'nobench' benchmark and pitched four Haskell implementation up against each other. It should be noted that these benchmark numbers are even more unreliable than usual. UHC's C backend doesn't work on x84-64 and thus it compiles to bytecode. All in all, you should trust benchmarks as much as you trust politicians.<br /><br />The benchmark results can be found here: <a href="http://darcs.haskell.org/%7Elemmih/nobench/x86_64/results.html">http://darcs.haskell.org/~lemmih/nobench/x86_64/results.html</a>.<br /><br />The results are updated frequently.<br /><br />The benchmark source can be found here: <a href="http://nobench.seize.it/">http://nobench.seize.it/</a><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-973608889421611230?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com11tag:blogger.com,1999:blog-1862878851303132605.post-73017169858131867062009-08-15T08:19:00.002-04:002009-08-15T08:36:32.674-04:00We've finally gotten around to replacing our Integer type with a real bignum implementation. The bignum code was written by Isaac Dupree in wonderfully pure Haskell, and it was a snug fit for our needs. After stripping the Prelude dependency and hooking it up to the Integer interface, it worked without a hitch.<br /><br />Let's try it out:<br /><br /><pre><br />david@desktop:lhc$ cat HelloWorld.hs<br />module Main where<br />main = do print (2^150)<br /> print (3*10^13*299792458)<br />david@desktop:lhc$ ./HelloWorld<br />1427247692705959881058285969449495136382746624<br />8993773740000000000000<br /></pre><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-7301716985813186706?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com0tag:blogger.com,1999:blog-1862878851303132605.post-17061879248623935372009-06-08T12:19:00.004-04:002009-06-08T14:04:31.107-04:00The new C backend has been pushed to the repository and it seems to work without a hitch. No particular effort has been directed at making it efficient (and none will since this backend is only a temporary measure). Initial testing shows it to be around 40-50 times faster than the interpreter.<br />Writing this backend was surprisingly easy; low-level Grin (LHC's intermediate language) can be directly pretty-printing as C code. By far the hardest part was giving up on LLVM and settling for C.<br /><br />Future development will focus on grin-to-grin optimizations and a native code generator.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-1706187924862393537?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com4tag:blogger.com,1999:blog-1862878851303132605.post-27838808375396852292009-05-21T03:25:00.003-04:002009-05-21T04:30:20.952-04:00It's been about 5 months but, finally, a new release of LHC has been born and is on hackage - so you should get it now!<br /><br />This new release has been a lot of hard work on behalf of David especially, and we've spent the past day or two working out a lot of installation issues on my MacBook etc.. But the result is looking really nice, even if premature. There are still some bugs to work out, but for the most part all our installation issues are fixed, and development can steam ahead on more interesting stuff.<br /><br />Perhaps the biggest change in this release is that LHC is now a backend for GHC instead of its own codebase. Amongst other things, this pretty much means that LHC already has support for all of GHC's language extensions. Also, it shares the exact same command line options (and a few more,) so it's pretty similar to GHC on the hood.<br /><br />The code base is very small, but it is simple: there is no garbage collection or exceptions, threading etc.. Everything is slow right now and the heap etc. are dummy. The result already works well though, and so we're releasing it now for your pleasure.<br /><br />There are full installation instructions for LHC + libraries <a href="http://lhc.seize.it/Front+Page#installing">HERE</a>.<br /><br />Enjoy.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-2783880837539685229?l=lhc-compiler.blogspot.com' alt='' /></div>Austin Seipphttp://www.blogger.com/profile/08003235138924772402noreply@blogger.com3tag:blogger.com,1999:blog-1862878851303132605.post-28826316372000467242009-05-04T12:57:00.009-04:002009-05-05T14:00:43.545-04:00Edward recently publicised some experiments with constructor specialization and the state monad. You can find the sources <a href="http://www.reddit.com/r/haskell/comments/8hbgu/an_adaptive_state_monad_40_faster_than_our_best/">here</a>.<br /><br />What he did was basically to remove laziness and polymorphism from the state monad using a fancy new GHC feature called <a href="http://www.haskell.org/haskellwiki/GHC/Type_families">indexed type families</a>. Benchmarking the different implementation was done by calculating the Fibonacci sequence and printing the 400,000th element.<br /><br />There are quite a number of such adaptive data types. They range from lists to maps to monads but they all share two fundamental drawbacks: (1) All usage combinations must be explicitly enumerated, (2) laziness must be eliminated. Fortunately for LHC, using whole-program optimization solve both problems (by static analysis and unboxing at a higher granularity).<br /><br />I believe it's important to realise that polymorphism and laziness are two sides of the same coin. Destroy one and you are likely to inadvertently destroy the other. 'Is this a bad thing?' you might ask. Well, the short answer is "yes!". Laziness, when used correctly, is incredibly powerful. Let's have another look at the State monad benchmark.<br /><br />The following program implements the above mentioned benchmark. It is 10 times faster and uses 50 times less memory than the most efficient strict version.<br /><pre><br />{-# OPTIONS_GHC -O2 -XBangPatterns #-}<br />import Control.Monad<br />import Control.Monad.State<br /><br />main = print . last . fst $ fib 400000<br /><br />fib n = unS (fibN n) (0,1::Int)<br />fibN n = replicateM' n oneFib<br />oneFib = (get >>= \(m,n) -> put (n,m+n) >> return m)<br /><br />replicateM' 0 fn = return []<br />replicateM' n fn<br /> = do !e ← fn<br /> r ← replicateM' (n−1 ∷ Int) fn<br /> return (e:r)<br /></pre><br /><br />So, in conclusion: Constructor specialization is an interesting technique but its full power can only be realised as an interprocedural optimization pass.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-2882631637200046724?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com1tag:blogger.com,1999:blog-1862878851303132605.post-23731781440335927462009-04-10T13:39:00.004-04:002009-04-11T08:55:54.186-04:00The LHC project has finally resumed development after a few weeks of inactivity. Things have taken big steps in a new direction, however, and nearly everything except the name has changed.<br />We're no longer a fork of JHC. Maintaining a complete Haskell front-end was too much of a hassle, especially considering we're only interested in optimization on the GRIN level. For this reason, LHC has reinvented itself as an alternative backend to the Glorious Glasgow Haskell Compiler.<br /><br />The lack of testability was a major problem in the previous version of LHC but hopefully we've learned from our mistakes. The new development efforts will be structured around a decremental reliance on a GRIN evaluator. In other words, we want to run the full testsuite between each and every significant code transformation. That no transformation should change the external behaviour of a GRIN program is a very simple invariant.<br /><br />The current toolchain looks as following:<br /><pre><br />david@desktop:basic$ cat Args.hs<br />import System<br /><br />main :: IO ()<br />main = do<br /> as <- getArgs<br /> mapM_ putStrLn as<br />david@desktop:basic$ ghc -fforce-recomp -O2 -fext-core -c Args.hs <br />david@desktop:basic$ lhc compile Args.hcr > Args.lhc<br />david@desktop:basic$ ./Args.lhc One Two Three<br />One<br />Two<br />Three<br /></pre><br /><br />The contents of 'Args.lhc' is unoptimized GRIN code. It is not by any means efficient or fast but it serves its purpose.<br /><br />Development will now focus on creating GRIN transformations that reduces the need for the RTS (our GRIN evaluator serves as the RTS).<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-2373178144033592746?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com8tag:blogger.com,1999:blog-1862878851303132605.post-37167311842657911102009-04-08T10:56:00.002-04:002009-04-08T11:04:01.156-04:00After weeks of development, lhc is finally able to interpret Hello World!<br /><pre><br />david@desktop:lhc$ cat HelloWorld.hs<br />module Main where<br />main = putStr "Hello world\n"<br />david@desktop:lhc$ ghc -O2 -fext-core HelloWorld.hs -c<br />david@desktop:lhc$ lhc build HelloWorld.hcr > HelloWorld.grin<br />Parsing core files...<br />Tracking core dependencies...<br />Translating to grin...<br />Removing dead code...<br />Printing grin...<br />david@desktop:lhc$ wc -l HelloWorld.grin<br />8054 HelloWorld.grin<br />david@desktop:lhc$ lhc eval HelloWorld.hcr <br />Parsing core files...<br />Tracking core dependencies...<br />Translating to grin...<br />Removing dead code...<br />Hello world<br />Node (Aliased 251 "ghc-prim:GHC.Prim.(#,#)") (ConstructorNode 0) [Empty,HeapPointer 263]<br /></pre><br /><br />Supported primitives include: indexCharOffAddr#, newPinnedByteArray#, *MutVar, *MVar.<br /><br />Exceptions are currently ignored and the heap is never garbage collected. However, since I'm evaluating the GRIN (as opposed to translating it to LLVM or C), adding these features should be easy as cake.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-3716731184265791110?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com2tag:blogger.com,1999:blog-1862878851303132605.post-67194152472361282072009-03-22T13:48:00.000-04:002009-03-22T13:48:00.224-04:00Developing a usable compiler for a high-level language such as Haskell isn't a trivial thing to do. Any effort to trade developer time against CPU time is likely to be a wise choice. In this post I will outline a few attempts to deal with the complexity of LHC in high-level ways. Hopefully the end result won't be too slow.<br /><br /><br /><span style="font-weight: bold;">Case short-circuiting.</span><br />Since case expressions in GRIN do not force the evaluation of the scrutinized value, they are usually preceded by a call to 'eval'. Then, after the 'eval' calls have been inlined, case-of-case patterns like this are very common:<br /><pre><br />do val <- case x of<br /> [] -> unit []<br /> CCons x xs -> unit (CCons x xs)<br /> Ffunc a -> func a<br />case val of<br /> [] -> jumpToNilCase<br /> CCons x xs -> jumpToConsCase x xs<br /></pre><br />This is obviously inefficient since the case for Nil and Cons will be scrutinized twice. In the GRIN paper, Boquist deals with this by implementing a case short-circuiting optimization after the GRIN code has been translated to machine code. However, dealing with optimizations on the machine code level is quite a tricky thing to do and I'd much rather implement this optimization in GRIN. By making aggressive use of small functions we can do exactly that:<br /><pre><br />do case x of<br /> [] -> jumpToNilCase<br /> CCons x xs -> jumpToConsCase x xs<br /> Ffunc a -> do val <- func a; checkCase val<br /><br />checkCase val =<br /> case val of<br /> [] -> jumpToNilCase<br /> CCons x xs -> jumpToConsCase x xs<br /></pre><br /><br /><br /><span style="font-weight: bold;">Register allocation and tail calls.</span><br />Using a fixed calling convention is not necessary for whole-program compilers like LHC. Instead, we choose to create a new calling method for each procedure (this is easier than it sounds).<br />This has the obvious consequence of requiring the convention for return values to be identical for procedures that invoke each other with tail-calls. This was deemed an unacceptable restriction in the GRIN paper, and all tail-calls were subsequently removed before register allocation took place. Afterwards, another optimization step reintroduced tail-calls where possible.<br />I believe this is too much trouble for too little gain. The possible performance hit is out-weighed by the ease of implementation and the guarantee of tail-calls.<br /><br /><br /><span style="font-weight: bold;">Simple node layout.</span><br />An unevaluated value is represented simply by a function name (or tag) and a fixed number of arguments. This value is then overwritten once it has been evaluated. However, the new value may be bigger than what was allocated to represent the unevaluated function.<br />One way to deal with this is to have two different node layouts: a fixed size node for small values, and a variable size node for big values. This is the approach taken in the GRIN paper and it understandably adds quite a bit of complexity.<br />Another method is to use indirections. This trades smaller average node size and ease of implementation against more heap allocations.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-6719415247236128207?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com1tag:blogger.com,1999:blog-1862878851303132605.post-74342310440244263742009-02-05T14:00:00.000-05:002009-02-05T15:38:38.247-05:00It has come to my attention that we are not using GRIN to it fullest. More specifically, it seems that the 'eval' and 'update' operations are handled by the RTS. This has unfortunate consequences for both the optimizer and the backend code.<br />Without an explicit control-flow graph (given by inlining eval/apply), many of our more important transformations cannot be performed. Even worse than the lost optimization opportunities is the increased complexity of the RTS. Dealing with issues of correctness is an annoying distraction from the more enjoyable endeavour of applying optimizations.<br /><br />Moving away from the magical implementation of 'update' means we have to starting thinking about our memory model. The GRIN paper suggests using a fixed node size with a tail pointer for additional space if necessary. With this scheme we can update common-case nodes without allocating more heap space. However, since we're most likely to encounter complications with respect to concurrency and certain forms of garbage collection, I think a simpler approach is more apt.<br />Replacing nodes with indirections is very easy to implement, it doesn't clash with any optimizations (the original GRIN approach interfere with fetch movement), and it opens the door for advanced features such as concurrency.<br /><br />So this is what I'll be working on in the near future. All magic has to be purged from the kingdom so logic and reason can reign supreme.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-7434231044024426374?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com8tag:blogger.com,1999:blog-1862878851303132605.post-91510535631741874542009-01-27T00:34:00.005-05:002009-01-27T15:57:51.165-05:00Version 0.6.20090126 has been released. It has been more than a month since our last release and we've made a lot of progress. The code is available from Hackage and can be installed as such:<br /><pre><br />cabal install lhc -fwith-base<br /></pre><br />Here's our changelog:<br /><ul><li>Fixed type classes.</li><li>Better variable ids.</li><li>Base library reorganization.</li><li>Better support for non-Linux systems.</li><li>Removed tagging on Int and Word.</li><li>Got Control.Arrow and Control.Applicative working by improving the handling of (->) as well as fixing type classes.</li><li>More extensive testsuite.</li><li>Lots of code clean-up.</li></ul>Future effort will be directed at adding Integer support in the base library, improving the efficiency of LHC and restoring control-flow analysis.<br /><br />Cheers,<br /> The LHC Team.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-9151053563174187454?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com0tag:blogger.com,1999:blog-1862878851303132605.post-37850748188989361212009-01-25T03:08:00.005-05:002009-01-27T12:46:50.505-05:00<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.76.3796">Code selection through object code optimization</a> by Davidson and Fraser describes a compiler architecture where instead of taking an AST and optimizing it, then generating code for a target machine, we instead take the AST and immediately generate <span style="font-style: italic;">worst-case </span>instructions which we then subsequently optimize, and then emit into assembly language. These instructions we generate and optimize are called <span style="font-style: italic;">register-transfer lists<span style="font-style: italic;"><span style="font-style: italic;"><span style="font-style: italic;"></span></span></span></span> or RTLs.<br /><br />RTLs are quite simple - a solitary RTL is just a single abstract machine instruction. A sequence of RTLs might look like so:<br /><pre><code>t[1] := reg[12]<br />t[2] := mem[8] * reg[0]<br />t[3] := t[1] + reg[3]<br />t[4] := t[2] * 10</code></pre>An RTL must specify a simple property - <span style="font-style: italic;">the machine invariant</span>, which states that any RTL maps to a single instruction on the target machine.<br /><br />The compilation process is like so, the input language (for example, C--, GRIN or any AST for that matter) is taken and fed to the <span style="font-style: italic;">code expander<span style="font-style: italic;"><span style="font-style: italic;"></span></span></span> which takes the input AST and generates a simple sequence of RTLs representing the AST - no attention at this point is paid to the generated code, and this keeps the code expander's job simple and easy. The code expander, however is a machine-dependent part of the backend - it requires knowledge of the target machine so that it may establish the machine invariant.<br /><br />After expansion, the code is subsequently optimized using e.g peephole optimization, constant subexpression elimination and dead code elimination. These optimizer parts are machine independent. Every optimization must make sure it does not violate the machine invariant.<br /><br />After optimization, we perform the task of code emission, it being the only other machine-dependent part of the compiler.<br /><br />In application to LHC, it is quite obvious a new backend is necessary. I believe this compilation method is applicable and preferable. Combined with whole program analysis, and my plans for a small and simple as possible runtime, this makes the compiler easier to retarget, and I wish for LHC to be a cross-compiler as well. It's obvious C is not the way to go, so minimizing burden on retargeting seems like a good strategy. My inevitable plans are for you to be able to take a haskell application, use LHC to compile it and get nice ASM code for whatever architecture you wish.<br /><br />The overall structure of the new backend I am thinking of is something like this (drawn very badly using <a href="http://draw.labs.autodesk.com/ADDraw/draw.html">Project Draw</a>):<br /><br /><object type="image/svg+xml" data="http://thoughtpolice.stringsandints.com/code/haskell/lhc/new-backend.svg" width="400" height="600"><br /><img src="http://thoughtpolice.stringsandints.com/code/haskell/lhc/new-backend.svg" /><br /></object><br /><br />We will perform as many optimizations as possible on the whole-program while it is in GRIN form, leaving the backend to do the task of peephole optimization/DCE/etc. in a machine-independent way, and then emit assembly code.<br /><br />On the note of the implementing an optimization engine for which to perform these operations, the approach described in <a href="http://www.cs.tufts.edu/%7Enr/pubs/zipcfg-abstract.html">An Applicative Control-flow Graph based on Huet's Zipper</a> seems promising as well. Garbage collection as well needs definite addressing before we can get LHC to compile truly serious programs; this will take a little more time to think and talk about with David. Eventually, we may even look into using <a href="http://www.eecs.harvard.edu/dias/dissertation/dissertation.pdf">Joao Dias' thesis research</a> to automatically generate compiler backends, like I believe GHC HQ wants to do.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-3785074818898936121?l=lhc-compiler.blogspot.com' alt='' /></div>Austin Seipphttp://www.blogger.com/profile/08003235138924772402noreply@blogger.com8tag:blogger.com,1999:blog-1862878851303132605.post-82905357805225203582009-01-22T10:57:00.006-05:002009-01-22T17:14:48.901-05:00Well, I finally figured out why the only two test cases that were working were HelloWorld and Kleisli. The compiler had been implicitly generating a lot of hard-wired instances for Int,Word,CInt, and all their numerous cousins -- but it was generating the methods too late (during conversion from HsSyn language to the E intermediate language) for the methods to be properly associated with their classes (which FrontEnd.Class does before typechecking even properly begins). Since none of us much liked the idea of having all this hardwired into the compiler, we decided that rather than try to adjust the machinery to work with the new handling of methods, we'd rather implement the instances in the library. So, that is what we have to do for every type in the following list:<br /><ul><li>Lhc.Prim.Int</li><li>Lhc.Basics.Integer</li><li>Data.Int.Int8</li><li>Data.Int.Int16</li><li>Data.Int.Int32</li><li>Data.Int.Int64</li><li>Data.Int.IntMax</li><li>Data.Int.IntPtr</li><li>Data.Word.Word</li><li>Data.Word.Word8</li><li>Data.Word.Word16</li><li>Data.Word.Word32</li><li>Data.Word.Word64</li><li>Data.Word.WordMax</li><li>Data.Word.WordPtr</li><li>Foreign.C.Types.CChar</li><li>Foreign.C.Types.CShort</li><li>Foreign.C.Types.CInt</li><li>Foreign.C.Types.CUInt</li><li>Foreign.C.Types.CSize</li><li>Foreign.C.Types.CWchar</li><li>Foreign.C.Types.CWint</li><li>Foreign.C.Types.CTime</li></ul><p>So bear with us if this takes a while to iron out. We have managed to get mini-base to build and many of the tests to run now, though getArgs apparantly doesn't compile yet.</p><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-8290535780522520358?l=lhc-compiler.blogspot.com' alt='' /></div>SamBhttp://www.blogger.com/profile/06560268240719951351noreply@blogger.com2tag:blogger.com,1999:blog-1862878851303132605.post-34151465306457070182009-01-19T23:00:00.003-05:002009-01-20T01:30:42.082-05:00Function calls in Haskell are typically far more numerous than in more traditional languages. This is in part due to laziness. Being lazy means that functions in Haskell do as little as possible to return a result. So to get all the data you need, you often have to call the functions multiple times.<br /><br />Consider the following snippet of code:<br /><pre><br />upto :: Int -> Int -> [Int]<br />upto from to<br /> = if from > to<br /> then []<br /> else from : upto (from+1) to<br /></pre><br />Here's what the compiled function would look like:<br /><pre><br />-- Arguments and results are (usually) kept in registers.<br />-- We generate a new calling convention for each function.<br />upto from to<br /> = case from `gtInt` to of<br /> 1 -> do -- Return a single tag representing '[]'.<br /> return [CNil]<br /> 0 -> do -- Allocate 5 heap cells.<br /> heap <- allocate 5<br /> -- CInt is the constructor for Int.<br /> heap[0] := CInt<br /> heap[1] := from<br /> -- Fupto represents a suspended call to 'upto'.<br /> heap[2] := Fupto<br /> heap[3] := from+1<br /> heap[4] := to<br /> -- Return a node as three separate pieces.<br /> -- &amp;heap[0] is the head of the list and &amp;heap[2] is the tail.<br /> return [CCons, &amp;heap[0], &amp;heap[2]]<br /></pre><br />As we can see, calling this function will only give us a single node (the node in this case is either a CNil or a CCons with two arguments). We will have to call it again to get more information out of it. For example, fully computing 'upto 1 10' requires 11 calls to 'upto' (10 CCons nodes and 1 CNil).<br /><br />Looking at the steps in 'upto' shows us that it isn't doing a whole lot. All variables (even arguments and results) are in registers and the data can easily fit in the cache. We could almost say that calling this function is as fast as looping in C. Let's add a bit more code and see what happens:<br /><pre><br />main = showMyList (upto 1 10)<br />showMyList [] = return ()<br />showMyList (x:xs)<br /> = do print x<br /> showMyList xs<br /></pre><br />The same code, now compiled to our intermediate language:<br /><pre><br />main = do heap <- allocate 3<br /> heap[0] := Fupto<br /> heap[1] := 1<br /> heap[2] := 10<br /> showMyList &amp;heap[0]<br /><br />showMyList lst<br /> = do -- Read the arguments to 'upto' from the 'lst' pointer.<br /> Fupto from to <- fetch lst<br /> -- Call 'upto'. The results are kept in registers.<br /> -- 'a' and 'b' are undefined if 't' is CNil.<br /> [t, a, b] <- upto from to<br /> -- Inspect the node tag.<br /> case t of<br /> CNil -> return [CUnit]<br /> CCons -> do -- Call print on 'a'. This call might invoke the garbage collector.<br /> print a<br /> -- Recurse on the tail.<br /> showMyList b<br /></pre><br /><br />This looks rather well. We could be proud if this was the end. However, there is one thing that we haven't considered: garbage collection. The garbage collector may run when we call 'print' and if it does then the pointer we have in 'b' will no longer be valid.<br />A common solution is to push 'b' to a stack (which the GC can walk and modify) and reload it after 'print' has returned. However, a stack allocation cost about as much as the call to 'upto' and hence incurs an overhead of nearly 50%.<br /><br />Fortunately there's a way around this. We can "simply" have the garbage collector update all registers that contain heap pointers. Doing so isn't exactly easy but it does allow us to keep pointers in registers and to avoid all unnecessary stack allocations.<br />The details of how to accomplish this will have to wait for another time.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-3415146530645707018?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com13tag:blogger.com,1999:blog-1862878851303132605.post-30789647444149365912009-01-17T18:11:00.003-05:002009-01-17T19:10:55.776-05:00It seems that the LLVM crowd have mistaken my blog posts for criticism of LLVM. Let me make it clear that I have nothing but respect for LLVM.<br /><br />I've previously mentioned that LLVM doesn't support zero-overhead garbage collection. Big deal. It's about the same as saying LLVM doesn't answer whether P=NP. I apparently failed in conveying that this is an unsolved problem in computer science.<br /><br />Solving this problem isn't as simple as putting heap pointers in registers (although it is required). The real beef lies in determining which registers are heap pointers when it isn't known statically. Determining at run-time which registers are heap pointers is intimately tied to the data model of the high-level language. Doing this well in an agnostic way is an unsolved problem. (Note that pointer tagging is generally avoided).<br /><br /><br />Several people apparently took it personally when I mentioned writing yet another NCG. Let it be clear that I'd never rewrite any of LLVM nor wish to belittle the effort it takes to write a general compiler. I was merely talking about writing a non-optimizing translator from an extremely limited IR to machine code.<br /><br /><br />So:<br /><ul><li>LLVM is great. I do not wish to criticise any part of it.</li><li>What you guys have created is impressive. I do not wish to belittle your efforts.<br /></li><li>LLVM is not a silver bullet. It does not solve all open questions in the academic world and no one expects it to.<br /></li></ul><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-3078964744414936591?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com4tag:blogger.com,1999:blog-1862878851303132605.post-71464378145285457862009-01-17T11:52:00.004-05:002009-01-17T17:38:19.020-05:00It seems that I didn't do a good job at explaining why LHC won't be using LLVM. In this post I will elaborate on why some people think C-- has more promise than LLVM as a substrate for lazy, functional languages.<br /><br />Let me start by making one thing clear: LLVM <span style="font-style: italic;">does</span> have support for garbage collectors. I am not disputing that. However, as Henderson has shown, so does C and every other language. The question we have to ask is not "Does this environment support garbage collection?" but rather "How efficiently does this environment support garbage collection?".<br /><br />To recap, Henderson's technique involves placing root pointers (the set of pointers which can be followed to find all live data) on a shadow stack. Since we manage this stack ourself, it shouldn't be a problem for the GC to walk it.<br />In short, each heap allocation incurs an unnecessary stack allocation and heap pointers are never stored in registers for long.<br /><br />Now what does this mean for languages like Haskell? Well, unlike programs written in more traditional languages, a Haskell application might very well do between 10 and 20 million heap allocations per second.<br />Writing Haskell programs is more about producing the correct data stream than it is about performing the right side-effects. It's common for functions in Haskell to manipulate data without execuing any side-effects. (Think spreadsheets.)<br />This way of computing obviously requires a very cheap method of allocation. Performing 10 million unnecessary stack allocations per second would severely hurt performance, and not having heap pointers in registers could easily be equally devastating.<br /><br />So what about LLVM? Shouldn't the built-in GC support in LLVM be more efficient than any cheap hack? Well, it turns out it isn't. The conflict between garbage collection and optimizations haven't changed, and neither have the solution: disabling or bypassing optimizations. This in turn means unnecessary stack allocations and sub-optimal use of registers.<br /><br />That LLVM haven't solved the problem of zero-overhead garbage collection isn't too surprising. Solving this while staying agnostic of the data model is an open question in computer science.<br />It is here C-- differs from LLVM. C-- is a research project that aims at solving difficult problems such as supporting efficient GCs and cheap concurrency. LLVM, on the other hand, is an engineering project.<br /><br />In conclusion: garbage collection in LLVM incurs unacceptable overhead, and while C-- and LLVM do have some overlap, the problems they're trying to solve are quite different.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-7146437814528545786?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com16tag:blogger.com,1999:blog-1862878851303132605.post-76068344399860251002009-01-15T20:07:00.005-05:002009-01-16T18:16:11.425-05:00Many people have pointed out that garbage collection can be implemented in a portable fashion in uncooperative environments such as C or LLVM. Specific details of how to do this can be found in Fergus Henderson's paper <span style="font-size:100%;">"</span><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.5570"><span style="font-size:100%;">Accurate garbage collection in an uncooperative environment</span></a><span style="font-size:100%;">"</span>.<br /><br />Henderson's technique is simply to put each pointer to newly allocated data on the stack. This bypasses all concerns about which variables will be put in registers and which will be spilled to the stack. However, the overhead of never using registers and performing unnecessary stack allocations can be quite significant.<br /><br />Since the goal of LHC is to generate efficient executables, shoehorning our executive model into a "hostile" environment like C or LLVM isn't an option. Writing a simplistic NCG won't be too much trouble, hopefully.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-7606834439986025100?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com17tag:blogger.com,1999:blog-1862878851303132605.post-70365415773322315562009-01-14T19:04:00.000-05:002009-01-14T19:18:52.557-05:00Well, I've been having some trouble with the typeclass implementation. I got rid of the long-standing bug where ill-typed rules were generated in <tt>E.FromHs</tt>, and I've gotten <tt>FrontEnd.Class</tt> to generate rules for method implementations which appear in instance declarations, but I haven't figured out how to implicitly fall back to the default implementation. The one approach I actually tried was to generate method implementations like:<br /><pre>Lhc.Order./= = Instance@.iLhc.Order./=.default</pre>which would quickly be rewritten to:<br /><pre>Instance@.iLhc.Order./=.Lhc.IO.IOError = Instance@.iLhc.Order./=.default</pre>but unfortunately, the typechecker stated that <tt>Instance@.iLhc.Order./=.default</tt> was not in the type-checking environment, and I couldn't figure out why :-(.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-7036541577332231556?l=lhc-compiler.blogspot.com' alt='' /></div>SamBhttp://www.blogger.com/profile/06560268240719951351noreply@blogger.com0tag:blogger.com,1999:blog-1862878851303132605.post-90115811514037657472009-01-14T10:24:00.000-05:002009-01-14T19:29:25.900-05:00You can follow the LHC development using these resources:<br /><br />Mailing list: <a href="http://projects.haskell.org/cgi-bin/mailman/listinfo/lhc">http://projects.haskell.org/cgi-bin/mailman/listinfo/lhc</a><br />Wiki: <a href="http://lhc.seize.it/">http://lhc.seize.it/<br /></a>Bug tracker: <a href="http://trac.haskell.org/lhc/report/1">http://trac.haskell.org/lhc/report/1</a><br />IRC channel: irc.freenode.net#lhc-compiler<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-9011581151403765747?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com0tag:blogger.com,1999:blog-1862878851303132605.post-19996901632205905452009-01-14T07:58:00.000-05:002009-01-14T19:29:47.594-05:00It might be difficult to get a sense of how feature-complete LHC is just by looking at the wiki and the mailing list. In this post I will try to answer the common questions of what LHC supports and where LHC is going.<br /><br />Let me start by introducing LHC itself. The LHC Haskell Compiler (LHC for short) was born out of <a href="http://repetae.net/computer/jhc/">JHC</a> on a cold Tuesday morning, November 18th, 2008. Her birth was necessitated by a conflict of opinion between John Meacham (the author of JHC) and myself. We simply couldn't agree on which build system would be the most appropriate: make or cabal. Since then we've made many changes that are unlikely to be merged back into JHC.<br /><br />As of this writing, LHC differs from JHC in the following ways:<br /><ul><li>Cabalized build system instead of Make.<br /></li><li>Extensive use of Haskell libraries. We have six more dependencies than JHC.</li><li>We use 'derive' instead of the unwieldy 'DrIFT' package. This, among other things, makes it possible to generate HPC information.</li><li>We support both GHC-6.8.x and GHC-6.10.x.</li><li>We're available on Hackage.</li><li>We've eliminated some usage of unsafe IO. On a project of this magnitude, getting segfaults instead of type-errors isn't acceptable.</li><li>We're very liberal in granting commit access. It's easier to undo bad patches than to make people contribute.</li></ul>Although we are not JHC, we are still similar enough to share many of the same disorders. Most importantly, we don't have support for exceptions, garbage collection or proper type-classes.<br /><br />The issues with type-classes is purely due to bugs in our code, and hopefully we can resolve them without too much headache. It should be noted that since Monad is a type-class, there are very few programs that LHC can compile at this stage.<br /><br />Exceptions and garbage collection are more fundamental problems, though. We simply cannot implement those feature efficiently in C. Using C-- is an obvious solution but unfortunately there are no usable C-- compilers. Using LLVM[1] is out of the question for the same reasons as C. We will probably end up writing our own native code generator.<br /><br />All in all, our future plans are like this:<br /><ol><li>Disable features until we can correctly compile Haskell98 programs.</li><li>Extend our testsuite to cover most of the codebase.<br /></li><li>Address performance issues. We are about 5-10 times slower than GHC and there are no fundamental reasons for this.</li><li>Write a code generator that supports exceptions and garbage collection.<br /></li></ol><br />[1]: On the surface it looks like LLVM has decent support for exceptions and garbage collecting. However, the documentation shows that it is essentially no better than in C.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-1999690163220590545?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com8tag:blogger.com,1999:blog-1862878851303132605.post-23670950993000541252009-01-12T15:32:00.000-05:002009-01-12T19:35:24.779-05:00Variable identification tags can contain four different types of information. In Haskell we would write it as such:<br /><pre><br />data Id = Empty -- Unused binding. Eg: '\ _ -> ...'.<br /> | Etherial Int -- Internal variable. Only used when type-checking.<br /> | Anonymous Int -- Anonymous variable created by the compiler.<br /> | Named Name -- Named variable created by the user.<br /></pre><br />However, in LHC this data structure was unrolled and packed into an Int. The encoding went as following:<br /><pre><br /> Empty = zero<br /> Etherial = negative numbers<br /> Anonymous = even, positive numbers<br /> Named = odd, positive numbers, used as keys in a global hash table.<br /></pre><br />This encoding gives us very fast operations on Sets and Maps but it also punishes mistakes with a vengeance. The increased performance is definitely not worth it and we've been working on untangling the Ids from day-1.<br /><br />As of today, I'm glad to say that we've finally restored the beautiful ADT and we can now hack without fear of segfaulting.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/1862878851303132605-2367095099300054125?l=lhc-compiler.blogspot.com' alt='' /></div>David Himmelstruphttp://www.blogger.com/profile/12982136700651117492noreply@blogger.com2