9cc全266commitを追いかけた。〜関数引数の扱い方について〜
これは PSI（東京大学工学部システム創成学科知能社会システムコース） Advent Calendar 2018 - Qiita の12/23の投稿です
Rui Ueyamaさんという方が開発した「9cc」というCコンパイラがあります。
約1ヶ月かけて、この266commit全てを追いかけました。
巷ではこれをRustで書き直したりと積極的な人が多く見受けられますが、僕にはそんなことはできないので、100%写経しながらコンパイラというものがどうやって作られているのかを知っていきました。
今回はその中で、関数の引数がどのように処理されているかに焦点を当てて紹介したいと思います。
目次
そもそも一般的に関数引数はどう処理される？
9ccの初期の段階ではどう処理してる？
9ccの最後の方ではどう処理してる？
そもそも一般的に関数引数はどう処理される？
昔々、関数引数は全てスタック上で引き渡されていました。
しかし実際には、6つ以上の引数を持つ関数はほとんど存在しな（いらし）く、不要なメモリアクセスが生じています。
レジスタならば算術演算命令によって直接アクセスできるため高速であり、最初のk個（k = 4 or 6）はレジスタで渡し、残りの引数はメモリで渡す、という方法が採用されています。
（関数fが別の関数gを呼び出すときに、レジスタで渡した関数fの引数が関数gの引数で上書きされないよう、結局関数fの引数はスタックフレームに退避しなきゃいけなくなるとか、レジスタで渡したはいいものの、その引数のアドレスを要求されたときにどうするんじゃいとか、別の問題が発生したりするのですが、これらの問題にはそれぞれ対処法があって、それはまた後日...）
9ccの初期の段階ではどう処理してる？
関数呼び出しを初めて導入したのは、
22commit目 Add funcion call ~ 25commit目 Add function parametersです。
ざっくり説明すると、字句解析を行なった後に、構文解析器において引数を関数に付属する配列として保持し、
static Node *function() { Node *node = calloc(1, sizeof(Node)); node->ty = ND_FUNC; // ←プログラムをFunctionの集まりとみなす。 node->args = new_vec(); Token *t = tokens->data[pos]; if (t->ty != TK_IDENT) error("function name expected, but got %s", t->input); node->name = t->name; pos++; // 引数を関数Nodeに追加していく expect('('); if (!consume(')')) { vec_push(node->args, term()); while (consume(',')) vec_push(node->args, term()); expect(')'); } // 関数の本体を解析する expect('{'); node->body = compound_stmt(); return node; }; Vector *parse(Vector *tokens_) { tokens = tokens_; pos = 0; Vector *v = new_vec(); while (((Token *)tokens->data[pos])->ty != TK_EOF) vec_push(v, function()); // ←プログラムをFunctionの集まりとみなす。 return v; }
次に、引数のためのスタック領域を確保する情報を保持しながら中間言語を生成し、
static void gen_args(Vector *nodes) { if (nodes->len == 0) return; // 引数ごとにIR_SAVE_ARGSという中間言語を生成 add(IR_SAVE_ARGS, nodes->len, -1); for (int i = 0; i < nodes->len; i++) { Node *node = nodes->data[i]; if (node->ty != ND_IDENT) error("bad parameter"); // 今はintにしか対応していないため、引数１つあたりにスタックポインタは8だけずらせば良い stacksize += 8; map_put(vars, node->name, (void *)(intptr_t)stacksize); } } Vector *gen_ir(Vector *nodes) { Vector *v = new_vec(); for (int i = 0; i < nodes->len; i++) { Node *node = nodes->data[i]; assert(node->ty == ND_FUNC); code = new_vec(); vars = new_map(); regno = 1; stacksize = 0; // 後にこのスタックサイズ分だけスタックポインタをずらす gen_args(node->args); gen_stmt(node->body); Function *fn = malloc(sizeof(Function)); fn->name = node->name; fn->stacksize = stacksize; fn->ir = code; vec_push(v, fn); } return v; }
最後にアセンブリを生成するときに引数をレジスタで渡している。（x86）
// 引数を渡すためのレジスタ。（引数渡し以外にもいろいろなことに使う） const char *argreg[] = {"rdi", "rsi", "rdx", "rcx", "r8", "r9"}; ... case IR_CALL: { for (int i = 0; i < ir->nargs; i++) // 関数呼び出しの時、引数の数だけレジスタに入れる printf(" mov %s, %s\n", argreg[i], regs[ir->args[i]]); printf(" push r10\n"); printf(" push r11\n"); printf(" mov rax, 0\n"); // raxは関数の戻り値を入れる printf(" call %s\n", ir->name); printf(" pop r11\n"); printf(" pop r10\n"); printf(" mov %s, rax\n", regs[ir->lhs]); break; } case IR_SAVE_ARGS: for (int i = 0; i < ir->lhs; i++) // 引数ごとにベースポインタ（フレームポインタ）の位置からずらしてレジスタから引数を取得 printf(" mov [rbp-%d], %s\n", (i + 1) * 8, argreg[i]); break;
試しに、簡単な関数呼び出しのアセンブリを生成してみよう。
$ ./9cc 'add(a,b) { return a+b; } main() { return add(1,2); }'
.intel_syntax noprefix .global add add: push rbp // ベースポインタの位置をスタックに保存 mov rbp, rsp // 今のスタックポインタをベースポインタに sub rsp, 16 // スタックサイズ分だけスタックポインタを移動 push r12 // r12 ~ r15は値を保存したいので退避 push r13 push r14 push r15 mov [rbp-8], rdi // rdi(１つ目の引数)の値をベースポインタから8だけずらしたアドレスにストア mov [rbp-16], rsi // rsi(２つ目の引数)の値をベースポインタから16だけずらしたアドレスにストア mov r10, rbp // r10, r11は計算途中の値を入れるレジスタ的な sub r10, 8 mov r10, [r10] mov r11, rbp sub r11, 16 mov r11, [r11] add r10, r11 mov rax, r10 jmp .Lend0 .Lend0: pop r15 pop r14 pop r13 pop r12 mov rsp, rbp pop rbp ret .global main main: push rbp mov rbp, rsp sub rsp, 0 push r12 push r13 push r14 push r15 mov r10, 1 mov r11, 2 mov rdi, r10 // rdi, rsiレジスタに引数を入れる mov rsi, r11 push r10 push r11 mov rax, 0 call add // rdi, rsiに引数を入れた状態でcallで関数を呼ぶ pop r11 pop r10 mov rbx, rax mov rax, rbx jmp .Lend1 .Lend1: pop r15 pop r14 pop r13 pop r12 mov rsp, rbp pop rbp ret
ここまで見てわかる通り、
const char *argreg[] = {"rdi", "rsi", "rdx", "rcx", "r8", "r9"};
と手動でレジスタを割り当てているため、6つを超えた引数を与えると、
$ ./9cc 'add(a,b,c,d,e,f,g) { return a+b+c+d+e+f+g; } main() { return add(1,2,3,4,5,6,7); }'
*** stack smashing detected ***: ./9cc terminated
Aborted (core dumped)
となってしまいますね。つまりk個を超えた引数をどうするかはまだ考えていない、しかし大半の関数は対応できるため、初期の段階ではこれでいいというわけです。
9ccの最後の方ではどう処理してる？
いきなり266commit目まで飛んじゃいます。
x86のコードを生成する部分を抜粋すると以下のようになっています。
static char *argregs[] = {"rdi", "rsi", "rdx", "rcx", "r8", "r9"}; // 64ビット static char *argregs8[] = {"dil", "sil", "dl", "cl", "r8b", "r9b"}; // 8ビット static char *argregs32[] = {"edi", "esi", "edx", "ecx", "r8d", "r9d"}; // 32ビット ... static char *argreg(int r, int size) { if (size == 1) return argregs8[r]; if (size == 4) return argregs32[r]; assert(size == 8); return argregs[r]; } ... case IR_CALL: for (int i = 0; i < ir->nargs; i++) emit("mov %s, %s", argregs[i], regs[ir->args[i]->rn]); emit("push r10"); emit("push r11"); emit("mov rax, 0"); emit("call %s", ir->name); emit("pop r11"); emit("pop r10"); emit("mov %s, rax", regs[r0]); break; case IR_STORE_ARG: emit("mov [rbp%d], %s", ir->var->offset, argreg(ir->imm, ir->size)); break;
9ccの最後の方では、int以外にもvoidやcharを扱えるようになっています。
それに伴い、関数引数として割り当てるレジスタも型に合わせて変化しています。
しかし、割り当てるレジスタは変わらず上限があるので、上限以上の引数を持つ関数は先ほど同様エラーになりますね。
ところで、話は少しそれますが、初期はintのみだったために簡単だったスタックサイズの計算はどうなっているでしょう。
以下からわかる通り、関数のローカル変数を足し合わせた分のスタックサイズ（下でいうoff）を確保しています。同時に、「〇〇番目の引数だから...」とアクセスするのではなく、varにoffsetを覚えさせて引数やローカル変数にアクセスしているのがわかります。
void emit_code(Function *fn) { // Assign an offset from RBP to each local variable. int off = 0; for (int i = 0; i < fn->lvars->len; i++) { Var *var = fn->lvars->data[i]; off += var->ty->size; off = roundup(off, var->ty->align); var->offset = -off; } // Emit assembly char *ret = format(".Lend%d", nlabel++); p(".text"); p(".global %s", fn->name); p("%s:", fn->name); emit("push rbp"); emit("mov rbp, rsp"); emit("sub rsp, %d", roundup(off, 16)); emit("push r12"); emit("push r13"); emit("push r14"); emit("push r15");
パーサを見れば、このローカル変数たちに関数引数も含まれていることがわかります。
static Var *param_declaration() { Type *ty = decl_specifiers(); Node *node = declarator(ty); ty = node->ty; if (ty->ty == ARY) ty = ptr_to(ty->ary_of); return add_lvar(ty, node->name); } ... static void toplevel() { ... Vector *params = new_vec(); while (!consume(')')) { if (params->len > 0) expect(','); // lvarに引数を追加 vec_push(params, param_declaration()); }
おわりに
最後まで読んでくださりありがとうございます。
これからもコンパイラ周りを勉強して発信していきたいと思います。
また、この9ccというコンパイラですが、最初の十数commitなら作者であるRui Ueyamaさん本人が解説を書いています。
読者の皆さんもコンパイラ書きましょう！
