HaskellでLLVMを試してみる


こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz :frog:　です。

## はじめに

Haskellには、LLVMのHaskellバインディングである`llvm-hs`や、FFIを使わないLLVM実装である`llvm-hs-pure`のHackageがあります。これらを利用すると、ドメイン固有言語（DSL）などの実装もしやすくなります。Toyモデルとして、LLVM公式のチュートリアルにある`kaleidoscope`の実装例もあります。
本稿では、LLVMのHaskellバインディング`llvm-hs`を使ってみることを目的に、そのサンプル実装である[`llvm-hs-tutor`](https://github.com/llvm-hs/llvm-hs-tutor)を扱います。

### 本稿の対象者

本稿の対象は次のような方を想定しております。

- プログラミング言語Haskellの知識がある方、興味がある方
- LLVMに興味がある方、LLVM や LLVM IR を何となく知っている方

### 動作環境

Haskellの環境構築については　@mod_poppo さんの記事[Haskellの環境構築2023](https://zenn.dev/mod_poppo/articles/haskell-setup-2023)を参考にして整えてください。本記事の動作を確認している環境は以下の通りです。

- macOS Ventura (Apple Silicon) 
- Xcode: 14.1
- LLVM 12.0.1
- GHC 9.2.5
- Cabal 3.8.1.0
- Stack 2.9.1
- Stackage: lts-20.3
- GHCup 0.1.18.0

## 動作環境を整える

Haskellでは、動作環境を整えるのには工夫しなければならないことが多いです。私の環境では、[`llvm-hs-tutor`](https://github.com/llvm-hs/llvm-hs-tutor)をそのまま git clone しただけでは、動作させることができなかったために次のような作業をしました。環境依存のところもありますが、最新環境に合わせる際の一例として順を追って紹介します。

#### 1. llvm-hs-tutor のリポジトリから git clone

```shell:git clone
$ git clone https://github.com/llvm-hs/llvm-hs-tutor.git
```
以下の作業は`llvm-hs-tutor`のディレクトリ内で操作します。
```shell:作業ディレクトリへ移動する
$ cd llvm-hs-tutor
```

#### 2. stack.yaml を書き換え

::: note
resolver が lts-20.3 に対応した場合は以降の操作（2.〜4.）は必要なくなるはずです。
:::

最新環境に合わせて、`resolver`を変更します。
```diff:書き換え
-resolver: snapshot.yaml
+#resolver: snapshot.yaml
+resolver: lts-20.3
```

依存するHackageをローカルを参照するように変更します。
```diff:書き換え
-#extra-deps:
-#- llvm-hs-12.0.0
-#- llvm-hs-pure-12.0.0
-#- llvm-hs-pretty-12.0.0
+extra-deps:
+- llvm-hs
+- llvm-hs-pure
+- llvm-hs-pretty
```

#### 3. llvm-hs, llvm-hs-pure と llvm-hs-pretty を submodule に追加

```shell:git submodule add
$ git submodule add https://github.com/llvm-hs/llvm-hs-pretty.git
$ git submodule add https://github.com/llvm-hs/llvm-hs.git llvm-hs-sub
```
`llvm-hs`と`llvm-hs-pure`は１つ階層が下になるため`llvm-hs-tutor`のディレクトリにシンボリックリンクを作成します。

```shell:シンボリックリンクの作成
$ ln -s llvm-hs-sub/llvm-hs llvm-hs
$ ln -s llvm-hs-sub/llvm-hs-pure llvm-hs-pure
```

#### 4. llvm-hs, llvm-hs-pure と llvm-hs-pretty を動作環境に合わせて修正

* stack.yaml の変更

llvm-hs, llvm-hs-pretty とも resolver を`resolver: lts-20.3`に変更し、llvm-hs-pretty の extra-deps をローカル参照するように変更します。

* llvm-hs-xxx.cabal の変更

bytestring は最新に合わせて`bytestring　　>= 0.11 && < 0.12`に変更します。更に、各ソースコードのimportも少し変更します。

## ビルドして動かしてみる

準備が整ったらビルドしてみましょう。

```shell:stackでビルドする
$ stack build

llvm-hs-pure > configure (lib)
:
[1 of 2] Compiling Main
[2 of 2] Compiling Paths_llvm_hs_tutor
Linking .stack-work/dist/aarch64-osx/Cabal3.6.3.0/build/helloworld/helloworld ...
llvm-hs-tutor> copy/register
Installing executable helloworld in /Users/...
Completed 3 action(s).
```

ビルドがうまくいったら、ようやく動作を試せます。`README.md`に書かれている通りの操作で確認してみましょう。
まずは、前処理としてLLVMのフロントエンドであるclangコマンドで、C言語のソースコードから仮想マシン上で動作する中間言語(LLVM-IR)を出力します。その次に、そのLLVM-IRのファイルを入力として、構造の解析を行うサンプルプログラムの動作を確認します。
お試しのためのC言語のソースコードは、`inputs/input_for_hello.c`にあり、それを使いましょう。

```shell:C言語からLLVM-IRに変換する
$ clang -S -emit-llvm inputs/input_for_hello.c -o input_for_hello.ll
```

このあと、ファイル`input_for_hello.ll`が作成されています。LLVM-IRはエディタで開いても人が読める内容です。中身を覗いてみてください。

```file: input_for_hello.ll
; ModuleID = 'inputs/input_for_hello.c'
source_filename = "inputs/input_for_hello.c"
; <略>
define dso_local i32 @main(i32 %0, i8** %1) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
;　<略>
  store i32 %21, i32* %7, align 4
  %22 = load i32, i32* %7, align 4
  ret i32 %22
}
;　<略>
```

アセンブリ言語を見慣れた方であれば、読めそうな雰囲気のファイルが出力されました。このファイルをHaskellで解釈しようということになります。続いて次のコマンドを実行してそれを試しましょう。

```shell:stackコマンドでLLVM-IRを読むプログラム（helloworld）を実行する
$ stack exec -- helloworld input_for_hello.ll

Hello from: Name "foo"
  number of arguments: 1
Hello from: Name "bar"
  number of arguments: 2
Hello from: Name "fez"
  number of arguments: 3
Hello from: Name "main"
  number of arguments: 2
```

出力を見てお分かり頂けると思いますが、このプログラムは定義されている関数名とその引数の数を出力するプログラムです。“そんな簡単なこと！？”と言えばそうですが、こういったLLVM-IRの構造解析がHaskellでできるようになるのも、Haskellバインディング`llvm-hs`が利用できるお蔭なのです。

## ソースコード HelloWorld.hs を眺めてみる

それでは実際のソースコード `app/HelloWorld.hs` を見てみましょう。そこまで長いコードではないので全体を眺めてみます。区切りながら説明していきます。


<details><summary>ヘッダ部分（import等）</summary>

```Haskell:header
{-# LANGUAGE FlexibleContexts #-}
module Main where

import Prelude hiding (readFile, writeFile)
import System.Exit (exitFailure, exitSuccess)
import System.Environment (getArgs)
import Data.List (isSuffixOf)
import Data.ByteString (readFile, writeFile, ByteString)
import Control.Monad.State hiding (void)
import Control.Monad.RWS hiding (void)

import LLVM.AST as IR
import LLVM.AST.Global as IR
import LLVM.Internal.Context as LLVM
import LLVM.Internal.Module as LLVM
import LLVM.IRBuilder.Monad as LLVM
import LLVM.IRBuilder.Module as LLVM
import LLVM.IRBuilder.Instruction as LLVM

type HaskellPassInput = [String]
type HaskellPassState = [(String, Int)]
type HaskellPassOutput = [String]
type HaskellPass a = IR.Module -> IRBuilderT (RWST HaskellPassInput HaskellPassOutput HaskellPassState ModuleBuilder) a
```
</details>

LLVMに必要なライブラリをインポートしています。特に注目したいのは、`IR`という名称でインポートされている`LLVM.AST`です。**AST**は**抽象構文木**（Abstract Syntax Tree）のことで、プログラムの構文解析で得られる情報を保持するためのものです。
このプログラムでは、型宣言`type HaskellPass a = IR.Module -> IRBuilderT (RWST HaskellPassInput HaskellPassOutput HaskellPassState ModuleBuilder) a`もポイントとなります。また、importのhidingで指定されている関数もノウハウ的には参考になりそうです。


<details><summary>main関数</summary>

```haskell:main
main :: IO ()
main = do
  args <- getArgs
  if (length args) == 1
  then do
    let file = head args
    if isSuffixOf ".bc" file
    then do
      mod <- LLVM.withContext (\ctx -> do
               LLVM.withModuleFromBitcode ctx (LLVM.File file) LLVM.moduleAST)
      (mod', _) <- runHaskellPass helloWorldPass [] mod
      bitcode <- LLVM.withContext $ (\ctx -> do
                   LLVM.withModuleFromAST ctx mod LLVM.moduleBitcode)
      writeFile file bitcode
      exitSuccess

    else if isSuffixOf ".ll" file
    then do
      fcts <- readFile file
      mod <- LLVM.withContext (\ctx -> do
               LLVM.withModuleFromLLVMAssembly ctx fcts LLVM.moduleAST)
      (mod', _) <- runHaskellPass helloWorldPass [] mod
      assembly <- LLVM.withContext $ (\ctx -> do
                    LLVM.withModuleFromAST ctx mod LLVM.moduleLLVMAssembly)
      writeFile file assembly
      exitSuccess

    else do
      putStrLn ("Invalid file extension (need either .bc or .ll): " ++ file)
      exitFailure

  else do
    putStrLn $ "usage: HelloWorld FILE.{bc,ll}"
    exitFailure
```
</details>

このプログラムはファイル名を１つ引数にとるため、main関数ではその引数をチェックしています。ファイル名の拡張子は、".ll"または".bc"かどうかをチェックされており、それ以外はエラーとなります。前述の例ではファイル名の拡張子は".ll"でしたが、clangの`-c`オプションで出力されるBitcode（ファイル名の拡張子は".bc"）も処理できます。
いずれの場合も「ファイルを読み込む⇒Passを実行する⇒ファイルに書き出す」という処理として書かれています。読み込み処理がファイル形式に応じて異なりますが、それ以外の処理は同じです。

詳細はLLVMの機構について詳しい情報に譲りますが、LLVMは次のようにFrontEndからBackEndへと処理が流れるような考え方で処理されています。このFrontEndからBackEndへ流れる処理の途中に中間コードであるIRを幾つか経由することが可能なフレームワークになっています。あるIRを別のIRに変換する機構をPassと呼んでおり、このPass機構によって容易に最適化処理を実現できるようになっております。

```plantuml
state IR_A
FrontEnd -r-> IR_A
IR_A -r-> IR_B : Pass
IR_B -r-> IR_C : Pass
IR_C -r-> BackEnd
```

本稿で見ている`llvm-hs-tutor`のサインプルコードでは最適化までは実装されていませんが、このPass機構の処理を実現するための枠組みが例示されています。その部分が次に記載した `runHaskellPass関数`です。その中から、抽象構文木（AST）を用いてプログラム内で定義されている関数名とその引数の数を調べて出力する`helloWorldPass関数`を呼び出しています。

<details><summary>runHaskellPass関数</summary>

```haskell:runHaskellPass
runHaskellPass :: (HaskellPass a) -> HaskellPassInput -> IR.Module -> IO (IR.Module, a)
runHaskellPass pass input mod = do
  let haskellPassState = []
  let irBuilderState = LLVM.emptyIRBuilder
  let modBuilderState = LLVM.emptyModuleBuilder
  let (((result, _), output), defs) = LLVM.runModuleBuilder modBuilderState $ do
                              (\x -> evalRWST x input haskellPassState) $
                                runIRBuilderT irBuilderState $ pass mod
  mapM_ putStrLn output
  return (mod { IR.moduleDefinitions = defs }, result)
```
</details>

runHaskellPass関数は、(HaskellPass a), HaskellPassInput, IR.Module を引数にとって、IO (IR.Module, a) を返します。この実装では、HaskellPassInputには空リスト [] が指定されていますので、実質はPassの処理関数と抽象構文木を受け取って抽象構文木を返していると読んでもよさそうです。`LLVM.runModuleBuilder　〜 runIRBuilderT irBuilderState $ pass mod`あたりの記述が、指定されたhelloWorldPass関数を適用している箇所になります。

<details><summary>helloWorldPass関数</summary>

```haskell:helloWorldPass
helloWorldPass :: HaskellPass ()
helloWorldPass mod = do
  let defs = IR.moduleDefinitions mod
  mapM_ visit defs
  return ()
  where
    visit d@(IR.GlobalDefinition f@(Function {})) = do
      tell ["Hello from: " ++ (show $ IR.name f)]
      tell ["  number of arguments: " ++ (show $ length $ fst $ IR.parameters f)]
      LLVM.emitDefn d
    visit d = LLVM.emitDefn d
```
</details>

helloWorldPass関数は、抽象構文木（AST）を解釈して、その構文が IR.GlobalDefinition の Function あれば、その名前とパラメータの数を表示すしています。

ここまで実際のソースコード `app/HelloWorld.hs` を見てきました。本稿で、HaskellのLLVMバインディングを使ってPass機構を軽く体感して頂けたら幸いです。 折角ですので、説明の途中にありましたBitcodeの場合の動作を以下に挙げて、本稿を締めたいと思います。

* Bitcodeの例

```shell:C言語からBitcodeに変換する
$ clang -c -emit-llvm inputs/input_for_hello.c -o input_for_hello.bc
```

ファイル`input_for_hello.bc`が出力されいます。このファイルはバイナリ形式ですので、人が読めるものではありません。中身を確認したいときには、バイナリエディタかバイナリダンプコマンド（hexdumpなど）で確認してください。

```shell:stackコマンドでBitcodeを読むプログラム（helloworld）を実行する
$ stack exec -- helloworld input_for_hello.bc

Hello from: Name "foo"
  number of arguments: 1
Hello from: Name "bar"
  number of arguments: 2
Hello from: Name "fez"
  number of arguments: 3
Hello from: Name "main"
  number of arguments: 2
```
出力結果は、当然ながらLLVM-IRのときと同じになります。


## 参考記事

本稿を記載するにあたって参考としたエントリーをいくつか紹介します。

https://qiita.com/mitsuchi/items/91b2b41cc63bb3ec87ff

https://qiita.com/toru0408/items/6bedee118ba08ea2c0b2

https://qiita.com/dmystk/items/049b783236abc785d04a

https://qiita.com/dmystk/items/4943f4160fa067ba5dea

## お詫びと本稿の扱い

[2020年のアドベントカレンダー](https://qiita.com/advent-calendar/2020/haskell)に本稿に近い内容のエントリーを書こうとしたものの、私　@kyamaz :frog:　の働く環境の変化もあり、その時期に投稿ができず、結果的に穴をあけてしまいました。その後ずっと記事を書く機会（きっかけ）をつくれていませんでしたが、この度、勤め先の部門イベントに参加する機会があり、本エントリーを書くことができました。本業以外の時間を与えてくれた部門イベントの企画の方々には感謝致します。
そして本稿は、2020年年末のアドベントカレンダーの穴埋め記事とさせて頂きます。:bow: