しかくいさんかく

解答略のメモ

23日目: [コンパイラ] シンボルテーブル

アドベントカレンダー2017 低レイヤ コンパイラ

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の23日目の記事です。

昨日は抽象構文木を作った。

これをアセンブラコードに変換できればコンパイラは完成だ。 変換の手順は、抽象構文木の最上段のPROGRAMノードから出発し、各ノードをニーモニックに置き換えていけばよい。

今日はその中で宣言系に関するノードを扱う。

やりたいこと

今日のサンプルコード(昨日までとは少し違う)

int g;
int func(int a);

int func(int a) {
  int c;
  c = 3;
  return a+c;
}

の抽象構文木は以下のようになる。

f:id:kaitou_ryaku:20171223181820p:plain

着色したノードは宣言系のノードだ。

  • 水色は宣言のノード
  • 緑色は型と名前のノード

具体的には

  • int型のグローバル変数gの宣言
  • int型の関数funcのプロトタイプ宣言
  • int型の関数funcの宣言
  • 関数funcのint型の引数aの宣言
  • 関数funcのint型のローカル変数cの宣言

これらの宣言は、加算や代入といった具体的操作を表すわけではない。 むしろコンパイラに対し「XXの資源を利用したいです」と予約する感じだ。 コンパイラはこれらの予約情報を受け付けた後で、アセンブラのコードを生成しなければならない。

予約の受付はシンボルテーブルという仕組みで実装される。

今日の目標は、宣言系のノードをシンボルテーブルに変換することだ。

グローバルスコープ

宣言系のノードは大きく2つに分割できる。 PROGRAM直下に生えるグローバル(大域)スコープのノードと、そうではないローカルスコープのノードだ。

グローバルスコープのノードには 関数プロトタイプを表すPROTOTYPE と、 関数宣言を表す F_DEC と、 グローバル変数を表す V_DEC の3つがある。

グローバル変数だけを表示したツリーは

f:id:kaitou_ryaku:20171223181826p:plain:w300

関数プロトタイプだけを表示したツリーは

f:id:kaitou_ryaku:20171223181832p:plain:w300

変数名と関数名は、緑のVARIABLEノードとして抽象構文木に出現している。 このノードは変数名や関数名を表すトークン

  • (IDENTIFY, "func")
  • (IDENTIFY, "g")

で構成されている。

変数と関数の情報を名前をキーとする表にまとめておくと便利だ。 同一スコープの中で名前が被らないことは言語仕様で保証されているので、テーブルのユニークなキーに適している。 文字列をキーにするには少し工夫がいるが、こういう精神で作成した表のことをシンボルテーブルという。

シンボルテーブル

まずはグローバルな情報をまとめたシンボルテーブルがほしい。

名前 スコープ 種類 型 サイズ アドレス トークン ハッシュ
"func" "GLOBAL" 関数 int - - 4 365
"g" "GLOBAL" 変数 int 4 0 1 287

関数プロトタイプのfuncと関数宣言のfuncは重複するので、1つにまとめている。

このテーブルは構造体配列で実装されており、右端のハッシュが配列の添字を表している。

シンボルテーブルの構造体 を見てみると

typedef struct {
  bool  used;
  char *str;         // token.str へのポインタ。"func"
  NODE *node;        // 宣言のノード
  int   kind;        // V_DEC or F_DEC
  int   type;        // intなら0
  int   size;        // V_DEC intなら4byteなので4
  int   token_index; // 変数を参照する際に、未宣言変数でないかチェックする用
  NODE *root;        // 宣言の存在する関数 (グローバルなら &(node[0]))
  char *root_name;   // 宣言の存在する場所の名前(関数名 or "GLOBAL")
  int   block;       // 宣言の存在するブロックの深さ (引数なら0, 関数内の宣言なら1)
  int   address;     // ローカル変数なら [ebp-address] グローバル変数なら [address]
} TABLE;

構造体メンバの意味はだいたい分かると思うので、非自明な部分だけ説明する。

sizeは、宣言ノードによって予約される資源が、メモリ上でどれだけの容量を占めるかbyte単位で表したものだ。 変数のサイズはint型なので4byteになる。 関数のサイズは機械語に変換した後でないと計算できないので、空欄になっている。

addressは、実行時にどのメモリアドレスに予約資源が格納されるかを表している。 実行時のメモリ配置は以下で与えられる。

f:id:kaitou_ryaku:20171212033457p:plain

メモリの0番地のあたりに関数を置いて、その後ろにグローバル変数を置いている。

  • 関数のアドレスは、機械語に変換した後でないと計算できないので空欄になっている。
  • グローバル変数のアドレスは、一番最後の関数の末尾アドレスからの差分で与えられる。

ローカル変数のアドレスはややこしいので、説明を後に回す。

ハッシュマップ

シンボルテーブルは「名前で検索」するための表と言ったが、文字列そのものを配列添字にするのは難しい。 代替案として、文字列を数値に変換するハッシュマップというアルゴリズムを用いる。

例えば、関数funcの情報をシンボルテーブルに登録したいとする。 まずfuncという文字列を、何らかのアルゴリズムで非負整数(ハッシュ値)に変換する。 その後シンボルテーブル(という名の構造体配列)のハッシュ値番目に、関数の情報を書き込めば良い。

関数の情報を取り出すときも、登録時と同様に、まず関数名をハッシュ値に変換する。 次にシンボルテーブルのハッシュ値番目を見れば、関数の情報がめでたくゲットできるという仕組み。

文字列をハッシュ値に変換する処理は、 two_node_to_hash関数 で実装した。

static int two_node_to_hash(NODE *var, const int kind, SOURCE s) {
  char *str = s.token[var  -> init].str;

  int hash = 0;
  for (int i=0; i<strlen(str); i++) {
    hash += str[i] * (((i+1)%2)*7 + ((i-1)%3)*11);
  }

  hash = hash*13 + kind * 23;
  if (hash < 0) hash = -hash;
  hash = hash % MAX_HASH_NUMBER;

  return hash;
}

文字列strが与えられたとき、str[i]によってi番目の文字を0から127までの数値に変換できる。 この性質を用いて文字列を数値に変換している。コード中の3とか7とか11に深い意味はない。 何も考えず適当に実装したのだが、まぁ動くからええやろ。

ところで、文字列strを登録しようとしてハッシュ値HASH(str)を計算した結果、その番号が使用済みの場合がある。 そういう時はHASH(str)+1にstrの情報を登録することにした。 でもそんなことしたら検索時に見つからなくなりそうだ。

これを回避する方法がある。 strを検索するときは、まずHASH(str)の番号のハッシュマップを見に行く。 そこに登録されている文字列がstrと同じなら、その情報を取得すればいい。 異なっていれば、HASH(str)+1を見に行く。 こういう手順でハッシュの衝突を解決できる。

グローバルな情報をシンボルテーブルに登録

次はグローバル変数と関数プロトタイプをシンボルテーブルに登録する仕組みを作る。

これはmake_global_table関数 で実装されている。

void make_global_table(TABLE *t, SOURCE s) {
  for (int i=0; i<MAX_HASH_NUMBER; i++) {
    t[i] = initialize_table();
  }

  int address = 0;
  fresh_tree(s);
  NODE *node = s.program -> down;
  while (node != NULL) {
    if      (node -> kind == V_DEC)     register_global_v( node, &address, t, s);
    else if (node -> kind == F_DEC)     register_function( node,           t, s);
    else if (node -> kind == PROTOTYPE) register_prototype(node,           t, s);
    node = node -> right;
  }
}

要するにPROGRAM直下の一層を左から右に走査している。 そして訪問した宣言ノードの種類に応じて、3種類の関数を呼び出している。

3つの関数は、シンボルテーブルtに宣言ノードの情報を登録するものだ。 例として register_global_v関数 の実装を見てみると

void register_global_v(NODE *node, int *address, TABLE *t, SOURCE s) {
  NODE *var = node -> down -> right;
  int hash = get_empty_hash(var, V_DEC, t, s);

  // 同名の変数は無いはず
  assert( search_hash_by_condition(var, s.program, V_DEC, t, s) < 0 );

  // 情報を登録
  t[hash].used        = true;
  t[hash].str         = s.token[var -> init].str;
  t[hash].node        = node;
  t[hash].kind        = V_DEC;
  t[hash].type        = 0;           // intなら0
  t[hash].size        = INT_SIZE;
  t[hash].token_index = var -> init; // 変数を参照する際に、未宣言変数でないかチェックする用
  t[hash].root        = s.program;   // 宣言の存在する関数 (グローバルなら &(node[0]))
  t[hash].root_name   = "GLOBAL";    // 宣言の存在する場所の名前
  t[hash].block       = 0;           // 宣言の存在するブロックの深さ
                                     //   グローバルなら0  引数なら1  関数内の宣言なら2
  t[hash].address     = *address;    // プログラム末尾からの差分

  *address += INT_SIZE;
}

まず最初に、変数名を表すノードvarを

NODE *var = node -> down -> right;

で取得している。 nodeがV_DECのノードであることを踏まえて下図を見て欲しい。

f:id:kaitou_ryaku:20171223181826p:plain:w300

V_DECから下に降りると、左端のTYPEのノードに着く。 さらに右へ進むと、VARIABLEのノードに到着する。 このノードに対応するトークンは (IDENTIFY, "g") なので、変数名の"g"が得られた。

次にget_empty_hash関数で変数名をハッシュ値に変換している。

そして同名の変数が既に登録されていないかsearch_hash_by_condition関数でチェックしている。 この関数はシンボルテーブル全体を走査し、varノードに一致する名前の変数が登録されていれば、そのハッシュ値を返す。 見つからなければ-1を返す。

これらの準備の後に、ハッシュテーブルに値を登録している。

関数宣言と関数プロトタイプの登録についてもざっくり説明しておくと、

  • 関数宣言用のregister_function関数では、まず同名の関数プロトタイプが既に登録されているか調べる。

    • もし登録されていなければ、関数の情報を普通に登録する。
    • もし登録済みなら、まず引数が整合するかチェックし、その後シンボルテーブルに登録済みの関数プロトタイプのノードを関数本体のノードに置き換える。

  • 関数プロトタイプ用のregister_prototype関数では、まず同名の関数が既に登録されているか調べる。

    • もし登録されていなければ、関数プロトタイプを普通に登録する。
    • もし登録済みなら、引数が整合するかチェックし、不整合ならエラーを返す。

以上の処理を実行すると、抽象構文木から関数プロトタイプとグローバル変数のノードは不要になる。 残るのは

f:id:kaitou_ryaku:20171223181842p:plain

あとは関数の内部を解析するだけだ。

関数ローカルなシンボルテーブル

func関数の中を解析しよう。

欲しいのは以下のテーブルだ。

名前 スコープ 種類 型 サイズ アドレス トークン HASH
"func" "GLOBAL" 関数 int - - 4 365
"g" "GLOBAL" 変数 int 4 - 1 287
"a" "func" 引数 int 4 8+ebp 12 475
"c" "func" 変数 int 4 -4+ebp 16 79

前節で登録したグローバル情報に加え、新たにfunc関数の引数aとローカル変数cが登録されている。

このテーブルが作成された時点で、抽象構文木は以下のように簡約される。

残されたVARIABLEノードを黄色で示した。 これらのノードから「名前」の情報を用いてシンボルテーブルにアクセスすることで、 変数や関数を参照できる。

関数ローカルな情報を登録する処理は make_local_table関数 で行っている。

void make_local_table( NODE *f_dec, TABLE *t, SOURCE s) {
  register_arguments(f_dec, t, s); // 引数の処理
  register_local_var(f_dec, t, s); // ローカル変数の処理
}

2つの関数が呼び出されているが、どちらも前節で解説したregister_global_v関数とほぼ同じ。 異なるのはアドレスに関する部分だ。

引数の登録と関数呼出

まず引数を処理する register_arguments関数 について、アドレスに関する部分だけを抜粋して見てみると

void register_arguments(NODE *f_dec, TABLE *t, SOURCE s) {
  NODE *v_dec = f_dec -> down -> right -> right;
  int address = 2*INT_SIZE; // INT_SIZEは4なので、初期値は8

  while (v_dec -> kind != FUNCTION) {
    t[hash].address = address; // 8, 12, 16, ...
    address += INT_SIZE;

    v_dec = v_dec -> right;
  }
}

これで

int FUNC(int a, int b, int c) {
  いろいろやる
}

というサンプルコードを処理すると、以下のシンボルテーブルができあがる。

変数名 TABLE構造体メンバのaddressの値
"a" 8
"b" 12
"c" 16

8,12,16の数字の意味がわかるだろうか？

たぶん意味分からんと思うので、 x86の関数呼出の記事を読み直して欲しい。

int a, int b, int cの3つを引数とする関数呼出をアセンブラで書くと

push cの値    ; 3番目の引数をスタックに詰む
push bの値    ; 2番目の引数をスタックに詰む
push aの値    ; 1番目の引数をスタックに詰む
call FUNC     ; 帰還するアドレスをメモしてFUNCにジャンプ
...           ; いずれここに帰還

FUNC:
push ebp      ; 呼出時のebpをメモ
mov  ebp, esp ; 計算前のespをメモ

いろいろやる
引数aの値は[ebp+8] で参照
引数aの値は[ebp+12]で参照
引数aの値は[ebp+16]で参照

leave         ; espを計算前に戻し、ebpを呼出時に戻す
ret           ; 帰還し、espを呼出時に戻す
  1. FUNCを呼び出す前に、c, b, aをpush
  2. 帰還するアドレスをpush
  3. 呼出時のebpをpush
  4. mov ebp, esp
  5. FUNCの内部処理開始

という順序で関数呼出を行う。 つまりebpの値と引数のアドレスの間には、帰還するアドレスと呼出時のebpの値が挟まっている。 これら2つのスタックをスキップして引数にアクセスするには

変数名 メモリアドレス 構造体メンバのaddressの値
"a" ebp+8 8
"b" ebp+12 12
"c" ebp+16 16

つまりTABLE構造体メンバのaddressの値は、ebpからの差分を与えているのだ。

ローカル変数とスタックフレーム

最後にローカル変数を処理する register_local_var関数 も見ておく。

さっきと同様にアドレスに関する部分だけを抜粋すると

void register_local_var(NODE *f_dec, TABLE *t, SOURCE s) {
  NODE *func = f_dec -> down;
  int address = -INT_SIZE; // 初期値は-4

  while (func != NULL) {
    if (func -> kind == V_DEC) {
      t[hash].address = address; // -4, -8, -12, ...
      address -= INT_SIZE;
    }

    func = func -> right;
  }
}

今回も、TABLE構造体メンバのaddressはebpからの差分を表している。

たとえば

int FUNC() {
  int a;
  int b;
  int c;
}

というコードから生成されるシンボルテーブルは以下のようになる。

変数名 メモリアドレス TABLE構造体メンバのaddressの値
"a" ebp-4 -4
"b" ebp-8 -8
"c" ebp-12 -12

これは、さっきの(引数処理の)アセンブラコードさえ理解できていれば、簡単に分かるはずだ。

アセンブラで考えると

call FUNC     ; 帰還するアドレスをメモしてFUNCにジャンプ
...           ; いずれここに帰還

FUNC:
push ebp      ; 呼出時のebpをメモ
mov  ebp, esp ; 計算前のespをメモ

sub esp, 0x10 ; ローカル変数の容量を確保
              ; 0xCでも良さそうだが、4byte単位で確保するルールらしい

いろいろやる
ローカル変数aは[ebp-4] で参照
ローカル変数bは[ebp-8] で参照
ローカル変数cは[ebp-12]で参照

leave         ; espを計算前に戻し、ebpを呼出時に戻す
ret           ; 帰還し、espを呼出時に戻す

重要なのは7行目の

sub esp, 0x10

の部分。 これはスタックをむりやり4個押し上げる操作に対応する。 そうしてできたスタックメモリの空いたスペースに、ローカル変数を3つ詰め込んでいる。

「スタックの押し上げは3個で十分じゃないか？」という指摘は、完全に正しい。 僕もよく知らないのだが、4byte単位で押し上げるのが良しとされているようだ。 もしローカル変数が5個以上なら、sub esp, 0x100とする必要がある。

関数が複数ある場合

今回のサンプルコードでは関数が1つしかなかった。 複数の関数が存在する場合は、シンボルテーブルの更新とコード生成を交互に行う必要がある。

  1. グローバルスコープの情報をシンボルテーブルに登録
  2. 関数Aの引数とローカル変数を解析してシンボルテーブルに登録
  3. 関数Aをニーモニックに変換
  4. 関数Aの引数とローカル変数をシンボルテーブルから削除
  5. 関数Bの引数とローカル変数を解析してシンボルテーブルに登録
  6. 関数Bをニーモニックに変換
  7. 関数Bの引数とローカル変数をシンボルテーブルに登録

以上でシンボルテーブルの説明は終了。 関数呼出の手続きが理解できていれば、難しいところは全くないはずだ。

明日はいよいよアセンブラのコード生成だ。胸が熱くなるな～