狠狠撸

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ファイルシステム
?パイプ、リダイレクト
?日本語の教科書が完備された、現
代的なPCで動作する教育用OS
MikanOSの30章後の姿

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

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

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

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

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

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

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

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

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

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

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

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

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)
Else:
Gen(Left)
Gen(Right)
Pop(RDI)
Pop(RAX)
Op(RAX, RDI)
Push(RAX)
?ノードを評価した結果は、必ずスタックトップに書かれる
N
L R

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

愚直にレジスタマシンに変換してみる
?スタックに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)
?ノードの評価値の格納先をGenの引数で指定する
N
L R

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

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

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

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

実装して実験
?OpeLaコンパイラに実装して実験した
?echo 'func main() int { return (1+2) + ((3+4) + (5+6)); }' | ./opelac
mov eax, 3
mov edi, 4
add rax, rdi
mov edi, 5
mov esi, 6
add rdi, rsi
add rax, rdi
mov edi, 1
mov esi, 2
add rdi, rsi
add rax, 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に勝った！

定義を後置できることによる難しさ
?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]に格納される
+
6
5
+
+
+
3
2
2
1 1
3
1
2
1
2
1
1
0 1 2
評価結果が格納されるレジスタ

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

2つの子のラベルが異なる場合
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])
? 大きな子が左右どちらにあるかに応じて
+
6
5
+
+ 3
2
2
1
1
評価対象ノードのラベルを「k」とすると、
大きい方の子は「k」、小さい方の子は「k-1」
0 1 2
0 1 2
0 2
1
1
3
m=1
<2

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

狠狠撸

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

More Related Content

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