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

はじめに

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

本稿の対象者

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

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

動作環境

Haskellの環境構築については　@mod_poppo さんの記事Haskellの環境構築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をそのまま git clone しただけでは、動作させることができなかったために次のような作業をしました。環境依存のところもありますが、最新環境に合わせる際の一例として順を追って紹介します。

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

git clone

$ git clone https://github.com/llvm-hs/llvm-hs-tutor.git

以下の作業はllvm-hs-tutorのディレクトリ内で操作します。

作業ディレクトリへ移動する

$ cd llvm-hs-tutor

2. stack.yaml を書き換え

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

最新環境に合わせて、resolverを変更します。

書き換え

-resolver: snapshot.yaml
+#resolver: snapshot.yaml
+resolver: lts-20.3

依存するHackageをローカルを参照するように変更します。

書き換え

-#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 に追加

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のディレクトリにシンボリックリンクを作成します。

シンボリックリンクの作成

$ 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も少し変更します。

ビルドして動かしてみる

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

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にあり、それを使いましょう。

C言語からLLVM-IRに変換する

$ clang -S -emit-llvm inputs/input_for_hello.c -o input_for_hello.ll

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

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で解釈しようということになります。続いて次のコマンドを実行してそれを試しましょう。

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 を見てみましょう。そこまで長いコードではないので全体を眺めてみます。区切りながら説明していきます。

ヘッダ部分（import等）

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

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

main関数

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

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

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

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

runHaskellPass関数

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)

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

helloWorldPass関数

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

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

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

Bitcodeの例

C言語からBitcodeに変換する

$ clang -c -emit-llvm inputs/input_for_hello.c -o input_for_hello.bc

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

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のときと同じになります。

参考記事

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

お詫びと本稿の扱い

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