llvm-hs-pure で遊んでみる

llvm-hs-pure と llvm-hs-pretty を使って遊んでみたので、備忘録として情報を残しておきます。

はじめに

llvm-hs は LLVM API と Haskell の間を繋いでくれるライブラリです。

llvm-hs は llvm-hs と llvm-hs-pure の２つのコンポーネントからなり、前者は LLVM API の FFI バインディングを、後者は LLVM の世界を表現する Haskell の型および関数を提供します。バインディングと表現が分離されている構成上、llvm-hs を使用するには LLVM のインストールが必要な一方、llvm-hs-pure には LLVM のインストールは要求されません。

さらに別のライブラリとして llvm-hs-pretty というものがあり、これは llvm-hs-pure の LLVM IR による pretty printing を提供しています。llvm-hs-pretty は LLVM のインストールなしに LLVM IR を出力できるため、お試しで遊んでみるのにはもってこいのライブラリです。

今回は llvm-hs-pure と llvm-hs-pretty を使って簡単な言語（四則演算のできる計算機）のコンパイラを実装してみました。

なお、この記事の作成にあたり、以下の記事を参考にさせていただきました。先人に感謝。

• Haskell+LLVM構成で作る自作コンパイラ - Qiita
• こわくないLLVM入門！ - Qiita

実装したコードは GitHub にアップしてあるので、必要に応じてご活用ください。

実装前の準備

実装には stack を使用します。stack new で適当にプロジェクトを作成して以下の依存関係を設定しておきます。

package.yaml

dependencies:
- base >= 4.7 && < 5
- text
- parsec
- llvm-hs-pure == 9.0.0
- llvm-hs-pretty == 0.9.0.0

stack.yaml

extra-deps:
- llvm-hs-pure-9.0.0
- llvm-hs-pretty-0.9.0.0

本記事の執筆時点（2022/07/19 現在）では、最新の llvm-hs および llvm-hs-pretty は GHC 9.0 ではビルドできないので注意が必要です。¹ そのため、以下のように stack.yaml の resolver に GHC 8.x のいずれかを指定する必要があります。

ここでは 8.x 系列の最新 LTS である GHC 8.10.7 を指定しています。

stack.yaml

resolver: lts-18.28

Hello World

簡単なものとはいえ、いきなり言語を実装するのはハードルが高いので、まずは llvm-hs-pure および llvm-hs-pretty の使い方を確認するために Hello World プログラムを書きます。

llvm-hs の使い方については こちら の公式のサンプルを参照すると理解が捗ります。

llvm-hs-pure の使い方

llvm-hs-pretty は ppllvm という pretty print のための関数を提供してくれるのみなので、特に使い方に迷うようなことはありません。他方、llvm-hs-pure は初見だと使い方がわからず戸惑う（戸惑った）ので、ここで簡単に説明します。

そもそも llvm-hs-pure の目的は LLVM IR (Intermediate Representation) という LLVM のフロントエンドとバックエンドを繋ぐインターフェースとなる中間言語（の Haskell 世界での表現）を生成することです。

LLVM IR は以下のような形式をしています。

hello.ll

; ModuleID = 'main'

declare external ccc i32 @printf(i8*, ...)

@hello = unnamed_addr constant [15 x i8] c"Hello, world!\0a\00"

define external ccc i32 @main() {
entry:
  %0 = call ccc i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @hello, i32 0, i32 0))
  ret i32 0
}

上記のプログラムは LLVM IR で Hello World をするためのもので、LLVM をインストールすれば以下のコマンドで実行できます。

$ lli example.ll
Hello, world!

LLVM はモジュールやブロックといった単位で構成されており、llvm-hs-pure の各関数もこれらの単位に依存します。モジュールやブロックといった用語の意味については こちら の記事の説明がわかりやすいので、そちらを参照ください。

llvm-hs-pure では LLVM.IRBuilder.Monad に定義されている関数群を用いて上記のようなプログラムに対応するモジュールを構成していきます。実際に見た方が早いと思うので、以下に上記の LLVM IR を生成するための Haskell のコードを示します。

Hello.hs

{-# LANGUAGE OverloadedStrings #-}
module Hello where

import Data.Text.Lazy

import LLVM.Pretty
import LLVM.AST hiding (function)
import LLVM.AST.Type
import LLVM.IRBuilder

hello :: Text
hello = ppllvm $ buildModule "main" $ do
    printf <- externVarArgs "printf" [ptr i8] i32
    hello <- globalStringPtr "Hello, world!\n" "hello"
    function "main" [] i32 $ \[] -> do
        extry <- block `named` "entry"; do
            call printf [(ConstantOperand hello, [])]
            ret (int32 0)

ごちゃごちゃ書いているので、１行ずつ読み解いていきます。

Hello.hs

hello = ppllvm $ buildModule "main" $ do

最初に buildModule をコールしています。llvm-hs-pure ではモジュールの中身となる関数やブロックに対応する ModuleBuilder を定義して buildModule に渡すことで LLVM のモジュールを構築することができます。

Hello.hs

    printf <- externVarArgs "printf" [ptr i8] i32
    hello <- globalStringPtr "Hello, world!\n" "hello"

外観から概ね察しがつくと思いますが、みんな大好き printf 関数を extern して、Hello World するための文字列を定義しています。これらの記述は LLVM IR の以下の行に対応します。

hello.ll

declare external ccc i32 @printf(i8*, ...)

@hello = unnamed_addr constant [15 x i8] c"Hello, world!\0a\00"

externVarArgs などの ModuleBuilder を構築するための関数は LLVM.IRBuilder.Module にあるので、この辺を眺めていれば最低限の構築はできるようになります。引数として渡している i8 や i32 といった型を表す関数群は LLVM.AST.Type に定義されています。

ただし、定数文字列を定義するための globalStringPtr だけは LLVM.IRBuilder.Instruction にあるので、ご注意ください。ややこしい ... 。

Hello.hs

    function "main" [] i32 $ \[] -> do
        extry <- block `named` "entry"; do
            call printf [(ConstantOperand hello, [])]
            ret (int32 0)

最後に main 関数を定義しています。ここでは、

1. entry ブロックを作成し、
2. extern した printf 関数を呼び出し、
3. 戻り値として 0 を返す

といった内容をそれぞれの行で記述しています。これは LLVM IR の以下の記述に対応します。

hello.ll

define external ccc i32 @main() {
entry:
  %0 = call ccc i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @hello, i32 0, i32 0))
  ret i32 0
}

要約すると、やるべきことは LLVM.IRBuilder.Module の関数群を利用して ModuleBuilder を構築し、buildModule に引き渡すだけです。LLVM.IRBuilder.Module の中の関数群の扱いに慣れれば、LLVM IR でそれなりの処理が書けるようになりそうです。

ここまでで llvm-hs-pure の使い方の雰囲気はわかったと思うので、いよいよ言語を実装していきます。

パーサの実装

パーサから実装していきます。実装には parsec を使用します。

実装する言語

今回は整数の四則演算のための比較的シンプルな言語を実装します。BNF を以下に示します。

<expr>   ::= <expr1>
<expr1>  ::= <expr2> "+" <expr2>
           | <expr2> "-" <expr2>
           | <expr2>
<expr2>  ::= <expr3> "*" <expr3>
           | <expr3> "/" <expr3>
           | <expr3>
<expr3>  ::= <number>
           | "(" <expr> ")"

AST の要素の定義

今回は整数の四則演算のみなので、整数と各演算を表す型があれば十分です。

AST.hs

module AST where

data Expr
    = ENum Integer
    | EAdd Expr Expr
    | ESub Expr Expr
    | EMul Expr Expr
    | EDiv Expr Expr
    deriving (Show)

パーサの実装

冒頭でも述べましたが、実装には parsec を使用します。parsec の使い方の詳細についてはこの記事では扱いませんが、こちら のサイトが非常にわかりやすいのでオススメです。

parsec では makeTokenParser を利用することで、Lexer を実装する手間なしにパーサを構築できます。最初に makeTokenParser を使って各種パーサを生成します。

Parser.hs

import qualified Text.Parsec.Token as P
import Text.Parsec.Language (emptyDef)

p = P.makeTokenParser emptyDef
integer = P.integer p
symbol = P.symbol p
parens = P.parens p

これらのパーサを利用して言語のフロントエンドとなるパーサを構築します。基本的には BNF に従って各種パサーを定義していくだけです。手始めに整数リテラルを読み取るパーサ number を実装します。

Parser.hs

import AST
import Data.Functor.Identity
import Text.Parsec as P

type Parser a = ParsecT String () Identity a

number :: Parser Expr
number = ENum <$> integer

基本的な整数値は生成した integer が読み取ってくれるため、ここでは Expr 型の ENum にラップしてやるだけで済みます。また makeTokenParser で生成したパーサは文字列中の空白を裏でこっそり取り除いてくれるので、コード中では一切考慮する必要はありません。楽ちんですね。

同様に各種演算のパーサも定義していきます。ここでは例として加算のための add だけ記載しますが、同じ要領で sub・mul・div も実装していきます。

Parser.hs

add :: Parser Expr
add = try $ do
    e1 <- expr2
    op <- symbol "+"
    e2 <- expr2
    return $ EAdd e1 e2

冒頭で try を使用していますが、これはパース失敗時に文字を消費しないようにするためです。詳細は省きますが、これを付与しないと後述の <|> が想定通りに動作しないなどの弊害が出ます。詳しく知りたい方は 公式ドキュメント を参照ください。

これまでに定義したパーサを使って各種 expr 系のパーサを定義していきます。

Parser.hs

expr :: Parser Expr
expr = expr1

expr1 :: Parser Expr
expr1 = add
    <|> sub
    <|> expr2

expr2 :: Parser Expr
expr2 = mul
    <|> div
    <|> expr3

expr3 :: Parser Expr
expr3 = number
    <|> parens expr1

これでパーサとしてはほぼ完成なのですが、eof を付与しないと式末尾に付与されている無駄な文字列を受け入れてしまうので、そこまで判定してくれるパーサを parser として定義しておきます。

Parser.hs

parser :: Parser Expr
parser = const <$> expr <*> eof

最後に、定義したパーサを実行するための関数 parse を定義して完成です。

Parser.hs

parse :: String -> Either ParseError Expr
parse = P.parse parser ""

P.parse の最後の引数の文字列はエラー時の処理にのみ使用されるものなので、ここでは特に気を払うことなく空文字列を与えて済ませています。

遊ぶ

以下のような REPL を書けばパーサの処理結果を表示して遊べます。

Main.hs

module Main where

import Parser
import System.IO

main :: IO ()
main = repl

repl :: IO ()
repl = do
    input <- prompt "llvm-hs> "
    case input of
        "" ->
            repl
        ":q" ->
            print "Bye!"
        _ -> do
            print $ parse input
            repl

prompt :: String -> IO String
prompt text = do
    putStr text
    hFlush stdout
    getLine

コードジェネレータの実装

llvm-hs-pure および llvm-hs-pretty を使った LLVM IR のジェネレータを実装します。

LLVM モジュールへの変換

今回は単純な四則演算のみを扱うため、単に Expr の各要素を対応する LLVM IR の要素に変換してあげれば OK です。

Compiler.hs

type LLVMBuilder = IRBuilderT (ModuleBuilderT Identity)

toOperand :: Expr -> LLVMBuilder Operand
toOperand (ENum n) = return (int32 n)
toOperand (EAdd e1 e2) = binOp e1 e2 add
toOperand (ESub e1 e2) = binOp e1 e2 sub
toOperand (EMul e1 e2) = binOp e1 e2 mul
toOperand (EDiv e1 e2) = binOp e1 e2 sdiv

binOp :: Expr
      -> Expr
      -> (Operand -> Operand -> LLVMBuilder Operand)
      -> LLVMBuilder Operand
binOp e1 e2 f = do
    o1 <- toOperand e1
    o2 <- toOperand e2
    f o1 o2

続いて llvm-hs-pure と llvm-hs-pretty を使って LLVM IR を出力する関数を記述します。

Compiler.hs

compile :: Expr -> Text
compile expr = ppllvm $ buildModule "main" $ do
    printf <- externVarArgs "printf" [ptr i8] i32
    format <- globalStringPtr "%d\n" "format"
    function "main" [] i32 $ \[] -> do
        entry <- block `named` "entry"; do
            result <- toOperand expr
            call printf [(ConstantOperand format, []), (result, [])]
            ret (int32 0)

やっていることは冒頭にある Hello World とほぼ同じです。ここではソースコードで与えられた式を評価して、その結果を printf で出力するようにしています。

ソースコードの読み込みと LLVM IR の出力

最後に Main モジュールを書いていきます。

Main.hs

import System.IO
import System.Environment
import qualified Data.Text.Lazy.IO as LT

import Parser
import Compiler

main :: IO ()
main = do
  args <- getArgs
  let srcPath = head args
  src <- readFile srcPath

  let distPath = srcPath ++ ".ll"
  let result = compile <$> parse src
  case result of
    Right ir -> LT.writeFile distPath ir
    Left err -> print err

コマンドライン引数からソースコードのファイルパスを取得し、それを読み込んで LLVM IR のファイルを出力しています。ソースコードを読み込む際のエラー処理等は割愛しています。

遊ぶ

以上でコンパイラが完成したので、実際に遊んでみます。以下のようなファイルを作成して、実際にコンパイルしてみます。

example.src

5 * (12 + 3) - 1

$ stack run -- /path/to/example.src

上記のコマンドを実行すると /path/to/example.src.ll が生成されます。中身は以下のような感じです。（可読性に配慮して実際の出力から無用な改行やスペース等を削除しています）

example.src.ll

; ModuleID = 'main'

declare external ccc i32 @printf(i8*, ...)

@format = unnamed_addr constant [4 x i8] c"%d\0a\00"

define external ccc i32 @main() {
entry_0:
  %0 = add i32 12, 3
  %1 = mul i32 5, %0
  %2 = sub i32 %1, 1
  %3 = call ccc i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @format, i32 0, i32 0), i32 %2)
  ret i32 0
}

lli で実行してみます。

$ lli /path/to/example.src.ll
74

プログラムとして与えた 5 * (12 + 3) - 1 の計算結果が出力されました。めでたい！

所感

というわけで llvm-hs-pure と llvm-hs-pretty を使ってコンパイラを書きました。llvm-hs は導入に少し苦労するらしいので、今回は全くタッチせずに済ませましたが、いつかは触れてみたいです。

特に、今回の実装作業の中で llvm-hs-pretty による出力はできたものの、いざ lli で実行しようとすると LLVM IR の型チェックでコンパイルエラーになるようなことがあったので、そのあたりの挙動が llvm-hs ではどう制御されているのかが気になっています。

Haskell の世界の型チェックとは別に LLVM IR の世界の型チェックも気にかけないといけないのであれば、結構大変そうな気がするのですが、その辺がうまく制御されていると楽しく遊べそうですね。

1. こちら にある通り、GHC 9.0.1 で導入された型推論まわりの変更の影響とのこと。 ↩