これは PSI（東京大学工学部システム創成学科知能社会システムコース） Advent Calendar 2018 - Qiita の12/23の投稿です
Rui Ueyamaさんという方が開発した「9cc」というCコンパイラがあります。
github.com
約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;
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++;
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());
return v;
}
次に、引数のためのスタック領域を確保する情報を保持しながら中間言語を生成し、
static void gen_args(Vector *nodes) {
if (nodes->len == 0)
return;
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");
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");
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
push r13
push r14
push r15
mov [rbp-8], rdi
mov [rbp-16], rsi
mov r10, rbp
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
mov rsi, r11
push r10
push r11
mov rax, 0
call add
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"};
static char *argregs8[] = {"dil", "sil", "dl", "cl", "r8b", "r9b"};
static char *argregs32[] = {"edi", "esi", "edx", "ecx", "r8d", "r9d"};
...
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) {
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;
}
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(',');
vec_push(params, param_declaration());
}
おわりに
最後まで読んでくださりありがとうございます。
これからもコンパイラ周りを勉強して発信していきたいと思います。
また、この9ccというコンパイラですが、最初の十数commitなら作者であるRui Ueyamaさん本人が解説を書いています。
低レイヤを知りたい人のための Cコンパイラ作成入門
読者の皆さんもコンパイラ書きましょう！
