ltmemo

低レイヤを知りたい人のためのCコンパイラ作成入門を読んだ

tags: compiler
2022-05-12

ToC

何を学ぶか

  • アセンブラで計算が行われる仕組みがわかる
  • ポインタのポインタがコンパイラでどのように実装されているか理解できる
  • コンパイラがアセンブラを吐き出すまでの流れがぼんやりわかる
  • C言語の構文に今より少し詳しくなっている

x86の命令

  • PC(プログラムカウンタ) IP(インストラクションポインタ)
    • 現在実行中の命令のアドレス
  • ISA(Instruction set architecture) 命令セット
  • branch instruction
    • 分岐命令
  • x86-64には歴史的経緯でいろんな名前がある
  • アセンブリ
    • 機械語に1:1で対応しつつ人にもまあ何とか読めなくはない形式
  • アセンブラ
    • アセンブリを機械語に変換する

アセンブラメモ

  • ret呼び出し時、raxレジスタに入っている値が戻り値になる
  • 関数の引数は第一引数からrdi, rsiに入れる
    • 確か5つぐらいまで入れられる。残りはスタックに積まれる
  • movは値をコピーする
  • .intel_syntax noprefixは、intelの命令を使うためのおまじないだそうな
  • 演算の優先順位は、生成文法の組み方で表現可能
    • 優先順位の異なる演算子は別の非終端記号にmapされる
  • 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 ")"

BNF, EBNF

Backus Naur formでBNF。EはExtendedのE
生成規則を記述するための記法

A = a1a2という形式で示す。これはAはa1a2のような0個以上の記号の列で示せる
それ以上展開できない記号が「終端記号(terminal symbol)」
どれかの生成規則の左辺に来ていて展開できるのを「非終端記号(nonterminal symbol)」と呼ぶ

非終端記号は複数の生成規則にマッチしても構わない

右辺は長さ0の記号(空)でも構わない。わかりづらいのでεが使われるんですって

EBNFで追加される、ちょっと複雑な例

  • A* 0個以上の繰り返し
  • A? Aもしくはε
  • A | B AもしくはB
  • (...) グループ化

再帰も可能。例えば四則演算の文法はこうなる

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

LL(1)パーサ

トークンを一つだけ先読みする再帰下降パーサのことをLL(1)パーサと呼ぶ
でもってLL(1)パーサが書ける文法のことをLL(1)文法という

スタックマシン

23+45のような計算は、二つの乗算の結果を保持していないとそのあとの加算が計算できない
この中間的な結果を保持しつつ計算できる仕組みがスタックマシーン

名前の通りスタックにpushしてpopしてイイ感じにする
stackの上にある要素を二つpopして計算してstackに積む、みたいなイメージ

x86-64はスタックマシンではなくレジスタマシン。x86-64の演算は通常は二つのレジスタに対して定義されていて、 スタックトップの二つの値に対して動作するように定義されているわけではない

レジスタマシンでどうやってスタックマシンをエミュレートするか

スタックマシンの1命令を複数命令で実装する

スタックの先頭の要素を指すレジスタを一つ用意しておく。これがスタックポインタ
スタックトップの二つの値をポップしたインド絵あれば、スタックポインタの要素を二つ取り出して、
取り出した要素の分だけ変更しておく
プッシュするときはスタックポインタの値を変更しつつ、それがさしているメモリ領域に書き込めばよい

x86-64のPSRレジスタはスタックポインタとして使うことを念頭に置いている
pushやpopという命令は暗黙のうちにRSPポインタをスタックポインタとして使う

push 1 push 2 //レジスタにロード pop rdi pop rax add rax, rdi push rax

のような感じ

idiv命令

idivは暗黙のうちにRDXとRAXをとってそれを128bit整数とみなして、引数の64bitで割り
商をRAX、余りをRDXにセットするという仕様になっている
cqo命令を使うとRAXに入っている64bitの値を128bitに伸ばしてRDXとRACにセットできるので
idivを呼ぶ前にcqoを呼ぶ

比較演算

# stackからのpop
pop rdi
pop rax
# 比較。結果はフラグレジスタというものにセットされる
cmp rax, rdi
sete al
movzb rax, al
  • seteはequal
  • <=ならsetle、!=ならsetneだよん

フラグレジスタ

演算結果が0かどうか、桁あふれが起きたか、結果が0未満かなどの毛㏍を格納するbitを持つ
通常の整数レジスタじゃなインド絵、raxに結果をセットしたい場合、フラグレジスタの特定bitをraxに持ってくる必要がある

seteは、cmpで調べた二つのレジスタの内容が同じとき、指定されたレジスタに1をsetする
上の例ではsete alのようにalを指定している
alはraxの下位8bitのalias
このときraxも更新されるのでゼロクリアしたい。それをやるのがmovzb

makefileメモ

  • コロンの左をターゲットと呼ぶ
  • ターゲットとタブでインデントされた0行以上のコマンドが一つのルールを構成する
  • コロンの後ろのファイル名を依存ファイルと呼ぶ
  • make fooでfooを作成しようとする。ここですでにファイルがある場合、依存ファイルよりターゲットが古ければルールを再実行する
  • .PHONYはダミーターゲットを作るコマンド
  • ファイル生成はしたくないが処理は行いたい場合に使う。testとかcleanは同じファイルがあると何もしてくれなくなる
  • CFLAGS,SRCSは変数
  • CFLAGSはmakeの組み込みルールで認識される、Cコンパイラに渡されるoption
    • -std=c11 c11で書かれたソースコード（c11は最新規格らしい）
    • -gはデバッグ情報を出力する
    • -staticはスタティックリンクを行う
  • wildcardはmakeの提供する関数で、引数にマッチするファイル名に展開される
  • $(VAL:.a=.b)はVALの.aを.bに置換する

スタックと関数呼び出し

  • ローカル変数はスタック上に置く
  • call命令はリターンアドレスをまずスタックに積む
    • この時点でスタックのトップにはリターンアドレスが積まれて、そこをRSPが指す
    • 8bitの変数a,bを確保すると二つ積まれて16bit先をRSPが指す
    • 変数のサイズはわかっているので、RSP+8でa、RSPでbにアクセスできることになる
  • 関数ごとの呼び出しに確保されるメモリ領域を関数フレーム、アクティベーションレコードと呼ぶ
  • ただしRSPは良く書き換えられるので、RSPとは別のレジスタを関数フレーム開始位置を記録するのに使う
  • これを「ベースレジスタ」、入ってる値を「ベースポインタ」と呼ぶ
  • 慣習的にはRBPがベースレジスタになる
  • 関数の先頭に出力する定型の命令をプロローグと呼ぶ、逆に関数の終わりはエピローグ
  • スタックのアドレスは大きい方から小さい方向に成長する
    • OSとかがアドレス0から始まるのを考えると、プログラムは下位に集まってる
    • なので上の方から伸ばした方が被る可能性がない、ということらしい
    • 実際は設計次第なのでどっちでもよい。が、世間的にはマシンスタックは下に成長するのが一般的

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

mov dst, [src]

のように書く。srcレジスタの値をアドレスとみなしてロードし、dstに保存する

mov rdi, [rax]

なら、raxのアドレスから値を引いてrdiに入れる
逆に設定するときは

mov [dst], src

とする

arrayの実装

  • sizeを返す関数が必要。その場合、保持した要素数*sizeを算出する
  • int x[2] のようになるので、型をparseした後identが来て、そのあとでサイズ（[2]や[1][3]）をparseする必要がある
  • x[1][10]のようなパターンがあるので]をconsumeした後再帰的に見に行く必要がある
  • baseのtype（intとか）の場合だけsize_ofを通して、offsetを計算する
    • pointerか同課の判定は、typeがbaseを持つかどうかで判断できる
    • baseがない場合はpointerかarray
  • 実装はarray_sizeが存在する以外はほぼポインタ
  • arr[3]は*(arr + 3)のエイリアス。&とsizeof以外の時、暗黙的にポインタとしてふるまう
  • 1byteの要素を読み込むときにmovsxやmovzxを使う必要があるのは、x86-64の仕様
    • alとかのエイリアスのレジスタ使うと上位bitにごみが残るんですって

ポインタの理解

  • int *x;と *xのアスタリスクは意味が違う
    • 前者はintのポインタ型を示すが、後者はderefを意味する
    • derefはそのアドレスにある値を持ってくる
  • ポインタ変数int *x;のxは、intのポインタ情報が入る固定長の長さを持つ変数
  • ポインタ型という型が存在するイメージ。この型はderefするとint型を返す
  • 変数なので、ローカル変数であればスタック上に固定長の領域がとられる。これはintの変数と同じ
    • ポインタのポインタも同様。derefするとポインタが帰ってくる
    • 実装上は現在8bit

グローバル変数の実装

  • localsと
  • 書き換え不要な定数は.textセクションに置くらしい
  • .dataセクションは書き換え可能な領域
  • .bssは実行前に値を設定する必要のない領域
  • .zeroはわからなかったけど、.alignとかを指定できるっぽいのでなんかそういう指定なのかも

structの実装

  • mennberへのアクセスは、構造体の位置からmemberのサイズ分のoffsetで表現される
  • memberは上に定義されているものから下に定義されているものまでの連結リストで表現されている
    • Cで可変長引数表現しようとするとこうなるのかな～
  • アクセスの効率化のためか、メンバの中で最大のbit数でalignmentされる
  • struct {int a; char b} x;は16bitになる。intのsizeでalignされるので
    • struct {int a; char b, char c} x;も16bitになる。intのsizeでalignされているが、それをchar二つでは超えないためだと思う

Cの構文

  • 関数が特に厄介
  • int x()
    • intを返す関数。識別子がx
  • int *x()
    • intのポインタを返す関数。識別子がx
  • int (*x)()
    • intを返す関数のポインタ。識別子がx
  • int **(*x)()
    • intのポインタのポインタを返す関数のポインタ。識別子がx
  • void (*x[20])(int)
    • intを引数にとってvoidを返す関数のポインタの配列。要素数は20。識別子はx
  • void (signal(int, void ()(int)))(int);
    • unixのsignal関数
    • signalの引数は、intと、intを引数にとってvoidを返す関数のポインタを引数に取る関数のポインタ
    • signalの返り値は、intを受けてvoidを返す関数へのポインタ

voidという型はメモリ上ではどのように表現されているのか

  • メモリの割り当てはもちろんなされるが、derefするとエラーになるし何かを入れたりできない

その他メモ

  • bash -xで実行トレースが見れる。デバッグで便利そう
  • stdbool.hをincludeしないとtrue/falseが使えない
  • 再帰下降構文解析
    • これで優先度を考慮した演算ができるようになるぞい
    • tokenは連結リストを作って、そのリストをなめながら生成規則に沿ってnodeを作る
      最後にnodeをたどってasmを出力
  • 文字列比較はmemcmpを使う
  • Cでは関数を先頭から順番に、その時点までに存在する情報だけでコンパイルできるようになっている なので、前方宣言が必要な場合がある これは歴史的経緯に依存する挙動（昔はメモリが非常に小さかった）
  • Cのグローバル変数、externをつけると宣言になる
  • 代入式の左辺に来ることができるのはメモリのアドレスを指定する式だけ
    • 変数はメモリの存在していてアドレスを持つので、左辺に書ける
    • *pのようなポインタ参照も、pの値がアドレスという話なので書ける
    • a.bはaの一からbのサイズ分オフセットしたメモリを指している
  • retはstackからアドレスをpopしてそこにジャンプする命令
  • Cの連結リストを更新してくのなんか新鮮だった
    • 生のiteratorもどきを作ってる感じだからだろうか
  • 文脈自由文法では、変数は使用前に宣言する、というようなルールを表現できない
  • 符号アリ整数を8bit->64bitのように拡張する場合、符号bitが1なら上位bitを全部1で埋めて、
  • 符号bitが0なら新たな上位bitを0で埋める
  • アセンブリでもbit演算はできる
    • bit演算に親しみがないので、16の倍数か判定するときに&15を取るのなるほどなーってなった
  • .Lから始まるアセンブリのラベルは、ファイルスコープになって別のファイルからは参照されない
    • ちゃんとuniqueにする必要があるけど助かる
  • forやwhileはjmpとかjeの組み合わせて実現できる
    • gotoで置き換えた処理を考えてからそれをアセンブリに落とすとシンプル
  • 変数定義に際してはnullにも対応した
    • 型のparse自体はそんなにややこしくない
    • int a;のような形式のみをサポートしているため構文がシンプル
  • 関数呼び出しのテストを書くときに、別のソースで定義した関数を呼び出しているのが面白かったな
    • 足りない機能でもアセンブリに落ちてればよいのだ...
  • (n + align - 1) & ~(align - 1)で、nをalignの倍数にできる
    • ただしalignは2^nの必要がある
  • dwordはダブルワードの略
    • ワードは歴史的経緯で、16bitと64bitのことを指す。これはコンピュータ上で自然に扱える整数やアドレスのサイズのこと
    • 32bitになるときワードの意味を変えないようにdouble wordでdword、64bitをquad wordでqwordとか呼ぶようになったそうな
  • 1byte,2byte,4byteと、対応したサイズのレジスタがある
  • short int(2byte)や、long int(4byte)のような型が存在する。ややこしすぎんか？
最終更新: 2022-07-14