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

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

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

成果物のコードだけを参照したい方は、 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を生成する非常に小さいコード例を示します。

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;
}

ビルド方法

g++ minimum_builder.cpp `llvm-config --cxxflags --ldflags --libs --system-libs` -o minimum_builder

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 を参照しましょう。命令発行のメソッドは CreateXxxxx() という名前になっているので、念頭に置くと良いです。LLVM IRの命令セットは LLVM Language Reference Manual に詳細がありますが、詳しすぎて読みづらいです。よくまとまっているきつねさんでもわかるLLVM をオススメします。

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

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

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

Phi の扱い

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

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

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

ユークリッドの互除法をスタックアクセスで実現したLLVM IRにmem2regを適用した例を、Gistに載せたので参考程度にご覧ください。

Passの適用

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

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

-mem2reg のようにして適用するPassを指定します。どのようなPassがあるかは LLVM’s Analysis and Transform Passes か opt -help を参照してください。

C++でのPass適用

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

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

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

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

組み込み関数

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

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

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

C言語での記述

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

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

宣言

  {
    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

呼び出し

    builder.CreateCall(writeFunc, std::vector<llvm::Value *>(1, expression()));

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

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

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

LLVM IRの実行

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

インタプリタ

lli test.ll

実行バイナリ経由

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

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

まとめ

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

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

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

おまけ

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

なぜあなたのKaleidoscopeはコンパイルできないのか？

参考文献

公式ドキュメント

LLVM Language Reference Manual
Kaleidoscope: Implementing a Language with LLVM
- 対象のLLVMが古いので参考程度に
LLVM Doxygen
- これ自体には検索機能がないので、 llvm IRBuilder みたいにクラス名でググりましょう

書籍

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

記事

普通の大学生が【LLVM】やってみた
- LLVMのバージョンが古いですが、コードを公開されていて参考になりました
LLVMを始めよう！〜 LLVM IRの基礎はclangが教えてくれた・Brainf**kコンパイラを作ってみよう〜
LLVM APIを使ってみよう！〜 Brainf**kコンパイラをIRBuilderで書き直してみた〜
- 後からよく読むと、これに大体書いてあることに気づいた
llvm 5.0 linking error with llvm::Module::dump()
- これで Module#print() の存在を知りました

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

挑戦の痕跡 https://github.com/ysakasin/DummyC ↩

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