2f62e5267a1c2874dcfa674cf8654e0cb3f189d6

コミットコメントが仰々しい感じがする。

test.sh

とりあえずここを見れば次に実装することがわかる。コードを見る限り、そこまで追加機能はないようだが……？

int pos = 0;
enum {
  ND_NUM = 256,     // Number literal
};
typedef struct Node {
  int ty;           // Node type
  struct Node *lhs; // left-hand side
  struct Node *rhs; // right-hand side
  int val;          // Number literal
} Node;

posはプログラムの読み込み位置かな？NodeはTokenとどう違うんだろう？

Node *new_node(int op, Node *lhs, Node *rhs)
Node *new_node_num(int val)

んーまだよくわからない。

Node *number()

数字のtokenから数字のnodeを作っている？

Node *expr()

再帰的なNodeを作っているようだ。

char *regs[] = {"rdi", "rsi", "r10", "r11", "r12", "r13", "r14", "r15", NULL};

んーアセンブラの変数(レジスタ)の名前列？これは予約語なのかなあ、単純に数字が増加しているだけではないし、よくわからない。アセンブラを少し学ぶ必要がありそうだ。

https://qiita.com/edo_m18/items/83c63cd69f119d0b9831

によるとrdiはシステムコールに使われるレジスタ。でも他はそうではないっぽい。

http://milkpot.sakura.ne.jp/note/x86.html

によると汎用レジスタの一覧にすべて収まる。

おそらく、システムコールを使うときにはrdiは意味を持つが、そうでなければ汎用的に使えるレジスタ、ということかな？レジスタは、とりあえず8個使うようだ。

char *gen(Node *node)

nodeを再帰的にたどって、node毎に利用するレジスタを割り当てるっぽい。そのうえで、node->tyからアセンブラの足し算引き算コードを作り出す。レジスタはnodeに割り当てられたものを使う。

  printf("  mov rax, %s\n", gen(node));

これはつまりトップレベルに割り当てられたレジスタを終了ステータスレジスタに割り当てているので、最終的にこのレジスタに全ての計算結果が返ってきているはずということか！ coolだ。

ここまで写経してきて、ふと思い立って1+2+3+4+5+6+7+8の出力アセンブラを見比べてみた。

before

.intel_syntax noprefix
.global main
main:
  mov rax, 1
  add rax, 2
  add rax, 3
  add rax, 4
  add rax, 5
  add rax, 6
  add rax, 7
  add rax, 8
  ret

after

.intel_syntax noprefix
.global main
main:
  mov rdi, 1
  mov rsi, 2
  add rdi, rsi
  mov r10, 3
  add rdi, r10
  mov r11, 4
  add rdi, r11
  mov r12, 5
  add rdi, r12
  mov r13, 6
  add rdi, r13
  mov r14, 7
  add rdi, r14
  mov r15, 8
  add rdi, r15
  mov rax, rdi
  ret

んー違いはあるけど恩恵はまだなさそうな感じがする。次行ってみよう。

https://github.com/rui314/9cc/commit/dca0fdb71df98d8500170ff8178eaac0c8f9edaa

test.sh

try 153 '1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17'

んーこれまたhttps://github.com/rui314/9cc/commit/916237396164ae25557b62bf0d1ca9d9cf8c2070からのメリットが見えない感じ。 https://github.com/rui314/9cc/commit/2f62e5267a1c2874dcfa674cf8654e0cb3f189d6から予想できるのは、おそらくレジスタを有効に使って計算が長くても対応できるようにしそうなこと。

// Intermediate representation
enum {
  IR_IMM,
  IR_MOV,
  IR_RETURN,
  IR_KILL,
  IR_NOP,
};
typedef struct {
  int op;
  int lhs;
  int rhs;
} IR;

名前からして"内部表現"……？token -> node -> irという変化だろうか？ mrubyでの経験に当てはめると、MOVで変数をレジスタに割り当てたり、RETURNで関数の返り値を決めれるようにしたりという感じかな？ IMMはimmediateで即値を表す？KILLは分からない。NOPは何もしない命令っぽい。

データ構造からして、命令と対象と引数でアセンブラと言うか機械命令語っぽい感じ？

IR *ins[1000];
int inp;
int regno;

Intermediateが複数のsでinsかな？これもtokens[1000]と同じく雑に1000個空間を用意しているっぽい。同じくinsのポインタpでinp、regnoはレジスタナンバーというところかな？

int gen_ir_sub(Node *node)

名前からしてirを作るサブ関数っぽい。関数の中も見ていく。

  if (node->ty == ND_NUM) {
    int r = regno++;
    ins[inp++] = new_ir(IR_IMM, r, node->val);
    return r;
  }

レジスタ番号regnoとnodeの値node->valをIMM命令としてinsに登録してポインタinpを進める。多分レジスタrにnode->valを割り当てるんだろうと思う。割り当てたレジスタ番号を返すのはなんでだろう？あとでアセンブラとして書き出すのかな？

assert(node->ty == '+' || node->ty == '-');

Cのassertって個人的には好きで、バグ検知しつつここから先のコードの制限というか説明になっていて良い。 Rubyでいうとraise unless expr だと思ってる。

  int lhs = gen_ir_sub(node->lhs);
  int rhs = gen_ir_sub(node->rhs);
  ins[inp++] = new_ir(node->ty, lhs, rhs);
  ins[inp++] = new_ir(IR_KILL, rhs, 0);

node->tyは'+'とか'-'とかが入っている。これもirの命令として流用するようだ。 gen_ir_subを再帰的に使っている。たしかnode自体が再帰的にツリー状になっていたはず。返り値はレジスタ番号だったので、lhsもrhsもレジスタ番号だろう。足し算引き算の左右の値をirで纏めて、おそらく後でアセンブラに変換するんだろう。ここでKILL命令。おそらく再帰の終わりを表している？まだわからない。

int gen_ir(Node *node) {
  int r = gen_ir_sub(node);
  ins[inp++] = new_ir(IR_RETURN, r, 0);
}

これまでのgen_ir_subと違うのは、最後にRETURN命令をつけていることだけ。おそらくこれまで再帰的に処理してきた全結果が渡ってきたレジスタ番号を、関数の返り値として設定するんだろう。

char *regs[] = {"rdi", "rsi", "r10", "r11", "r12", "r13", "r14", "r15"};
bool used[8];
int reg_map[1000];

regsは前回と変わらない。 usedとreg_mapから察するに、レジスタ番号それぞれを、使ってるor使ってないで管理するためのものなんだろう。 reg_map[1000]はinsとかに1:1で対応するんだろうか？

int alloc(int ir_reg)

mallocやallocaを連想させる名前。未割り当てのレジスタを返してほしい関数かな？引数はレジスタ番号？中身も見ていく。

  if (reg_map[ir_reg] != -1) {
    int r = reg_map[ir_reg];
    assert(used[r]);
    return r;
  }

if文からir_regは0〜999の数字なんだろう。-1はまだ未登場の値。未使用を表すのかな？ assert文から察するにused=trueのレジスタ番号rを返すっぽい。used=trueでいいのか？

  for (int i = 0; i < sizeof(regs) / sizeof(*regs); i++) {
    if (used[i])
      continue;
    used[i] = true;
    reg_map[ir_reg] = i;
    return i;
  }

regsは8つのレジスタだった。これをループで回す。条件はregs[i]でもいい気はする。もしくはusedで8って決め打ちしちゃってるしi < 8とか……。まあわかりやすさを重視した結果かな？ used=trueなら飛ばして次へ。used=falseならused=trueにしてreg_map[ir_reg]に使っているregsのindexを割り当てて番号を返す。さっき出てきたreg_map[ir_reg]には-1は割り当てられえない。あとで初期化するのかな？それともfree的な関数が出るのかな？ともかくこの関数が返すのは、regsのindex番号のようだ。 0〜999のなにかしらの番号ir_regが与えられた時、使えるregsのindexを返す。このindexからアセンブラを書き出すんだろう。

void kill(int r) {
  assert(used[r]);
  used[r] = false;
}

usedフラグをoffにするだけ。レジスタの再利用のためかな。

void alloc_regs()

長いので見ていこう。allocとどう違うんだ。

  for (int i = 0; i < inp; i++) {
    IR *ir = ins[i];

inpはinsのindexだった。これまで進んだins全てでループしているっぽい。

    switch (ir->op) {

命令毎になんかする。

    case IR_IMM:
      ir->lhs = alloc(ir->lhs);
      break;

allocはとにかく使えるregsのindexを返す関数(という予想)だった。 IR_IMMはgen_ir_subで出てきた。lhsはregnoというインクリメントする謎の値だった。この時点では使えるかどうかわからないから使えるレジスタindexを割り当てているんだろう。ここから、おそらくalloc_regs関数はalloc関数のirレベルで適用するものと予想。

    case IR_MOV:
    case '+':
    case '-':
      ir->lhs = alloc(ir->lhs);
      ir->rhs = alloc(ir->rhs);
      break;

IR_MONと'+'と'-'が一緒になっているのに面食らったが、おそらく全て左右の2つのレジスタを使う命令なんだろう。

    case IR_RETURN:
      kill(reg_map[ir->lhs]);
      break;

IR_RETURNは関数の返り値と予想している。killは使ってないフラグを設定するんだった。関数の返り値は再利用すると思われるんだがkillするからには再利用はしない。予想は外れていることになる。これまでのcommitからアセンブラの最後のプロセスの終了ステータスを設定するやつか？

    case IR_KILL:
      kill(reg_map[ir->lhs]);
      ir->op = IR_NOP;
      break;

IR_KILLはgen_ir_subの最後に登場していた。例えば足し算では左と右のレジスタの値を足して左のレジスタに入れる。そうすると右側のレジスタは再利用可能になる。ということかな。

void gen_x86()

なまえからしてアセンブラを吐きそうな感じだ(勘)。またまた見ていく。

  for (int i = 0; i < inp; i++) {
    IR *ir = ins[i];

alloc_regsと同じくinsのループのようだ。

switch (ir->op) {

ちなみに実行順はmain関数を見るにgen_ir->alloc_regs->gen_x86のようだから予想は合っている。ここでの命令は全てalloc_regsが終わったあとの世界のようだ。

    case IR_IMM:
      printf("  mov %s, %d\n", regs[ir->lhs], ir->rhs);
      break;

IR_IMMは使えるレジスタ左に即値のnode-valが右に入っていた。これでmov reg1 123のように出力されるんだろう。

    case IR_MOV:
      printf("  mov %s, %s\n", regs[ir->lhs], regs[ir->rhs]);
      break;

単純に右から左へのコピー。変数とかを使えるようにするための布石か？ならこのテストコードではこの命令自体がいらないような……。作るところもないし。

    case IR_RETURN:
      printf("  mov rax, %s\n", regs[ir->lhs]);
      printf("  ret\n");
      break;

これは予想通り最終的な結果をプロセスの終了ステータスに割り当てている。

    case '+':
      printf("  add %s, %s\n", regs[ir->lhs], regs[ir->rhs]);
      break;
    case '-':
      printf("  sub %s, %s\n", regs[ir->lhs], regs[ir->rhs]);
      break;

左右に使えるレジスタ番号が入っているので、ここで使えることが保証される。

    case IR_NOP:
      break;

IR_KILLとかが変化してIR_NOPになったものだろう。何もしないことが便利なときもある。

int main(int argc, char **argv)

一応main関数も見ていこう。

  for (int i = 0; i < sizeof(reg_map) / sizeof(*reg_map); i++)
    reg_map[i] = -1;

やはりreg_mapはallocで予想したとおり-1で初期化されていた。

  tokenize(argv[1]);
  Node* node = expr();

  gen_ir(node);
  alloc_regs();

  printf(".intel_syntax noprefix\n");
  printf(".global main\n");
  printf("main:\n");
  gen_x86();

やはりtoken -> node -> irと変換していき、レジスタ割当を行って、アセンブラを吐いておわり。

token = 空白など余計な文字を除いた文字の列

node = 構文的な計算順序の組み立て

ir = このプログラミング言語のVM的なもの

ということかな。

んー、やはりテストコードからは、実装が先の世界に行き過ぎてる感がある。

アセンブラはこうなった

.intel_syntax noprefix
.global main
main:
  mov rdi, 1
  mov rsi, 2
  add rdi, rsi
  mov rsi, 3
  add rdi, rsi
  mov rsi, 4
  add rdi, rsi
  mov rsi, 5
  add rdi, rsi
  mov rsi, 6
  add rdi, rsi
  mov rsi, 7
  add rdi, rsi
  mov rsi, 8
  add rdi, rsi
  mov rsi, 9
  add rdi, rsi
  mov rsi, 10
  add rdi, rsi
  mov rsi, 11
  add rdi, rsi
  mov rsi, 12
  add rdi, rsi
  mov rsi, 13
  add rdi, rsi
  mov rsi, 14
  add rdi, rsi
  mov rsi, 15
  add rdi, rsi
  mov rsi, 16
  add rdi, rsi
  mov rsi, 17
  add rdi, rsi
  mov rax, rdi
  ret

スペクトラム

rui312/9ccを写経する-その2

https://github.com/rui314/9cc/commit/2f62e5267a1c2874dcfa674cf8654e0cb3f189d6

test.sh

before

after

https://github.com/rui314/9cc/commit/dca0fdb71df98d8500170ff8178eaac0c8f9edaa

test.sh