The 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. 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.
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.
The current toolchain looks as following:
david@desktop:basic$ cat Args.hs import System
main :: IO () main = do as <- getArgs mapM_ putStrLn as david@desktop:basic$ ghc -fforce-recomp -O2 -fext-core -c Args.hs david@desktop:basic$ lhc compile Args.hcr > Args.lhc david@desktop:basic$ ./Args.lhc One Two Three One Two Three
The contents of 'Args.lhc' is unoptimized GRIN code. It is not by any means efficient or fast but it serves its purpose.
Development will now focus on creating GRIN transformations that reduces the need for the RTS (our GRIN evaluator serves as the RTS).
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.
Developing 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.
Case short-circuiting. 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:
do val <- case x of [] -> unit [] CCons x xs -> unit (CCons x xs) Ffunc a -> func a case val of [] -> jumpToNilCase CCons x xs -> jumpToConsCase x xs
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:
do case x of [] -> jumpToNilCase CCons x xs -> jumpToConsCase x xs Ffunc a -> do val <- func a; checkCase val
checkCase val = case val of [] -> jumpToNilCase CCons x xs -> jumpToConsCase x xs
Register allocation and tail calls. 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). 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. 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.
Simple node layout. 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. 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. Another method is to use indirections. This trades smaller average node size and ease of implementation against more heap allocations.
It 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. 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.
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. 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.
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.
Version 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:
cabal install lhc -fwith-base
Here's our changelog:
Fixed type classes.
Better variable ids.
Base library reorganization.
Better support for non-Linux systems.
Removed tagging on Int and Word.
Got Control.Arrow and Control.Applicative working by improving the handling of (->) as well as fixing type classes.
More extensive testsuite.
Lots of code clean-up.
Future effort will be directed at adding Integer support in the base library, improving the efficiency of LHC and restoring control-flow analysis.
Code selection through object code optimization 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 worst-case instructions which we then subsequently optimize, and then emit into assembly language. These instructions we generate and optimize are called register-transfer lists or RTLs.
RTLs are quite simple - a solitary RTL is just a single abstract machine instruction. A sequence of RTLs might look like so:
An RTL must specify a simple property - the machine invariant, which states that any RTL maps to a single instruction on the target machine.
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 code expander 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.
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.
After optimization, we perform the task of code emission, it being the only other machine-dependent part of the compiler.
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.
The overall structure of the new backend I am thinking of is something like this (drawn very badly using Project Draw):
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.
On the note of the implementing an optimization engine for which to perform these operations, the approach described in An Applicative Control-flow Graph based on Huet's Zipper 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 Joao Dias' thesis research to automatically generate compiler backends, like I believe GHC HQ wants to do.
Well, 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:
Lhc.Prim.Int
Lhc.Basics.Integer
Data.Int.Int8
Data.Int.Int16
Data.Int.Int32
Data.Int.Int64
Data.Int.IntMax
Data.Int.IntPtr
Data.Word.Word
Data.Word.Word8
Data.Word.Word16
Data.Word.Word32
Data.Word.Word64
Data.Word.WordMax
Data.Word.WordPtr
Foreign.C.Types.CChar
Foreign.C.Types.CShort
Foreign.C.Types.CInt
Foreign.C.Types.CUInt
Foreign.C.Types.CSize
Foreign.C.Types.CWchar
Foreign.C.Types.CWint
Foreign.C.Types.CTime
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.
