kaleidoscope-hs.git
7 months agoFind our JIT'ed function and run it master
Luke Lau [Sun, 2 Jun 2019 18:33:35 +0000 (19:33 +0100)]
Find our JIT'ed function and run it

Here is where the magic happens. We first mangle the symbol before
passing it to findSymbolIn: The compilation then happens here. It will
spit back a FFI pointer, which we then need to invoke ourselves.

In order to do this we have to specify the Haskell type of the function
that we're pointing to, which resides in C-land, hence the ccall
attribute in our foreign declaration.

Try it out!

7 months agoPower up the OrcJIT
Luke Lau [Sun, 2 Jun 2019 18:25:26 +0000 (19:25 +0100)]
Power up the OrcJIT

We're going to be derivating from the Kaleidoscope tutorial, by using
the newer OrcJIT framework rather than MCJIT.
OrcJIT allows for lazy, On Request Compliation, and is built up of
different layers for linking, compiling, etc.

We start it off by creating a new execution session which will hold all
of our layers, followed by a symbol resolver which we won't need (yet).
We then create the linking and compilation layers, and then a ModuleKey:
something that llvm-hs uses to keep track of modules across each
invocation of withModule.

There's a lot of things to keep track of so I've added a small data type
to hold them all.

7 months agoDetect and remove __anon_exprs in repl
Luke Lau [Sun, 2 Jun 2019 16:39:47 +0000 (17:39 +0100)]
Detect and remove __anon_exprs in repl

You might have noticed that when entering in top-level expressions you
end up getting duplicate __anon_expr.1, __anon_expr.2s etc. Since we
don't want these anonymous functions to stick around, in this commit
we're detecting them and then removing them once we're done.

We also only want to run the JIT whenever the user has entered a
top-level expression, so we've also sketched that out.

7 months agoGenerate the module inside the repl
Luke Lau [Sun, 2 Jun 2019 16:28:31 +0000 (17:28 +0100)]
Generate the module inside the repl

The Kaleidoscope tutorial acts as a repl where each top-level expression
is evaluated when you enter it. Currently we were building up the
llvm-hs-pure AST inside our REPL, and then converting it to an actual
LLVM IR module in main when we called buildModuleT.

In order to do this line-by-line JITing, we'll need the actual LLVM
module when we enter the line. This will prepare us for the craziness
that will come in the following commits

8 months agoSet up the LLVM context and optimise the module
Luke Lau [Sun, 19 May 2019 14:58:31 +0000 (15:58 +0100)]
Set up the LLVM context and optimise the module

Now that we have some LLVM IR generated, we can run PassManager on our
module to get a bunch of neat optimisations on it. Try it out with 3 + 2
to see some constant folding.
Note that the original tutorial uses FunctionPassManager which optimises
on a function per function basis: llvm-hs doesn't expose this yet (and
this is all using the legacy pass manager anyway), so for now we just
optimise the entire module at the end.

8 months agoGenerate code for call expressions
Luke Lau [Sun, 19 May 2019 13:23:31 +0000 (14:23 +0100)]
Generate code for call expressions

In order to call a function in LLVM IR, we need to grab a
GlobalReference to it. Currently we just make it ourselves, inferring
the type of it based on what arguments the caller provided and the fact
that all functions return a double.

8 months agoHandle EOFs in the repl
Luke Lau [Sun, 19 May 2019 13:19:07 +0000 (14:19 +0100)]
Handle EOFs in the repl

This way whenever ^D is typed at the repl, the program gracefully
terminates and prints out the complete module.

8 months agoGenerate code for externs
Luke Lau [Sat, 18 May 2019 23:29:49 +0000 (00:29 +0100)]
Generate code for externs

8 months agoGenerate code for functions and variables
Luke Lau [Sat, 18 May 2019 23:23:31 +0000 (00:23 +0100)]
Generate code for functions and variables

Now that we're generating functions, variables can now be bound. This
means we will have to somehow keep track of what variables are available
in scope (i.e. passed to us in 'funciton'), so we've wrapped our
IRBuilderT in a ReaderT (Map String Operand).

For now if the variable doesn't exist in scope, we just crash the
program. But later on we will introduce a mechanism for errors, and tidy
up the transformer stack.

8 months agoGenerate code for binary operations
Luke Lau [Sat, 18 May 2019 22:43:07 +0000 (23:43 +0100)]
Generate code for binary operations

Also throw in the rest of the comparisons whilst we're at it.

8 months agoBegin codegen
Luke Lau [Sat, 18 May 2019 21:52:15 +0000 (22:52 +0100)]
Begin codegen

Now the fun begins.
You should start by installing the llvm-hs packages. This tutorial will
be keeping things "vanilla" by just installing the packages globally
rather than using a .cabal file.

$ cabal new-install --lib llvm-hs llvm-hs-pure llvm-hs-pretty --write-ghc-environment-files=always

The above command should be enough to install them, assuming you already
have LLVM installed correctly. (At the time of writing llvm-hs-pretty
needs to be installed from source for llvm-8.0:
https://github.com/llvm-hs/llvm-hs-pretty)

Like our parsing, our code generation is also monadic (this is a Haskell
tutorial). There are two monads that we can use: IRBuilder and
ModuleBuilder. The former is for LLVM IR instructions and the latter for
function definitions, constants and the like.

The original tutorial puts everything into one module, so we are going
to follow suit here. This makes things a bit hairy since now the repl
needs to take place inside of a ModuleBuilderT IO. In an effort to keep
our code as pure as possible, we've added a hoist function so that we
can keep our codegen code inside ModuleBuilder.

There's also a helper function to grab the most recent definition so
that we can print out similar to in the tutorial. This and hoist have
been tucked away into Util.hs.

So far we only generate code for numbers: But this now paves the way for
the rest of the code generation.

8 months agoAdd basic repl
Luke Lau [Sat, 18 May 2019 20:11:11 +0000 (21:11 +0100)]
Add basic repl

For the moment this doesn't have any parsing errors other than "Couldn't
parse". We'll go back to this later!
Also note we're printing to stderr.

8 months agoParse call expressions
Luke Lau [Sun, 19 May 2019 13:16:31 +0000 (14:16 +0100)]
Parse call expressions

The Call constructor stores the name of the callee and the list of
arguments being passed to it.

8 months agoParse parentheses
Luke Lau [Sat, 18 May 2019 19:32:54 +0000 (20:32 +0100)]
Parse parentheses

Yes, it's that easy. Try out the difference between
1 * 2 + 3
and
1 * (2 + 3)

8 months agoParse defs and externs
Luke Lau [Sat, 18 May 2019 16:54:06 +0000 (17:54 +0100)]
Parse defs and externs

They both share a common prototype so we can split that out into a
separate definition. We also want to be able to parse top level
expressions, so we add constructor for that in AST.
Hopefully now you can see the beauty of monadic parsing:
Function <$> readPrec <*> readPrec

8 months agoParse variables in expressions
Luke Lau [Sat, 18 May 2019 16:51:22 +0000 (17:51 +0100)]
Parse variables in expressions

8 months agoParse more binary ops
Luke Lau [Sat, 18 May 2019 16:17:41 +0000 (17:17 +0100)]
Parse more binary ops

We can parameterise the precedence that we parse so that * is parsed
before +/- etc.
Try it out with `ghci AST.hs`, and see the difference between
*AST> read "1 * 2 - 3"
and
*AST> read "1 + 2 - 3"

8 months agoStart parsing expressions
Luke Lau [Sat, 18 May 2019 15:53:40 +0000 (16:53 +0100)]
Start parsing expressions

This starts off with defining not the AST, but just what expressions we
want to be able to parse.
So far we just handle numbers, and addition involving 2 numbers.
We use the built-in ReadPrec parser combinators, which allow us to
recursively parse the binary op of addition, and even allow us to reuse
the Read instance on Int!
prec and step are needed since without them, parseAdd will just get
stuck repeatedly trying to parse the left expression (a).

8 months agoInitial commit
Luke Lau [Sat, 18 May 2019 15:28:49 +0000 (16:28 +0100)]
Initial commit