LLVM 6.0 で作るフロントエンドの道しるべ

本記事はC++でLLVM 6.0を用いてフロントエンドを作成する、その第一歩を踏み出すための記事です。はじめに、C++でLLVM IRを生成する方法を知るために最小構成のコードを解説し、そのあとPhiの扱いと組み込み関数の実装方法を紹介します。

筆者は今まで、いくつかおもちゃレベルのプログラミング言語を作ってきました。その中でLLVM対応したいという漠然とした思いから [きつねさんでもわかるLLVM][きつねさん] や [Kaleidoscope][万華鏡] に挑戦[^1]しました。しかし、バージョンの壁、ドキュメント量の壁、検索しても古い情報しか出てこない壁などに当たってくじけていました。

本気で取り組み始めた結果、それらの壁をなんとか突破することができ、LLVM 6.0を用いたフロントエンド実装を作ることができました。そこで得た知見を、同じ悩みを持つ人のためにまとめました。

成果物のコードだけを参照したい方は、 [ysakasin/pl0](https://github.com/ysakasin/pl0) の `llvm_frontend.hpp`, `llvm_frontend.cpp` をご覧ください。

# 対象読者
- LLVM IRの生成をしたいけど、どう手をつけたらいいかわからない
  - 特にC++からの扱い方が謎
- 自作言語のLLVMフロントエンドを作りたいが、LLVM 3.Xの情報しか出てこなくて辛い
- [きつねさんでもわかるLLVM][きつねさん] を写経したけどバージョンの違いで挫折した
- [Kaleidoscope: Implementing a Language with LLVM][万華鏡] をやってみたけどバージョンの違いで挫折した
- LLVM 6.0とか、最近のバージョンをつかいたい

これらは壁を破る前の筆者の状況を示したものでもあります。

# 目標
- C++でLLVM 6.0 のライブラリを使って、LLVM IRを生成できるようになる
- 生成したLLVM IRを実行する

# 書いてないこと
- 字句解析や構文解析などの、コンパイラ/インタプリタ作成における予備知識
- LLVM IRの説明
- C++以外のバインディングの使い方
  - おそらくセマンティクスは一緒なので、流用できると思います。
- LLVMのインストール方法

# 環境

筆者の確認環境は以下の通りです。

- macOS Sierra
- LLVM 6.0.1
- clang 6.0.1

ただし、この記事ではmacOS独自の話はしません。Unix互換OSであれば動作すると思われます。

# 最小構成から見る使い方

LLVM IRを生成する非常に小さいコード例を示します。

```c++:minimum_builder.cpp
// Copyright (c) 2018 SAKATA Sinji
// Released under the MIT license
// https://opensource.org/licenses/mit-license.php

#include <llvm/Bitcode/BitcodeWriter.h> // for llvm::WriteBitcodeToFile
#include <llvm/IR/IRBuilder.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/Support/FileSystem.h>
#include <llvm/Support/raw_ostream.h>

int main() {
  llvm::LLVMContext context;
  llvm::Module *module = new llvm::Module("top", context);
  llvm::IRBuilder<> builder(context);

  auto *funcType = llvm::FunctionType::get(builder.getInt64Ty(), false);
  auto *mainFunc = llvm::Function::Create(
      funcType, llvm::Function::ExternalLinkage, "main", module);
  auto *entrypoint = llvm::BasicBlock::Create(context, "entrypoint", mainFunc);

  builder.SetInsertPoint(entrypoint);

  builder.CreateRet(builder.getInt64(0));

  std::error_code error_info;
  llvm::raw_fd_ostream raw_stream("out.ll", error_info,
                                  llvm::sys::fs::OpenFlags::F_None);
  module->print(raw_stream, nullptr);

  // module->print(llvm::outs(), nullptr); // print LLVM IR to stdout
  // llvm::WriteBitcodeToFile(module, raw_stream); // write LLVM Bitcode to file
  return 0;
}
```

```bash:ビルド方法
g++ minimum_builder.cpp `llvm-config --cxxflags --ldflags --libs --system-libs` -o minimum_builder
```

```llvm:out.ll
; ModuleID = 'top'
source_filename = "top"

define i64 @main() {
entrypoint:
  ret i64 0
}
```

IRの生成では`llvm::IRBuilder`を中心に事が進んでいきます。 `llvm::Module`, `llvm::Function `, `llvm::BasicBlock`の基本セットをつくり、IRBuilderにターゲットとなるBasicBlockを登録します。その後、`IRBuilder#CreateRet()`など呼び出すと、メソッドに対応する命令が先ほど登録したBasicBlockに追加されます。

IRBuilderにどんなメソッドがあるのかは [IRBuilderのdoxygen](http://llvm.org/doxygen/classllvm_1_1IRBuilder.html) を参照しましょう。命令発行のメソッドは `CreateXxxxx()` という名前になっているので、念頭に置くと良いです。LLVM IRの命令セットは [LLVM Language Reference Manual][LangRef] に詳細がありますが、詳しすぎて読みづらいです。よくまとまっている [きつねさんでもわかるLLVM][きつねさん] をオススメします。

ここまでで登録したLLVM IRは `llvm::Module` の `print()` という便利関数で出力できます。これは指定のstreamに `out.ll` に示したような人間が読めるアセンブリ形式で出力してくれます。出力形式にはプログラムが扱いやすいビットコード形式もあります。ビットコード形式は `llvm::WriteBitcodeToFile()` を用いることで出力できます。

ここまでの説明で、もうLLVM IRを生成するための土台が完成しました。あとは以下のようなサイクルを続けて、この最小構成から発展させていくということになります。

1. 目的の動作をするLLVM IRがないか調べる
2. IRBuilderでどう書けばいいか調べる
3. 実装する


# Phi の扱い

LLVM IRの特徴の一つに Phi命令 があります。これについても触れておきます。

LLVM IR が SSA であるという点から、Phi命令が存在していますが、理解を阻むポイントの一つになっています。**しかし、フロントエンド作成においてはPhiを考慮する必要はありません**。なぜなら、LLVMは最適化Passが非常に発達しているからです。

目的の動作をするIRを、まずはPhiを使わずにスタックを多用して生成します。そして **mem2reg Pass** を用いて最適化するという流れがオススメです。 mem2regはIR中のスタックアクセスを可能な限りレジスタアクセスに置き換える最適化Passで、Phiを使った最適化もしてくれる優れものです。

[ユークリッドの互除法をスタックアクセスで実現したLLVM IRにmem2regを適用した例](https://gist.github.com/ysakasin/9663dcbba9f8c404a4c953ec13c58e25)を、Gistに載せたので参考程度にご覧ください。

## Passの適用

既存のPassを適用する時には `opt` コマンドを利用します。

```bash
opt -S -mem2reg source.ll -o optimized.ll
```

`-mem2reg` のようにして適用するPassを指定します。どのようなPassがあるかは [LLVM’s Analysis and Transform Passes](https://llvm.org/docs/Passes.html) か `opt -help` を参照してください。


## C++でのPass適用

外部のコマンドに任せず、コンパイル時点で最適化Passを適用して出力したいところですが、C++でのPassの扱い方がわからないので諦めました。

[きつねさん][きつねさん] に書かれている `llvm::PassManager` クラスは大きな変更があったようで、本に書かれているような使い方ができなくなっています。Doxgenで新しいクラス構造を参照できるのですが、使い方が全くわかりませんでした。

旧PassManagerクラスは `llvm::legacy::PassManager` として残っていて、一応使えるようです。しかし、mem2regの行方がわからす諦めました。

ご存知の方がおりましたら、コメントや編集リクエストをくださるとありがたいです。

# 組み込み関数

プログラミング言語として、何かを標準出力に表示する関数くらいは欲しいものです。これらは組み込み関数として実装することが近道です。 [きつねさんでもわかるLLVM][きつねさん] に記載された方法がわかりやすので、それを紹介します。

大まか流れは以下のようになります。

1. 組み込み関数をC言語で記述
2. コンパイラサイドで組み込み関数のプロトタイプを宣言しておく
3. `clang`組み込み関数をLLVM IRに変換
4. `llvm-link` でLLVM IRをリンク


### C言語での記述

まずは目的の組み込み関数をC言語で実装します。例として、整数を標準出力に表示する `write()` は `printf()` をラップする事で実現しています。

```c:builtin.c
#include <stdint.h>
#include <stdio.h>

uint64_t write(uint64_t n) { return printf("%lld\n", n); }

uint64_t writeln() { return printf("\n"); }
```

### コンパイラサイドの処理

コンパイラの対応は、他の関数を実現するのと同様に、宣言と呼び出しの処理を書くだけです。BasicBlockの生成は不要です。

[宣言の例: llvm_frontend.cpp#L19-L31](https://github.com/ysakasin/pl0/blob/5a958a2b4019be337fdd4e2380e03b90ef62cf3b/llvm_frontend.cpp#L19-L31)

```cpp:宣言
  {
    std::vector<llvm::Type *> param_types(1, builder.getInt64Ty());
    auto *funcType =
        llvm::FunctionType::get(builder.getInt64Ty(), param_types, false);
    writeFunc = llvm::Function::Create(
        funcType, llvm::Function::ExternalLinkage, "write", module);
  }

  {
    auto *funcType = llvm::FunctionType::get(builder.getInt64Ty(), false);
    writelnFunc = llvm::Function::Create(
        funcType, llvm::Function::ExternalLinkage, "writeln", module);
  }
```

[呼び出しの例: llvm_frontend.cpp#L213](https://github.com/ysakasin/pl0/blob/5a958a2b4019be337fdd4e2380e03b90ef62cf3b/llvm_frontend.cpp#L213)

```cpp:呼び出し
    builder.CreateCall(writeFunc, std::vector<llvm::Value *>(1, expression()));
```

### 組み込み関数のIR化とリンク

`clang` で組み込み関数のIRを生成し、それを自作コンパイラで生成したIRと `llvm-link` でリンクさせて終了です。


```bash
clang -emit-llvm -S -O -o builtin.ll builtin.c
llvm-link out.ll builtin.ll -S -o linked.ll
```


# LLVM IRの実行

LLVM IRはインタプリタによる実行とコンパイルしてからの実行が可能です。

### インタプリタ

```bash
lli test.ll
```

### 実行バイナリ経由

```bash
llc test.ll
clang test.s -o test
./test
```

これでLLVM IRの生成から実行まで、一通りこなせるかと思います。

# まとめ

LLVM IRを生成する最小構成のサンプルコードから初めて、組み込み関数の実装など、LLVMのフロントエンドを書くうえで最低限と思われる触りを、本記事では行いました。これらの前提知識があればLLVM 6.0の環境でLLVMと戦い始めることができるようになったかと思います。

LLVMの世界は、その広大ゆえに整備しきれていないドキュメントとの戦いになるような気がしています。LLVMの資産から得られるメリットが非常に大きいゆえに、新しく資料を記すことも非常に有益なことだと感じました。

筆者のようなLLVM入門者が増え、そして最新の資料を残していってくれることを期待します。

# おまけ

筆者のようにKaleidoscopeがコンパイルできない人向けの記事を書きました。

- [なぜあなたのKaleidoscopeはコンパイルできないのか？](https://qiita.com/sakasin/items/ee69892db0775ebdcdb3)


# 参考文献

### 公式ドキュメント

- [LLVM Language Reference Manual][LangRef]
- [Kaleidoscope: Implementing a Language with LLVM][万華鏡]
    - 対象のLLVMが古いので参考程度に
- [LLVM Doxygen](http://llvm.org/doxygen/index.html)
    - これ自体には検索機能がないので、 `llvm IRBuilder` みたいにクラス名でググりましょう

### 書籍

- [きつねさんでもわかるLLVM][きつねさん]
    - LLVMのバージョンが古くて動かないコードが多数なのが問題だが、LLVM IRとAPIの概要を抑えるのにオススメ
- [コンパイラ 作りながら学ぶ](http://shop.ohmsha.co.jp/shopdetail/000000005115/)
    - LLVMの記述はありませんが、字句解析、構文解析、意味解析、コンパイル、VMなどについての教科書
    - この教科書に書かれているPL/0'をLLVM対応しようともがいた結果、本記事が生まれました

### 記事

- [普通の大学生が【LLVM】やってみた](https://qiita.com/long_long_float/items/50ba0d9dc4075f3934a1)
    - LLVMのバージョンが古いですが、コードを公開されていて参考になりました
- [LLVMを始めよう！ 〜 LLVM IRの基礎はclangが教えてくれた・Brainf**kコンパイラを作ってみよう 〜](https://itchyny.hatenablog.com/entry/2017/02/27/100000)
- [LLVM APIを使ってみよう！ 〜 Brainf**kコンパイラをIRBuilderで書き直してみた 〜](https://itchyny.hatenablog.com/entry/2017/03/06/100000)
    - 後からよく読むと、これに大体書いてあることに気づいた
- [llvm 5.0 linking error with llvm::Module::dump()](https://stackoverflow.com/questions/46367910/llvm-5-0-linking-error-with-llvmmoduledump)
    - これで `Module#print()` の存在を知りました

### 筆者が作ったおもちゃ言語たち

- [ysakasin/pl0](https://github.com/ysakasin/pl0)
    - 初めてLLVM対応しました
- [ysakasin/holang](https://github.com/ysakasin/holang)
- [ysakasin/brainfuck.cc](https://gist.github.com/ysakasin/f80c4050a76d71eb65c5dd00a45572d6)
- [ysakasin/ludolph](https://github.com/ysakasin/ludolph)
- [ysakasin/carrot](https://github.com/ysakasin/carrot)

[きつねさん]:https://book.impress.co.jp/books/1112101137
[万華鏡]:https://llvm.org/docs/tutorial/
[LangRef]:https://llvm.org/docs/LangRef.html
[^1]: 挑戦の痕跡 https://github.com/ysakasin/DummyC