Zenn
⚓

Rustで自作プログラミング言語を自作x86_64アセンブラでセルフホスティングした記録

2022/12/23に公開
Rust
compiler
tech

この記事は言語実装 Advent Calendar 2022の23日目の記事です。

導入

2021年、私は llrl という自作プログラミング言語のセルフホスティングに取り組みました。

https://zenn.dev/yubrot/articles/eaaeeab742b4a1

セルフホスティングには成功し、生成された処理系の実行ファイルのバイナリが完全一致するところまで辿り着きましたが、この言語処理系のバックエンドは「LLVMを使う」で終わっていたので、バックエンドの実装にもっと目を向けたいと思いました。そこで2022年は、この言語処理系に 新たにx86_64を直接ターゲットとするバックエンドを追加し、LLVMを用いずにセルフホスティングできるようにしました。 本記事はこの取り組みの振り返りとなります。

自作プログラミング言語の特徴とバックエンドの要件

llrlには大きな特徴が2つあります。

  • Hindley-Milnerベースの型推論による静的型付け (+型クラス)
  • Lisp-likeなS式によるシンタックスとマクロ

1つ目はバックエンドの追加にはあまり影響はありません。LLVMバックエンド、新たなバックエンドはともに、意味解析が済んで型クラスのインスタンス等は解決済みの中間表現を入力に取ります。

2つ目はバックエンド実装に大きく影響します。LLVMによるバックエンドでは、LLVMでコンパイルしたマクロを、LLVMのJIT実行エンジンでそのままコンパイル中に実行していました。新しいバックエンド実装でもこの形式を踏襲したかったため、バックエンドはただコード生成できるだけではなく、マクロのコンパイル結果をメモリにロードしてJIT実行できる必要がありました。

アセンブラ + JITエンジンを自作する

ということで、 (元々アセンブリに疎かったのもあり) アセンブリの学習も兼ねて、まずアセンブラと関連するバイナリユーティリティを含んだライブラリ xten を実装しました。全てが純粋なRustによる実装で、プロセス内で動作します。
アセンブラのAPIデザインについては以下の記事をご参照ください。

https://zenn.dev/yubrot/articles/6d9b0eb95f412b

xtenは大きく分けて asm, elf, jit の3モジュールからなり、以下のように利用できます。

  • asm モジュールのアセンブラでコード生成を行い、 asm::Object を生成する
  • elf::write_relocatable_object で asm::Object をELFファイルとして出力する
  • jit::Engine に add_object して asm::Object をJIT実行するためにメモリにロードする

elf モジュールは最後の実行ファイルの生成のためのELFオブジェクトファイルの生成に、 jit モジュールはマクロのJIT実行に使用します。
このようなライブラリを実装する上で、上の記事で紹介しているような基本的なアセンブラ機能… x86_64のマシンコードへのエンコードももちろん重要ですが、もう一つ重要な課題として 「リロケーション情報を理解すること」 がありました。

リロケーション情報の表現

一般的なアセンブラのアセンブリコードでは、外部のシンボルや特定のジャンプ先が ラベル で表現され、それを埋め込むことができます。例えば以下のようなCのコードは、以下のようなアセンブリコードに対応します。

void hoge(int a);
void fuga(int b);

int hello(int foo, int bar) {
  if (foo == bar) {
    hoge(foo);
    return 123;
  } else {
    fuga(bar);
    return 456;
  }
}

  ...
hello:
  sub  rsp, 8
  cmp  edi, esi
  je  .l1
  mov  edi, esi
  call  fuga@PLT
  mov  eax, 456
  jmp .l2
.l1:
  call  hoge@PLT
  mov  eax, 123
.l2:
  add  rsp, 8
  ret

ここで、関数 hoge, fuga や、if分岐に対応するラベル .l1, .l2 がアセンブリコード中に表れます。x86_64のマシンコードのレベルで 文字列でジャンプ先などを指定できるような高抽象な機能があるわけではなく、 これらラベルはアセンブラが何らかの処理によって解決しているものになります。
具体的には、マシンコードのレベルでは、ラベルに相当する値は単にプログラムカウンタ (インストラクションポインタ, RIP) からの 相対アドレス値 やメモリ上の特定の位置を指す 絶対アドレス値 となっています。これらの値は、プログラムがメモリ上にロードされ、実行されるまでのいずれかのフェーズで計算され、埋め込まれます。
例えば、ある命令 je .l1 の10バイト先にラベルの定義 .l1: があるなら、相対アドレスとして 10 が埋め込まれる、といったイメージです。

このようなラベルという抽象に対応して、xtenでは asm::Object に シンボル と リロケーション の情報が集約されています。

  • シンボル Symbol
    • ある定義がオブジェクト上のどこにあるかの情報。名前と位置情報の組
  • リロケーション Reloc
    • ある定義の使用の情報。どこで何を使用していて、それをどう埋め込むかの情報の組

シンボルは w.define(some_label, is_global) に対応して記録されます。

リロケーションは、例えば w.jmpq(some_label) のような抽象化された命令に対応する WriteInst の実装が以下のようになっていて、ここで記録されます。 (WriteInst トレイトの詳細はxtenアセンブラの解説記事をご参照ください)

impl<W> WriteInst<W> for Jmpq<Label>
where
    W: Write + SectionWrite,
{
    fn write_inst(&self, w: &mut W) -> io::Result<()> {
        // 32bit 相対アドレス指定のjmp命令を、仮にアドレス値を 0 として書き込んでおき、
        w.jmpq(0i32)?;
        // このjmp命令のアドレスの部分に対応するリロケーション情報を記録する
        // (PcRel32はProgram counter relative 32bitの略)
        w.use_relative(-4, self.0, -4, RelocType::PcRel32);
        Ok(())
    }
}

これらシンボル、リロケーションの情報を踏まえると、xtenの elf, jit モジュールの働きを以下のように説明できます。

llrlではマクロのJIT実行、実行ファイル生成がともに必要なので、xtenの jit, elf モジュールはともに asm::Object を入力にとって動作するように実装されています。

chibiバックエンドの実装

マクロのJIT実行を含め、新たなバックエンドの実装に必要と思われる道具が揃ったので、バックエンド本体を実装していきます。

LLVMによるバックエンドの実装時点で、コンパイラの動作テストのためのテストケース群の準備や、高級な言語機能を低級な表現に変換(lowerize)する実装、JITコンパイルとマクロの実行のスケジュール実装などを既に終えていたため、新たなバックエンド実装で行うことは「ある程度低級な中間表現を入力にとってマシンコードを生成する」のみです。

バックエンドの実装は、実装が平易なrui314/chibicc (およびその源流とも言えるAn Incremental Approach to Compiler Construction) を参考に進めることにしました。バックエンド名もここからとって chibi としています。

コード生成

chibiccのコード生成器の特徴的な点として、スタックマシンをターゲットとしているかのようなマシンコードを生成する点が挙げられます。 a + b のコード生成を疑似コードで表現すると以下のようなイメージになります。

void codegen_binary_add(expr *a, expr *b) {
  // まず左辺aを実行 (するコードを生成):
  // (結果が整数値の場合、それをRAXレジスタに格納するものとする)
  codegen(a);

  // ここで、左辺の評価結果をスタックにpushしてしまう
  emit_push(RAX);

  // 右辺bを実行:
  // ここで、右辺の実行時点で左辺はスタックにpushされているので、
  // codegenはレジスタを自由に使って結果を計算することができる
  codegen(b);

  // RCX <- 右辺, RAX <- 左辺
  emit_mov(RCX, RAX);
  emit_pop(RAX);

  // RAX, RCXの加算結果をRAXに
  emit_add(RAX, RCX);
}

これはレジスタをよりうまく利用する最適化されたマシンコードに比べると非効率ですが、レジスタ割り当てなどの実装を必要としないため、実装が容易になります。chibiccのソースコードを読み込んだ記録がZennのスクラップにあるので、気になった方はこちらも参照してください。

https://zenn.dev/yubrot/scraps/e3963a612c29de

llrlのchibiバックエンドもこの方法を踏襲したため、全体としてcodegen.rsの実装は、長くはあるものの、平易なものとなっています。パフォーマンスを犠牲に実装を平易にするこのような割り切りは他にもあります:

  • すべてのローカル変数の束縛はスタックに領域を割り当てる
  • llrlの関数の呼び出し規約ではすべての引数を単にスタックに積む

Cの関数呼び出し

厳密に仕様に準拠した実装が要求される場所もあります。最たるものはCの関数呼び出しで、Cの関数呼び出しのABIに準拠する必要があります。ABIによって以下のような事柄が定められています。

  • 引数や返り値がどのように分類 (Classification) されるか
  • それぞれの分類のデータについて、どのようにレジスタ・スタックを用いて関数に渡すか、関数から返されるか
  • 関数呼び出しの前後でどのレジスタの値が保存されていなければならないか、また保存されている保証がないか

一方で、これらはあくまでCの関数を call するときに満たされていれば良いので、やはりllrlでは実装の簡易さを優先して、 まず引数を全て評価してスタックにpushしてから、レジスタ渡しされる引数をレジスタにpopしてセットしていく 形で実装しています:

// At impl<'a> FunctionCodegen<'a>
fn eval_c_call<F>(
    &mut self,
    c_fun: impl FnOnce(&mut Self) -> io::Result<Option<F>>,
    ret: &Ct,
    args: &[Rt],
) -> io::Result<Option<Layout>>
where
    inst::Callq<F>: WriteInst<Writer>,
{
    // 引数、返り値のレイアウト情報を計算 (ABIのClassificationに対応する情報も計算される)
    let mut arg_layouts = Vec::<Layout>::new();
    for arg in args { ...  }
    let ret_layout = self.ctx.layout(ret);

    // レイアウト情報をもとに、各引数がどう(どのレジスタ or スタック)渡されるかを計算
    let call_args = CallArg::c_args(arg_layouts, &ret_layout);

    // 引数を、スタック渡しされる引数群とレジスタ渡しされる引数群に大別する
    let (stack_args, reg_args) = args.iter().zip(call_args.iter()).partition::<Vec<_>, _>(...);

    // 関数呼び出し用のスタック上のレイアウト (CallFrame) を計算
    let call_frame = CallFrame::new(call_args, CallRet::c(&ret_layout), &self.stack_frame);

    // 16バイトアライメント、および返り値のためのpaddingが必要な場合がある
    self.extend_stack(&call_frame.padding_before_stack_args())?;

    // スタック渡しの引数、レジスタ渡しの引数の順番に、それぞれ逆順で評価し、 **一度スタックにpushする**
    for (arg, _) in stack_args.iter().rev().chain(reg_args.iter().rev()) {
        let layout = continues!(self.eval(arg)?);
        self.push(&layout)?;
    }

    // 関数本体を評価によって取得
    let c_fun = continues!(c_fun(self)?);

    // 先ほどスタックに一時的にpushしていたレジスタ渡しの引数を、それぞれのレジスタにpopして設定していく
    for (_, c) in reg_args {
        match c {
            CallArg::Reg(a, None) => self.pop_eightbyte(a.reg)?,
            CallArg::Reg(a, Some(b)) => {
                self.pop_eightbyte(a.reg)?;
                self.pop_eightbyte(b.reg)?;
            }
            _ => panic!(),
        }
    }

    // 必要であれば返り値用のポインタをRDIに設定
    if let Some(offset) = call_frame.offset_to_ret_destination() {
        self.w.leaq(Rdi, memory(Rsp + offset as i32))?;
    }

    self.w.callq(c_fun)?;

    // 呼出し後、使用済みのスタック渡しされた引数群などを破棄する
    self.shrink_stack(&call_frame.remnants_after_call())?;

    Ok(Some(ret_layout))
}

今回ターゲットとしているx86_64 LinuxのSystem V AMD64 ABIについては、上でも紹介したchibicc ソースコードリーディング記録の中でおおまかにまとめてあるため、あわせて参照してください。

自作言語上にこれらを移植する

今回新たに実装したxten, chibiバックエンドを、Rustによる実装 (xten0, llrl0) に対応するようにllrlによる実装へ移植していきます (xten1, llrl1)。llrlは元からRustからの移植を考慮した言語機能を備えているので、基本的にひたすらやるだけです。

やるだけではある一方で、今回の対応で扱うコードベースがより大きくなった結果、分割コンパイルを一切サポートしていないllrlではコンパイラ全体のコンパイルに結構な時間がかかるようになってしまいました。特にxten1/asm/inst.llrlは、x86_64の命令セットを20000行越えのコードの中で並べていて巨大なため、意味解析にかなりの時間がかかります。

テストする

chibiバックエンドの実装においても、目標はセルフホスティングでした。セルフホスティングのゴールは生成されたバイナリの完全一致です。

今回新たにchibiバックエンドを加えたことで、既存のLLVMバックエンドを含めてより様々なビルドバージョンが考えられるようになりました。ビルドバージョンを呼び分けるため、世代ごとに使用したバックエンドの識別子 (LLVMなら l, chibiなら c) を llrl1 の後に付け加えていく形で特定のビルドバージョンを表現することにしました。具体例を挙げると:

  • llrl1l - llrl0 のLLVMバックエンド l でコンパイルされたllrl1コンパイラ
  • llrl1c - llrl0 のchibiバックエンド c でコンパイルされたllrl1コンパイラ
  • llrl1lc - llrl1l のchibiバックエンド c でコンパイルされたllrl1コンパイラ
  • llrl1cc - llrl1c のchibiバックエンド c でコンパイルされたllrl1コンパイラ

この上で、llrl1/Makefileにはセルフホスティングのテストを行うルールを用意しています。
同じ種類のバックエンドを使用した2世代目 (ex. llrl1cc) と3世代目 (ex. llrl1ccc) のバイナリの一致が確認できます。現在のllrlでは、以下の4パターン全てでバイナリが完全一致します。

llrl1/Makefile
.PHONY: self-hosting1lll self-hosting1lcc self-hosting1cll self-hosting1ccc
self-hosting1lll: llrl1ll llrl1lll
	diff llrl1ll llrl1lll
self-hosting1lcc: llrl1lc llrl1lcc
	diff llrl1lc llrl1lcc
self-hosting1cll: llrl1cl llrl1cll
	diff llrl1cl llrl1cll
self-hosting1ccc: llrl1cc llrl1ccc
	diff llrl1cc llrl1ccc

感想・次に取り組みたいこと

マシンコードとのギャップはまだまだ大きい

今回、スタックマシン風のマシンコードを生成することでLLVMの依存を取り払い、x86_64ネイティブのバックエンドを実装してセルフホスティングすることに成功しましたが、CPUの性能を有効に発揮できるマシンコードとはまだまだギャップが大きいと感じます。chibiバックエンドが入力に受け取る中間表現は、もともとLLVMバックエンドがLLVM-IRを生成できる程度までの低級化を行うためにデザインしたものなので、最適化を考えるならまた新たに適切な中間表現を学んで考えていくのが良さそうです。

Rustが楽しい・快適

やっぱりRustは書いていて楽しい・快適な言語だと感じます。例えばxtenのアセンブラ実装では、このようなAPIをイメージそのままに実現でき、かつrust-analyzerによってIDE上で快適に利用できました (命令セットが大量なので、補完にもたつく等あるのではないかと思っていました)。
chibiバックエンドの実装にために事前に行ったllrl本体の改修でも、Rustによるコードが型システムや所有権によって堅牢であることと、この規模のコードベースではrust-analyzerの即応性が非常に高いことから快適にリファクタリングが行えました。

開発者体験とLanguage Servder Protocol

llrlは元々実用的なプログラミング言語を目指して開発しているわけではありませんが、それにしても言語機能の有無ではないところで開発者体験が著しく悪いところがあります。コンパイル速度とエディタ(IDE)上の開発サポートの無さです。上述のように、Rustの開発の快適性にはrust-analyzerも大きく寄与しています。

なのでllrlでもLanguage Server Protocolを自前でサポートしてみたいところですが、現在のllrlの実装は分割コンパイルや並行処理をまったく想定していないところなど、LSPを実現するにはアーキテクチャ的な限界があるものと考えられます。Rustのような意味解析が複雑でマクロもある言語のLSPをどう実現しているのか、まずはrust-analyzerの実装に飛び込んで深掘りしてみるのが良いかなと考えています。

次なるバックエンド?: WebAssembly

llrlとの相性が悪くないなら実装を試みたいものの一つにWebAssemblyバックエンドがあります。
WebAssemblyはもともと触れたい技術でしたが、このバックエンド実装を終えるまではお預けとしていました。最近はWASIというワードを目にする機会も多くなり、WASIを活用する方向で試すのは楽しそうです。もちろんWebAssemblyという名前に含まれるWeb上でセルフホスティングして動作することを目指すのも面白そうです。とはいえ、まだWebAssemblyに親しみがないので、まずは親しみを得ていきたいところです。

Discussion