学習内容

・スタックマシンへのコンパイル
・x86-64におけるスタックマシンの実現方法

今回やること

1.抽象構文木をコンパイルするにはどうするかを考える
2.レジスタマシンでどう実現するかを考える

1.抽象構文木をコンパイルするにはどうするかを考える

例えば下記のような場合

“+"
├── B   
└── A

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

で達成される。

具体的に 2 + 3 * 4のときは

“+"
├── "*"
│   ├── 4
│   └── 3
└── 2

1左の部分木をコンパイルしてPUSH 2される
2右の部分木をコンパイルしようとして、再帰的に部分木の左側がコンパイルされてPUSH 3される
3部分木の右側がコンパイルされてPUSH 4される
4再帰元に戻る、MULが出力される
5再起元に戻り、ADDが出力される

このようにすると抽象構文木をアセンブリにおとしていける

2.レジスタマシンでどう実現するかを考える

レジスタマシンであるx86-64でどのように実現するか？
→スタックの先頭を指すレジスタを用意してスタックポインタとして扱い、仮想的なスタックマシンとする。C言語ではRSPをスタックマシンのトップ（=プリングルスの一番上）にしている

push 1
push 2

→メモリに値を登録する。
X86-64ではスタックは高いアドレスから低いアドレスに向かって積み上げるように設計されているため、例えば

0x0FF8           2
0x1000           1

のように積み上がっていく

// 左辺と右辺をRAXとRDIにポップして足す
pop rdi
pop rax
add rax, rdi

→メモリを直接足す命令はないので、レジスタにロードして、その後加算する

// 足した結果をスタックにプッシュ
push rax

→スタックポインタが指す位置として指定するため戻す

前節との差分

PUSH 1
PUSH 2
ADD

→ADDのところで実際に計算をするためにロードして、その結果をスタックにプッシュし直すところが違う

具体的に 3 + 1 * 2をx86-64形式で書いてみると

// 3 をスタックにプッシュ
push 3

// 1 * 2 を計算して結果をスタックにプッシュ
push 1
push 2

pop rdi
pop rax
mul rax, rdi
push rax

// スタックトップの 2 つの値を足す
// つまり 3 + 1 * 2 を計算する
pop rdi
pop rax
add rax, rdi   ; rax = rax + rdi (3 + 2)
push rax       ; 最終結果 (5) をスタックにプッシュ

ここまでの流れをC言語で表すと下記のようになる

// nodeが1 * 2だとするとする
void gen(Node *node) {
  if (node->kind == ND_NUM) {
    printf("  push %d\n", node->val);
    return;
  } // 数字だったらpushする

  gen(node->lhs); // 左部分木を処理。この場合1　←ここが再帰的
  gen(node->rhs); // 右部分木を処理。この場合2

  printf("  pop rdi\n");
  printf("  pop rax\n”); // 取り出される

  switch (node->kind) {
  case ND_ADD:
    printf("  add rax, rdi\n");
    break;
  case ND_SUB:
    printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
    printf("  imul rax, rdi\n");
    break;
  case ND_DIV:
    printf("  cqo\n");
    printf("  idiv rdi\n");
    break;
  }

  printf("  push rax\n”); // 結果をプッシュし直す
}

所感

・仮想スタックマシンのロジックを考える→実際にコードにしてみるというながれがおもしろい