iterable-company commented 1 year ago

参照する本 https://www.sigbus.info/compilerbook

参考: 植山先生のWebiner https://github.com/iterable-company/compiler_for_lower_layer/issues/2

x86-64機械語入門 https://zenn.dev/mod_poppo/articles/x86-64-machine-code

iterable-company commented 1 year ago

次回 Cとそれに対応するアセンブラから

iterable-company commented 1 year ago

https://chat.openai.com/c/27dd64a7-1de3-41c8-ba23-243add1b5c15

int main() {} で返された値はコマンドの終了コードになる。 $echo $? で見ることができる。

callの動き

callというのは関数を呼び出す命令です。具体的にcallは次のことを行います。

callの次の命令（この場合ret）のアドレスをスタックにプッシュ
callの引数として与えられたアドレスにジャンプ

ret の動き

retを呼んで関数からリターンしています。具体的にretは次のことを行います。

スタックからアドレスを1つポップ
そのアドレスにジャンプ

解説

plusからリターンしたところにあるのはmainのret命令です。元のCコードではplusの返り値をそのままmainから返すということになっていました。ここではplusの返り値がRAXに入った状態になっているので、そのままmainからリターンすることで、それをそのままmainからの返り値にすることができます。

章まとめ

CPUはメモリを読み書きすることでプログラムの実行を進めていく
CPUが実行するプログラムと、そのプログラムが扱うデータは、どちらもメモリに入っていて、CPUはメモリから順に機械語命令を読み、その命令を実行する
CPUにはレジスタという小さな記憶領域があり、多くの機械語はレジスタ間での操作として定義されている
アセンブリは機械語を人間にとって読みやすくした言語で、Cコンパイラは普通はアセンブリを出力する
Cの関数はアセンブリでも関数になる
関数呼び出しはスタックを使って実装されている

次回 https://www.sigbus.info/compilerbook#%E9%9B%BB%E5%8D%93%E3%83%AC%E3%83%99%E3%83%AB%E3%81%AE%E8%A8%80%E8%AA%9E%E3%81%AE%E4%BD%9C%E6%88%90 から

iterable-company commented 1 year ago

電卓レベルの言語の作成

再帰下降構文解析法(recursive descent paring)

$ bash -x test.sh のように -x をつけると verbose になる。

long strtol(const char *nptr, char **endptr, int base); baseにした基数でnptrの数値文字列を数値に変換する。最初に数値でない文字列と出会った位置のアドレスをendptrに設定する。

iterable-company commented 1 year ago

step 3: トークナイザを導入

https://chat.openai.com/c/1513446d-06e7-41af-9848-251cee461738

void* calloc(size_t num_elements, size_t element_size);

element_sizeのサイズを持つものを num_element個分の領域を確保して先頭のアドレスを返す。

step 4: エラーメッセージを改良

error_at の第一引数に token->str を渡しているのがミソ。

次回 https://www.sigbus.info/compilerbook#%E6%96%87%E6%B3%95%E3%81%AE%E8%A8%98%E8%BF%B0%E6%96%B9%E6%B3%95%E3%81%A8%E5%86%8D%E5%B8%B0%E4%B8%8B%E9%99%8D%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90

iterable-company commented 1 year ago

文法の記述方法と再起下降構文解析

パーサの出力のデータ構造を知り、最終的なゴールを把握する
文法規則を定義するルールを学ぶ
文法規則を定義するルールをもとに、パーサを書くテクニックを学ぶ

木構造による文法構造の表現

パーサでは、フラットなトークン列を木構造にする。

左から計算しなければいけない演算子を「左結合」の演算子、右から計算しなければいけない演算子を「右結合」の演算子という。代入の = を除いて、ほとんどは左結合。

AST表現

算術演算のように2つの項に対する演算として定義されているものは２分木にする。関数の本体のように、順番に実行されるだけの場合は、子要素をフラットに持つ木として表す。

生成規則による文法の定義

BNF

それ以上展開できない記号を「終端記号」（terminal symbol）どれかの生成規則の左辺に来て展開できる記号を「非終端記号」（nonterminal symbol）生成規則で定義される文法を「文脈自由文法」（context free grammer）

非終端記号は複数の生成規則にマッチしても良い。 => A = α1 と A = α2 の両方の規則があった場合、Aはα1, α2のどちらに展開しても良い。

生成規則の右辺は、空でもいい。 => ε で表す

文字列はダブルクオートで括って"foo"のように書く。文字列は常に終端記号。

書き方	意味
A*	Aの0回以上の繰り返し
A?	Aまたはε
A \| B	A または B
( ... )	グループ化

例: A = ("fizz"|"buzz") は Aは、"fizz"または"buzz"が0回以上繰り返された文字列

単純な生成規則

expr = num ( "+" num | "-" num )*

EBNFでは木構造を表すだけで、演算を左から順番に行うなどの規則はない。言語仕様に「加減算は左から先に行う」などと書いておく。

生成規則による演算子の優先順位の表現

expr = mul ("+" mul | "-" mul)*
mul = num ("*" num | "/" num)*

平坦な単純な構造では、上記で演算の優先順位が表されている。

再帰を含む生成規則

expr = mul ("+" mul | "-" mul )*
mul = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

カッコも含めた優先順位が表されている。

iterable-company commented 1 year ago

再帰下降構文解析

今やりたいことは、生成規則から具象構文木を構成する、つまりプログラムを構成する。のではなく、その反対でプログラムが与えられた時に、抽象構文木を構成すること。

ある種の生成規則については、規則が与えられれば、その規則から生成される文にマッチする構文木を求めるコードを機械的に書くことができる。

次回 https://www.sigbus.info/compilerbook#%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF%E3%83%9E%E3%82%B7%E3%83%B3

iterable-company commented 1 year ago

スタックマシン

前回で演算の優先度に対応した抽象構文木の構成方法を学んだ。今回は、この木をアセンブリに変換する方法を説明する。

加減算の場合は、状態の保持は1つだけ（rax）で良かったが、乗除算が加わった今回は１つだけで済むとは限らない。ここでスタックマシンの登場。

スタックマシンの概念

スタックマシンのADD命令はスタックから2つ値をpopしてきて、それらを加算し、結果をスタックにpushする。 SUB, MUL, DIVも演算は違うがスタックの動作は同じ。

計算例:

// 2"3
PUSH 2
PUSH 3
MUL

// 4*5
PUSH 4
PUSH 5
MUL

// 2*3 + 4*5
ADD

CISC と RISC

CISCは

機械語の演算がレジスタだけではなくメモリアドレスを取ることが可能
機械語命令が可変長
複雑な命令を１語で行う命令が備わっている

RISCは

演算は必ずレジスタ間のみで行い、メモリに対する操作はレジスタへのロードとレジスタからのストアだけである
機械語命令が固定長
簡単な命令のみ備えている

x86-64以外はCISCだが、それ以外に生き残っているプロセッサはほとんどがRISCベース。 ARM, PowerPC, SPARC, MIPS, RISC-V

RISCは高速化しやすい。Intelはx86-64の命令を内部的にRISC型の命令に変換して、RISCプロセッサ化し、高速化を行った。

スタックマシンへのコンパイル

A + B　を抽象構文木化した。

   +
A    B

をコンパイルする時は、

左の部分木をコンパイルする
右の部分木をコンパイルする
スタックの２つの値を、それらを加算した結果で置き換えるコードを出力

   +
2    *
    3    4

PUSH 2
PUSH 3
PUSH 4
MUL
ADD

x86-64におけるスタックマシンの実現方法

x86-64はスタックマシンではなく、レジスタマシン。スタックマシンのテクニックをレジスタマシンでエミュレートする。

方法: スタックマシンで１つの命令になっているものを、レジスタマシンでは複数の命令に分解する

スタックの先頭の要素を指すレジスタを用意する => スタックポインタという
pop, pushともに、スタックポインタの指す位置を変更して、値を取り出したり、書き込んだりすればよい

// 1 + 2
push 1
push 2

pop rdi
pop rax
add rax, rdi

push rax

// 2"3 + 4*5
push 2
push 3

pop rdi
pop rax
mul rax, rdi
push rax

push 4
push 5

pop rdi
pop rax
mul rax, rdi
push rax

pop rdi
pop rax
add rax, rdi
push rax

idiv 命令

idivは符号あり除算を行う命令。 idivは暗黙のうちにrdxとraxをとって、それを合わせたものを128ビット整数とみなして、それを引数のレジスタの64ビットの値で割る。商をraxに、余りをrdxにセットする。 cqo命令を使うと、raxに入っている64ビットの値を128ビットに伸ばしてrdxとraxにセットすることができる。

最適化

アセンブリを出力するところで最適化するようにせず、出力は素直な実装で行い、出力されたアセンブリをスキャンして特定の系列を別の命令で置き換えるようにした方がよい。

iterable-company commented 1 year ago

step5: 四則演算のできる言語の作成

メモリ管理しないポリシー

allocで確保しているメモリをfreeで解放していないが、これは意図的。コンパイラはアセンブリを生成するだけの短命なプログラムで、出力が終わって実行が終わるとメモリは全てOSに戻されるため、いちいち解放する必要がない

次回 https://www.sigbus.info/compilerbook#%E3%82%B9%E3%83%86%E3%83%83%E3%83%976%E5%8D%98%E9%A0%85%E3%83%97%E3%83%A9%E3%82%B9%E3%81%A8%E5%8D%98%E9%A0%85%E3%83%9E%E3%82%A4%E3%83%8A%E3%82%B9

iterable-company commented 1 year ago

step6: 単項プラスと単項マイナス

expr = mul ( "+" mul | "-" mul)*
mul  = unary( "*" unary | "/" unary)*
unary = ("+"|"-")? primary
primary = num | "(" expr ")"

を実装。ここで、- num はパース時点で 0 - num に変換してしまう。

次回 https://www.sigbus.info/compilerbook#%E3%82%B9%E3%83%86%E3%83%83%E3%83%977-%E6%AF%94%E8%BC%83%E6%BC%94%E7%AE%97%E5%AD%90

iterable-company commented 1 year ago

https://chat.openai.com/c/8480d41a-6eee-4bb9-a3fc-9f254cc6aa8f

step7: 比較演算子

トークナイズするときは長さの長い文字列から先にトークナイズする。そうしなければ、">=" を">"と"="に分解してしまう現象が起きる。

expr       = equality
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | "(" expr ")"

アセンブリの生成

cmp命令: 同一の場合1、そうでない場合は0

pop rdi
pop rax
cmp rax, rdi
sete al
movzb rax, al

x86-64では、比較命令の結果は特別な「フラグレジスタ」というものにセットされる。。フラグレジスタは整数演算や比較演算命令が実行されるたびに更新されるレジスタで、

結果が0かどうかといったビット
桁あふれが発生したかどうかというビット
結果が0未満かどうかといったビットなどを持っている。

ALはRAXの下位8ビットを指す別名レジスタにすぎない。 seteがALに値をセットすると、自動的にRAXも更新されることになる。 RAX全体を使用する場合は、上位56ビットをゼロクリアする必要がある。

movzb命令 => コピーする際に、コピー元の下位1バイトはそのままで、上位ビットはゼロを埋める

iterable-company commented 1 year ago

https://chat.openai.com/c/b03d6948-392f-4cd6-b253-c26a767582e8

分割コンパイル

全てのプログラムを一つのファイルに書けば、理論的にはリンカは不要。そういう場合、標準関数のようなものも、そのファイルに含めなければならず、標準関数を外だししようとすると、それだけリンカは必要になる。

分割コンパイル

一つのファイルにつき、一つのオブジェクトファイルができる。これをつなぎ合わせるのがリンカの役目

ヘッダファイルの必要性とその内容

void print_bar(struct Foo *obj) {
  printf("%d\n", obj->bar);
}

上記のコードを分割コンパイルする場合、struct Foo について知っていなければならない。

例）　別のCファイルに入っている関数を呼び出すコードを出力するために必要な情報

識別子が関数の名前であることを知っている
引数の個数、それぞれの型

必要ない情報

呼び出す先の関数の実装
関数のアドレス
- とりあえずアドレス0にジャンプするようなcall命令を出力する
- オブジェクトファイル内に、「オブジェクトファイルのXバイト目をYという名前の関数のアドレスで修正する」という情報を残しておく

関数宣言には、宣言を表す extern をつけてもよいが、通常はファイルが分割されていることで見ればわかるのでつけない。

#include "foo.h"

と書いておくと、#includeの行がfoo.hファイルの内容に置き換えられる。

typedef もコンパイラに型情報を教えるために使われる。複数のCファイルで使われている場合、ヘッダファイルに書いておく。コンパイラは宣言を読み込んだだけではなんのアセンブリも出力しない。

一つのファイルに全プログラムを閉じ込めた場合でも、あるものをコンパイルするときに、その行までの情報でコンパイルできなければいけない仕様になっている。そのため、後ろに実装があるものの宣言を予め上部に書いておく必要がある場合がある。

リンクエラー

実体がなくても、宣言だけあればコンパイル自体はとおる。リンカがアドレス解決をしようとした時に、修正する先のアドレスがないリンクエラーになる。

複数のオブジェクトファイルに同じ関数、変数が含まれている場合もリンクエラーになる。ヘッダファイルに実体が書かれていると、それをインクルードしているところで、それぞれコンパイルされてしまい複数実体が定義されているのと同じ状態になってしまう。例外的に、インライン関数、C++のテンプレートの展開結果は重複を許す形でオブジェクトファイルに含まれる。

グローバル変数の宣言と定義

グローバル変数はアセンブリレベルでは関数と同じようなもの。 => 定義と宣言をわける必要がある => 変数の本体が複数のCファイルに重複している場合、リンクエラーになる

グローバル変数はデフォルトでは実行禁止メモリ領域に割り当てられている。

extern をつけると宣言になる。

extern int foo;

以下は、どれか一つのファイルでの定義

int foo;

初期化で値を与える場合は、「定義」で与えるものであり、「宣言」で与えるものではない。

iterable-company commented 1 year ago

Step 8 ファイル分割とMakefileの変更

Makefile

コロンの前の名前をターゲットと呼ぶ。コロンに続く0個以上のタブインデントされたコマンドの行が続く。コロンの後ろに続く0個以上のファイル名のことを依存ファイルと呼ぶ。

.PHONY はターゲットがその名前のファイルを作りたいわけではない場合に指定する。 => clean, test など

次回 https://www.sigbus.info/compilerbook#%E9%96%A2%E6%95%B0%E3%81%A8%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E5%A4%89%E6%95%B0 から

iterable-company commented 11 months ago

step9: 1文字のローカル変数

変数はアドレスに名前をつけたようなもの。関数fのローカル変数aを固定アドレスにしてしまうと、再帰的に呼び出されたときにうまくいかない。 => スタックに変数を積む

call命令はリターンアドレスをスタックに積む => 関数が呼び出された時点でのスタックトップにはリターンアドレスが積まれている

rsp が始めリターンアドレスを指しており、関数のローカル変数a, b の領域を確保し、スタックは伸長し、rspの指す位置が変わる。 rsp は演算命令のときに変更されるため、関数フレームの最初の位置を指すベースポインタを導入する。rbp 関数実行中にはベースポインタを変更してはいけない。関数呼び出し毎に元のベースポインタを保存しておいて、リターンする前に書き戻す。

例）ロカール変数x, yを持つ関数gの呼び出し内で、さらにローカル変数x, yを持つ関数fを呼び出した場合
...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス
fの呼び出し時点のrbp
a
b

rbpは「fの呼び出し時点のrbp」の位置を指しており、rspはbの位置を指すようにしたい。それは以下で実現できる。

push rbp
mov rbp, rsp
sub rsp, 16

fをcallで呼び出した直後のスタック


...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス

rbp:「gの呼び出し時点のrbp」のアドレス rsp: |fのリターンアドレス|のアドレス

push rbp を実行


...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス
fの呼び出し時点のrbp（「gの呼び出し時点のrbp」のアドレス）

rbp: 「gの呼び出し時点のrbp」のアドレス rsp: 「fの呼び出し時点のrbp」のアドレス

mov rbp, rsp を実行した後のスタック


...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス
fの呼び出し時点のrbp（「gの呼び出し時点のrbp」のアドレス）

rbp: 「fの呼び出し時点のrbp」のアドレス rsp: 「fの呼び出し時点のrbp」のアドレス

sub rsp, 16 を実行した後のスタック


...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス
fの呼び出し時点のrbp（「gの呼び出し時点のrbp」のアドレス）
a
b

rbp: 「fの呼び出し時点のrbp」 rsp: 「b」

iterable-company commented 11 months ago

step9 その2

関数からリターンするときには、rbpに元の値を書き戻して、rspがリターンアドレスを指している状態にしてret命令を呼び出す。

mov rsp, rbp
pop rbp
ret

mov rsp, rbp を実行する前のスタック


...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス
fの呼び出し時点のrbp
a
b

rbp: 「fの呼び出し時点のrbp」 rsp: 「b」

mov rsp, rbp


...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス
fの呼び出し時点のrbp
a
b

rbp: 「fの呼び出し時点のrbp」 rsp: 「fの呼び出し時点のrbp」

pop rbp


...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス
fの呼び出し時点のrbp
a
b

rbp: 「gの呼び出し時点のrbp」 rsp: 「fのリターンアドレス」

pop した値の行き先が rbpだから

ret


...
gのリターンアドレス
gの呼び出し時点のrbp
x
y
fのリターンアドレス
fの呼び出し時点のrbp
a
b

rbp: 「gの呼び出し時点のrbp」 rsp: 「y」

call命令は自身の次の命令がある位置のアドレスをスタックに積む。 => retでcallの次の命令から再開される

iterable-company commented 11 months ago

step9 その3

program    = stmt*
stmt       = expr ";"
expr       = assign
assign     = equality ("=" assign)?
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | ident | "(" expr ")"

左辺式と右辺式

代入式の左辺にくるのは、メモリアドレスを指定する式。 a + 1 といった式はレジスタだけに存在する可能性もあるため、メモリ位置を表すものとして扱えないため、&(a+1)のような表現も無効。

任意のアドレスから値をロードする方法

ローカル変数にアクセスするにはスタックトップだけでなく、スタック上の任意の位置にアクセスする必要がある。

mov dst, [src]

srcのメモリ位置に入っている値をアドレスとみなして、そのアドレスに入っている値をdstにセットする。

push, pop は rsp をアドレスとみなしてメモリアクセスするので、 push rax

mov [rsp], rax
add rsp, 8

pop rax

mov rax, [rsp]
sub rsp, 8

次回 https://www.sigbus.info/compilerbook#%E3%82%B9%E3%83%86%E3%83%83%E3%83%9710%E8%A4%87%E6%95%B0%E6%96%87%E5%AD%97%E3%81%AE%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E5%A4%89%E6%95%B0 から

iterable-company commented 11 months ago

差し込み https://www.youtube.com/watch?v=xH8eThCt3R0

mold と再現可能なビルド

再現可能なビルド: 毎回同じバイナリが出力されるビルド

マシンによらない、OS、タイムゾーン、時刻などによらないセキュリティ上望ましい => shaが毎回同じ

悪意のあるコードをコミットしても、ソースコードが公開されているから信頼性の担保になる。誰かにハイジャックされて配布バイナリが異なっている場合でも大丈夫。

コンパイラ、リンカは狙われる危険性が高い。 => サプライチェーンアタックビルドで使っているプログラムに何かを埋め込むことができるから。

再現不可能にする要因

コンパイラ、リンカ、ライブラリのバージョンの違いタイムスタンプ（時間依存）

ファイルのタイムスタンプ
ファイルヘッダに埋め込まれたタイムスタンプ

ランダム性

ファイル一覧を取得した時のファイルの順番
マルチスレッド化されたプログラムの出力のランダムさ

ビルドを再現可能にする手法

コンパイラ、リンカ、ライブラリは同一のものを使うタイムスタンプは現在時刻ではなく、特定の決められて時間にするランダム性を排除する（ソートするとか）

コンパイラ、リンカ、ライブラリを同一にする

dockerを使う => shaハッシュも指定する

apt-get である日付のレポジトリの状態から取ってこれるので、バージョンを揃えることができる => snapshot.debian.org

タイムスタンプ

最後にコミットしたgit の時間

生成したファイルのタイムスタンプをtouchコマンドでリセットする gzipするときに --no-nameする

moldにおけるチャレンジ

libc を static リンクすると dlopen が使えなくなる => リンクタイム最適化が使えなくなる

古いglibcでビルドしないと、それより古いバージョンのglibc のマシンでは動かない

https://github.com/rui314/mold/blob/main/dist.sh

iterable-company commented 11 months ago

step10: 複数文字のローカル変数

次回 https://www.sigbus.info/compilerbook#%E3%82%B9%E3%83%86%E3%83%83%E3%83%9711return%E6%96%87

iterable-company commented 11 months ago

step11 return 文

program    = stmt*
stmt       = expr ";" | "return" expr ";"
expr       = assign
assign     = equality ("=" assign)?
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | ident | "(" expr ")"

return 用にトークンTK_RETURNを用意する。文法上特別な意味を持つトークンには、別の型をあてがう

iterable-company / compiler_for_lower_layer

Note #1

callの動き

ret の動き

解説

章まとめ

電卓レベルの言語の作成

step 3: トークナイザを導入

step 4: エラーメッセージを改良

文法の記述方法と再起下降構文解析

木構造による文法構造の表現

AST表現

生成規則による文法の定義

単純な生成規則

生成規則による演算子の優先順位の表現

再帰を含む生成規則

再帰下降構文解析

スタックマシン

スタックマシンの概念

CISC と RISC

スタックマシンへのコンパイル

x86-64におけるスタックマシンの実現方法

idiv 命令

最適化

step5: 四則演算のできる言語の作成

メモリ管理しないポリシー

step6: 単項プラスと単項マイナス

step7: 比較演算子

アセンブリの生成

分割コンパイル

分割コンパイル

ヘッダファイルの必要性とその内容

リンクエラー

グローバル変数の宣言と定義

Step 8 ファイル分割とMakefileの変更

Makefile

step9: 1文字のローカル変数

step9 その2

step9 その3

左辺式と右辺式

任意のアドレスから値をロードする方法

mold と再現可能なビルド

再現不可能にする要因

ビルドを再現可能にする手法

コンパイラ、リンカ、ライブラリを同一にする

タイムスタンプ

moldにおけるチャレンジ

step10: 複数文字のローカル変数

step11 return 文