OpeLa: セルフホストなOSと言語処理系を作るプロジェクト

OpeLa セルフホストなOSと言語処 理系を作るプロジェクト Kernel/VM探検隊online part3 2021年7月10日 @uchan_nos

自己紹介 内田公太 @uchan_nos サイボウズ・ラボ株式会社  OSと言語処理系の研究開発 趣味：自作OSコミュニティ「osdev-jp」の運営 著書：  ゼロからのOS自作入門  自作エミュレータで学ぶx86アーキテクチャ

本日の発表のコンセプト 誰 言語処理系やOSの自作やセルフホスト に興味がある人に 何 OpeLaプロジェクトの存在と中身を知り 自分も設計や開発に参加してみたい と言ってもらいたい！

目次 MikanOSとOpeLa OpeLa言語 OpeLaコンパイラの内部 構文に関する考察

OpeLaとは……の前に、MikanOSとは 「ゼロからのOS自作入門」で作る サンプルOS  30章で作れる！ 現代的な構成  UEFIによる起動  64ビットモード  プリエンプティブマルチタスク  ページングによるメモリ管理  FAT32ファイルシステム  パイプ、リダイレクト MikanOSの30章後の姿 日本語の教科書が完備された、現 代的なPCで動作する教育用OS

MikanOSはまだまだ進化中 「ゼロからのOS自作入門」の最後のバージョンを元に、GitHub上 で開発継続中  タスクバーの時計  マンデルブロ集合の描画アプリ  USB CDCデバイスの（一部）サポート  各種バグ修正 プルリクエスト大歓迎  有用なプルリクなら受け取ります  見ていて面白いアプリ、便利なアプリ  アプリが必要とするシステムコール  ドキュメント、OSのロゴ これまでに（uchan除く）7人からプルリクを受け付けた

改めて、OpeLaとは Operating & Language processing system OSと言語処理系のセルフホストを目指すプロジェクト  言語処理系：コンパイラ、アセンブラ、リンカ、ライブラリ等  セルフホスト：自分自身をビルドすること  GCC on LinuxでGCCとLinuxをビルドすることと同類 OSの ソース コード 言語処 理系の ソース コード Linuxの ソース コード GCCの ソース コード 自作言語処理系 GCC 自作OS Linux

OpeLaプロジェクトの目的 1. コンピュータが動く仕組みを深く学びたい人の教材となる 2. uchanの技術的興味を満たす OS：MikanOSを採用予定  教科書が完備されていて学習しやすい + OpeLa 言語処理系：新しく作る  現在はOpeLaコンパイラを実装中 セルフホストを目指すことで、自ずと必要な機能が定まってくる  OS：言語処理系が動く程度の機能  言語処理系：言語処理系やOSを記述できる程度の機能

OpeLaプロジェクトで作る物と順序 作った物をできるだけ活用する、という方針で順序を決定 1. セルフホストなOpeLaコンパイラ（C++で実装） 2. アセンブラ、リンカ（OpeLaで実装）  この時点で言語処理系が全部自作に切り替わる 3. ビルドツール（makeみたいなやつ） 4. MikanOSをOpeLa言語に移植 5. 言語処理系にMikanOS向けアプリ生成オプション追加 6. 言語処理系をMikanOSに移植

目次 MikanOSとOpeLa OpeLa言語 OpeLaコンパイラの内部 構文に関する考察

OpeLa言語 func main() int { printf("hello, world\n"); } extern "C" printf func(*byte, ...) int; OSを書くための言語（ついでにアプリも書ける） 言語機能はCに近く、構文はGoに近い セフルホストを目指し、C++ on Ubuntuで実装中 設計と実装は道半ば

OpeLaコンパイラの現状 OpeLaコンパイラの機能を一覧するなら、テストケース  https://github.com/uchan-nos/opela/blob/master/compiler/v2/test.opl  テストケース自体をOpeLa言語で実装してある 2021/07/05現在の主要な機能  四則演算、制御構文（if, for）、変数定義  任意ビット幅整数、ポインタ、配列、構造体、型変換  ジェネリック関数 同梱してるサンプルアプリ  rpn: 逆ポーランド記法計算機  list: 線形リストの実装サンプル  sdl: SDL2を使った画面表示デモ

• https://github.com/uchan-nos/opela/blob/master/compiler/v2/test.opl

SDL2を使ったデモアプリ カーソルキーでロゴ 移動 スペースキーで背景 色変更 外部関数呼び出し機 能でSDLの関数を呼 び出す Cのヘッダファイル を読めないので、構 造体は自前で定義

OpeLa言語の特徴 OSを書くために設計されている 「uint3」などの任意ビット幅の整数型 「アドレス型」という、整数とポインタのあいのこの型 構造体に関連する特殊な機能 マルチタスク未サポートで使えるコルーチン CPU固有命令をネイティブにサポート

アドレス型 func notifyEndOfInterrupt() { // 組み込みのアトミック読み書き関数を使ってレジスタアクセス var eoi *uint32 = 0xfee000b0 @ address; AtomicStore(eoi, 0); // same as: AtomicStore(0xfee000b0@address@*uint32, 0) } 「@」は型変換演算子で、「値 @ 型」と使う address型の値は、任意のポインタに代入可能  Cのvoid*のような役目 アドレス値を直書きしている箇所をgrepしやすい！

構造体に関連する特殊な機能 type idtEntry packed_struct { Offset(15:0) address16; SegmentSelector uint16; IST uint3; _ uint5; Type uint4; _ uint1; DPL uint2; P uint1; Offset(31:16) address16; Offset(63:32) address32; _ uint32; }; Offsetフィールドは分割されている  後方互換性のための工夫

構造体に関連する特殊な機能 type idtEntry packed_struct { Offset(15:0) address16; SegmentSelector uint16; IST uint3; _ uint5; Type uint4; _ uint1; DPL uint2; P uint1; Offset(31:16) address16; Offset(63:32) address32; _ uint32; }; idt[21] = { .Offset = &intHandler21, .SegmentSelector = 1 * 8 .Type = 14, .DPL = 0, .P = 1 }; Offset(msb:lsb)でビット範囲を指定 共通の接頭辞がグループ化される  Offsetは1つのフィールドを構成する グループ化されたフィールドは、連続 であるかのように読み書きできる

OpeLa言語の設計方針 OSを書くために便利な機能を入れる セルフホストを達成するために必要な機能を入れる OSを書くのに不要な機能は入れない  例外やGCなど 機能の選択はバランスを考える 機能の 便利さ 機能追加 コスト

目次 MikanOSとOpeLa OpeLa言語 OpeLaコンパイラの内部 構文に関する考察

Ver.1とVer.2 OpeLaコンパイラは大きく2つのバージョンがある  Ver.1: 2020年に作っていたスタックマシン型コンパイラ  Ver.2: 2021年から作っているレジスタマシン型コンパイラ 機能は（やっと）Ver.2 > Ver.1 性能も Ver.2 > Ver.1

スタックマシンでのコード生成 OpeLaコンパイラVer.1のコード生成は愚直に木をたどる Gen(N): // ノードを評価し、結果をスタックにPush If N is 整数リテラル: Push(N) N Else: Gen(Left) L R Gen(Right) Pop(RDI) Pop(RAX) Op(RAX, RDI) Push(RAX) ノードを評価した結果は、必ずスタックトップに書かれる

具体例：1+2+3 コンパイル対象の式 抽象構文木 1+2+3 出力コード + + 1 3 2 push 1 push 2 pop rdi pop rax add rax, rdi push rax push 3 pop rdi pop rax add rax, rdi push rax

愚直にレジスタマシンに変換してみる スタックにPushする代わりに、レジスタにMov Gen(R1, N): // ノードを評価し、結果をレジスタR1に格納 If N is 整数リテラル: Mov(R1, N) Else: Gen(R1, Left) R2 = GetFreeReg() Gen(R2, Right) Op(R1, R2) AddFreeReg(R2) N L R ノードの評価値の格納先をGenの引数で指定する

レジスタ消費が少ないケース 左側にだけ発達している木に対し、出力コードは次の通り コンパイル対象の式 抽象構文木 RAX + 1+2+3+4 RAX + RAX + RAX 1 レジスタ消費は高々2 4 R10 3 R10 2 R10 出力コード mov mov add mov add mov add rax, r10, rax, r10, rax, r10, rax, 1 2 r10 3 r10 4 r10

レジスタ消費が多いケース 右側に発達している木に対し、出力コードは次の通り コンパイル対象の式 1+(2+(3+4)) 抽象構文木 出力コード RAX + + R10 RAX 1 R10 2 + R11 R11 3 レジスタ消費は高々4 明らかに無駄なレジスタ割り付け 4 RDI mov mov mov mov add add add rax, r10, r11, rdi, r11, r10, rax, 1 2 3 4 rdi r11 r10

レジスタ割り付け戦略 A) スタックマシンとして構成したコンパイラを、愚直にレジスタマ シンに変換する  木の形によっては容易にレジスタが枯渇  レジスタが枯渇したらメモリに逃がす（spill） B) スタックマシンでIRを出力し、後からレジスタ割り付け  IRでは仮想レジスタ（無限個ある）を使う  IRを読み、仮想レジスタと物理レジスタの対応を頑張って決める C) スタック使用を許しつつも、ある程度の最適化を達成する D) 木のたどり方を工夫して最適なレジスタ割り付けを決める

最適なレジスタ割り付けを決める Ershov数を使うアルゴリズム  「コンパイラ―原理・技法・ツール」より Ershov数=そのノードを評価するのに必要なレジスタの数 Ershov数の求め方 1. すべての葉のラベルを「1」とする 2. 1つの子だけ持つ中間ノードのラベルは、 子と同じ数値とする 3. 2つの子を持つ中間ノードのラベルは a. b. 子の数値が異なる→大きい方と同じ数値 子の数値が等しい→それより1大きい数値 + 3 + 2 + 2 1 2 3 1 1 1 + 2 5 6 1 1

実装して実験 OpeLaコンパイラに実装して実験した echo 'func main() int { return (1+2) + ((3+4) + (5+6)); }' | ./opelac mov mov add mov mov add add mov mov add add eax, edi, rax, edi, esi, rdi, rax, edi, esi, rdi, rax, 3 4 rdi 5 6 rsi rdi 1 2 rsi rdi 生成された計算プログラムは 3つのレジスタを使う最適なものになった ※eaxなどのレジスタを使うのは 演算順序とは関係ない最適化を施したため

Ver.1とVer.2の性能比較
func main() int {
return fib(40) != 102334155;
}
func fib(n int) int {
if n <= 1 {
return n;
} else {
return fib(n-1) + fib(n-2);
}
}

コンパイラ

実行時間
（5回の最良）

アセンブラ行数

OpeLa Ver.1

1.36秒

104

OpeLa Ver.2

0.629秒

69

GCC 10.2 -O0

0.664秒

GCC 10.2 -O3

0.170秒

Python3

28.6秒

Core i7 1165G7 2.80GHz/32.0GB RAM/Ubuntu 20.04 on WSL2
使用したOpeLaは6/30の時点のもの
 コミットID eb6fd5643447858094263bb7d744de74189440ac
GCC -O0に勝った！

目次 MikanOSとOpeLa OpeLa言語 OpeLaコンパイラの内部 構文に関する考察

定義を後置できることによる難しさ OpeLaでは変数、関数、型の定義を後置 できる  識別子を見た時点では区別できない Cの型変換は紛らわしい  (foo)(bar)  fooが変数名ならfooの評価結果を使った関数 呼び出し  fooが型名なら型変換 ジェネリクスが登場するとなお難しい  foo<bar>(0)  (foo < bar) > 0 かもしれない func main() MyInt { return Add(2, 3); } func Add(a, b int) int { return a + b; } type MyInt int64;

型変換の構文 OpeLaでの型変換は「値 @ 型」  x := 42@int8;  xは8ビット整数型となる ＠はC/C++で奇跡的に空いてる演算子だった ダブルミーニング  型変換→Cast→cAsT→AT→@  型→Kata→kATa→@

ジェネリクスの構文 C++では foo<bar>  構文解析時に意味解析の結果（fooやbarが指すものの情報）が必要 Rustでは foo::<bar>  通常は値を期待している文脈で型を指定するとき、::<>を使う  ::<> Turbofish構文（魚ロケット） OpeLaでは foo@<bar>  型変換演算子を拡張し、型リストを取れるようにした  「@の後ろには型が来る」という一貫性ある拡張

協力者募集

OpeLaプロジェクトは協力者募集中です OpeLaプロジェクトのロゴ製作 言語の設計に関する議論の話し相手  ex「a==bで両辺の型が違うとき、どこまで暗黙的な型変換を許すか」 OpeLa言語を使ったサンプルアプリ開発 コンパイラ開発 コンパイラのAArch64移植 アセンブラ、リンカ、ライブラリ、ビルドツール開発 OpeLa言語へのMikanOS移植 興味ある方はお声かけください。開発用Slackにご招待します。

まとめ MikanOSとOpeLa  OpeLaはセルフホストなOSと言語処理系を作るプロジェクト OpeLa言語  OSを書くのに便利な機能（アドレス型とか）がある OpeLaコンパイラの内部  Ershov数を用いたレジスタ割り当て 構文に関する考察  後方定義、型演算子@ 協力者募集

質疑応答用スライド

Ershov数を使ったコード生成 準備  レジスタに通し番号を振る：R[0], R[1], …… コード生成  ルートから開始し、再帰的に実行  ラベルkを持つ中間ノードのコード生成は、k個のレジスタだけを使う • 番号のベース値「b」から始まるk個：R[b], R[b+1], …… R[b+k-1] • 評価結果は常にR[b+k-1]に格納される + 3 + 2 0 1 2 + 2 1 2 3 1 1 1 評価結果が格納されるレジスタ + 2 5 6 1 1

2つの子のラベルが等しい場合 評価対象ノードのラベルを「k」とすると、子のラベルは「k-1」である 1. ベース値「b+1」を使い、右辺のコードを再帰的に生成  結果はR[b+k-1]に格納されることになる 2. ベース値「b」を使い、左辺のコードを再帰的に生成  結果はR[b+k-2]に格納されることになる 3. Op(R[b+k-1], R[b+k-2]) + 3 0 1 2 + 2 1 2 1 1 0 1 2 + 2 0 1 2 + 2 0 1 2 0 1 2 5 6 1 1 0 1 2

2つの子のラベルが異なる場合 評価対象ノードのラベルを「k」とすると、 大きい方の子は「k」、小さい方の子は「k-1」 1. ベース値「b」を使い、大きな子のコードを再帰的に生成  結果はR[b+k-1] 2. ベース値「b」を使い、小さな子のコードを再帰的に生成  子のラベルをmとすると、結果はR[b+m-1]  m<kなのでR[b+k-1]は使用されない 3. Op(R[b+k-1], R[b+m-1]) あるいは Op(R[b+m-1], R[b+k-1]) Mov(R[b+k-1], R[b+m-1])  大きな子が左右どちらにあるかに応じて + 3 + 2 0 1 2 + 2 0 1 2 0 1 2 3 m=1 <2 1 5 6 1 1

Ver.1とVer.2の出力コードの比較
今回注目する部分
func fib(n int) int {
if n <= 1 {
return n;
} else {

OpeLa Ver.1の出力
mov qword ptr [rbp+-8], rdi
push rax
lea rax, [rbp-8]
push qword ptr [rax]
push 1
pop rdi
pop rax
cmp rax, rdi
setle al
movzx eax, al
push rax
pop rax
test rax, rax
jz LABEL0

OpeLa Ver.2の出力
mov qword ptr [rbp-8], rdi
mov rax, qword ptr [rbp-8]
mov edi, 1
cmp rax, rdi
setle al
movzx eax, al
test rax, rax
jz LABEL1