Rather than dive entirely into working on a compiler, I’m going to approach the task in pieces. This post will go over how the Haskell LLVM bindings work while creating support for computing algebraic expressions. The next post will cover first-order functions, with closures to follow.

This calculator will be a standalone program that takes in algebraic equations on the command line, compiles them into LLVM bytecode, runs that code and prints the result. At the time of this writing, the LLVM bindings cannot load functions generated at runtime in ghci, so if you’re following along you’ll have to statically compile the result.

As before, this post is literate Haskell. It needs the LLVM bindings installed and set up correctly, and uses the parser from the last post. Please note that I needed to make a couple of changes to the parser module, so if you downloaded a copy before this post existed, you should grab an update.

> module Main where

> import Parser

> import Control.Monad.State
> import Control.Monad(join)

> import Data.Int

> import LLVM.Core
> import LLVM.ExecutionEngine
> import LLVM.Util.Arithmetic
> import LLVM.Util.File(writeCodeGenModule)

> import System.IO

The Haskell LLVM bindings can be split into two levels. There’s a low level interface that doesn’t give much more than direct bindings to the C++ api. This is great as a fallback, but can be rather tedious to work with.

The high level api provides translation between Haskell and LLVM values, and heavy-duty abstractions for generating LLVM bytecode. Most of this abstraction is provided by a CodeGen monad, which keeps track of basic blocks and uses the syntactic sugar of do blocks to make your code look significantly like assembly psuedocode.

Simplifying Assumptions

In order to get very far in compiling arithmetic expressions in a reasonable amount of time, we’ll need to make a few simplifying assumptions. Some are obvious, like that we won’t be dealing with functions at this point and can unhelpfully error out when someone tries to use one. Others are slightly more subtle.

In reality, after we’ve parsed the input, we should really be doing some checks on the output to ensure it is valid. This includes things like ensuring someone doesn’t try to add together a number and a lambda expression. If you look back at the parser, you’ll notice it was carefully structured to avoid this specific problem.

An issue we aren’t going to deal with is name conflicts. A real compiler would add an identifier renaming pass that ensures all name references are unique. Since this is a budget compiler, we’re going to assume the program was careful and did that for us. It isn’t exactly hard to do this, just a bit tedious, and might be worth experimenting with as an exercise.

It also makes life a lot easier if we require that names be defined before they are used. Haskell allows code like this:

let f = g + 5
    g = 10 in
    ...

In order to compile f, we need to know what g is. The obvious answer is to come up with a way to wait on compiling f until we’ve either compiled g or compiled everything there is to compile and not seen g, but that is a lot of work. This also might be something worth doing for practice though.

Another simplifying assumption that we’re making is assuming our programmers are only interested in creating functions that add or multiply 32-bit integer values. Partly this is done to avoid work, like supporting floating point values, that I feel isn’t quite interesting enough to be worth the effort for this kind of toy project. The 32-bit part is just plain cheating so we can easily convert from a Haskell Int32 to an LLVM integer on any kind of system.

Compilation Miscellany

In order to compile our programs, we need an environment that tracks the register a value was compiled into. This can be done with a simple association list of identifier names to register values, which the prelude handily defines a few functions to work with.

The type: Value Int32 corresponds to an llvm register storing a 32-bit integer. This environment would obviously need some adjusting if we wanted to support other kinds of values. The LLVM bindings approach this through limiting Value a based on appropriate type classes and the existential types extension. That would probably be the best bet to proceed from here.

> type Env = [(String, Value Int32)]

The LLVM bindings provide add and mul instructions that take two registers (or immediate values) and produce the appropriate result. We’ll need a function to translate the operations from our AST into the equivalent LLVM functions.

> getOpt Add = add
> getOpt Mul = mul

Compiling Expressions

Our entire compilation step can be expressed with a single function. Since we will want to reference variables bound in a containing let, that function will obviously need to accept the environment as an argument. The function will walk the AST, compiling results as it goes and trusting the CodeGen monad to do all of the bookkeeping.

The result of our expression compilation will be a register, bound up in the CodeGen monad. This is about the area where my understanding of Haskell gets fuzzy, so I can’t fully explain the reasoning behind the return value of this function.

> compileExp :: Env -> Exp -> CodeGenFunction r (Value Int32)

Compiling a constant is simple, just convert the AST’s string (we already know it’s an integer, thanks to the parser) to a Haskell Int32, then pass that to valueOf for conversion to an LLVM Int32, and bind the whole thing up in our monad.

> compileExp _ (Con x)       = return $ valueOf ((fromIntegral x)::Int32)

Likewise, compiling a variable is as simple as looking up the register it was previously compiled into based on the variable name. Since we’re not trying to be useful compiler writers, we’ll just give an error and exit if we can’t find the variable name.

> compileExp e (EVar v)      = case lookup v e of
>                             Just e  -> return e
>                             Nothing -> error $ "could not find variable: " ++ v

Compiling an arithmetic expression is a simple matter of compiling each side, then performing the arithmetic on the result.

> compileExp e (EOp o l r)   = do
>                              l' <- compileExp e l
>                              r' <- compileExp e r
>                              (getOpt o) l' r'

Let bindings are the only way to introduce variable names into the environment. The body of the let needs the variable to be bound to the value. For now we’re going to assume the value is not a lambda expression, in which case we can simply compute it into a register and associate that register with the variable name when compiling the body of the let.

> compileExp e (Let v val body) = do
>                  v' <- compileExp e val
>                  let e' = ((v::String),v'):e in
>                           compileExp e' body

Just to be clear, we’ll make sure that everything else (function application and lambda expressions) gives an error.

> compileExp _ _            = error "none of that, I'm still cheating"

Our “calculator” portion is formed by wrapping the expression in an LLVM function that computes it and returns the result. Here’s a simple function that does just that.

Since this is the first time we’ve actually made a function, it warrants going over what’s happening here. The createFunction function does pretty much what you would expect. It needs an argument detailing the link-time visibility of the function. For our specific purposes the parameter is irrelevant, but it’s there if you need it.

Notice that we aren’t providing a name for the function. Even according to our bindings we’re still working with anonymous functions! Of course, if you decompile the resulting bytecode you’ll see that LLVM comes up with names like @_fun1.

Our function takes no arguments, and simply compiles the expression, stores the result into a register, and returns it. Couldn’t be easier than that. The Function type represents this. If our function had taken a single integer argument its type would look like Function (Int32 -> IO Int32). Since we’re calling out to bindings that do all kinds of IO work, it’s reasonable to expect the IO monad to show up. With this type of declaration it’s impossible to call the function we’re making without being in the IO monad or committing irredeemable sins. We’ll try to keep our functional hearts pure, at least for the rest of this module.

> compileFun :: Exp -> CodeGenModule (Function (IO Int32))
> compileFun exp = createFunction ExternalLinkage $ do
>                    t <- compileExp [] exp
>                    ret t

Now we can wrap up the process of compiling our function and binding to it in Haskell. The LLVM bindings provide simpleFunction for just this task.

> compileToFun :: Exp -> IO Int32
> compileToFun exp = join $ simpleFunction $ compileFun exp

Our main function will simply loop forever, pulling in user input and running it through something to respond to it.

> main =
>     forever $ 
>     do putStr "> "
>        hFlush stdout -- have to flush for proper output ordering
>        s <- getLine
>        go s

Here’s the heart of our calculator. It attempts to parse the user’s input (generating an error message on failure), then compiles it and runs the containing function to get the result. Finally it writes the bytecode out to Calc.bc.

> go s =
>   case runwith letexpr id s of
>   Left err  -> putStrLn $ show err
>   Right exp -> do let fun = compileToFun exp in
>                             do r <- fun
>                                putStrLn $ "result: " ++ (show r)
>                                writeCodeGenModule "Calc.bc" $ compileFun exp
>                                                          

This file can be disassembled with llvm-dis, which generates somewhat surprising output. No matter how complicated your let bindings or arithmetic expression, you’ll always get a function that simply returns the pre-computed result. LLVM has an extensive number of optimization passes, and a good selection of them are enabled for you by default in the Haskell bindings. One of these is the constant propogation pass, which looks for arithmetic that can be done at compile time and eliminates the intermediary computation.

I’ll walk through an example, to show how the magic works. We’ll start with this expression:

let f = 5; g = 2 in 4 * f + (20 + 2)

It parses into:

Let "f" (Con 5)
  (Let "g" (Con 2)
    (EOp Add
      (EOp Mul (Con 4) (EVar "f"))
      (EOp Add (Con 20) (Con 2))))

A (very) naive “hand-compilation” would give us something like the following:

define internal i32 @_fun1() {
_L1:
        %1 = $5
        %2 = $2
        %3 = mul $4 %1
        %4 = add $20 %2
        %5 = add %3 %4
        ret i32 %5
}

First off, we obviously don’t need the %1 and %2 registers, all they do is hold constants. It’s simple to push their values into the relevant expressions. This act of recognizing a constant and using it to replace the register it was being stored in is constant propagation. Once that push has happened, the %1 and %2 registers become unused, and can be dropped.

define internal i32 @_fun1() {
_L1:
        %3 = mul $4 $5
        %4 = add $20 $2
        %5 = add %3 %4
        ret i32 %5
}

Now we can look at the %3 register, which just multiplies two constants. We know how to do that too, and it’s no stretch to handle the addition on %4. This optimization, called constant folding, is closely related to constant propagation.

define internal i32 @_fun1() {
_L1:
        %3 = $20
        %4 = $22
        %5 = add %3 %4
        ret i32 %5
}

But now we’ve got more registers that are nothing but labels for constants, you know what to do.

define internal i32 @_fun1() {
_L1:
        %5 = add $20 $22
        ret i32 %5
}

Now we’re another constant fold & propagate step away from the exact output LLVM gives us, which is:

define internal i32 @_fun1() {
_L1:
        ret i32 $42
}

Tune in next time for first-order functions.

No comments