コマ3: 変数・代入・シンボルテーブル

int main() {
    int a;
    int b;
    int c;
    a = 3;
    b = 5;
    c = a + b;
    return c;
}

この回で扱う範囲

対象にするプログラムは、次の形に限定する。

int main() {
    int 変数名;
    ...
    式;
    ...
    return 式;
}

先頭の変数宣言と式文の後に、末尾の return 式; を1個だけ置く。 共通の Parser は途中の return や空本体も受理するが、この回の実行対象は上の形に限定する。 途中の return で共通エピローグへ移る処理はコマ4で実装する。

扱う機能は以下の通り。

この回では、すべての変数を 8 バイト整数として扱う。 int は本来 4 バイトだが、前半では実装を単純にするため、スタック上では各変数に 8 バイトを割り当てる。

if、while、関数呼び出し、ポインタはまだ扱わない。

scalar_type ::= 'int'            /* ポインタはコマ7、char はコマ8 */
obj_type    ::= scalar_type

program       ::= func_def        /* ユーザー定義関数はコマ6 */
var_decl      ::= obj_type IDENT ';'

func_def    ::= 'int' 'main' '(' ')' func_body   /* 一般の関数定義はコマ6 */
func_body   ::= '{' { var_decl } { expr_stmt } 'return' expr ';' '}'

stmt        ::= expr_stmt
              | 'return' expr ';'
expr_stmt   ::= expr ';'         /* 空文 ; はコマ5 */

expr        ::= assign_expr
assign_expr ::= unary_expr '=' assign_expr   /* 右結合 */
              | binary_expr      /* 条件 ? : はコマ4 */
binary_expr ::= unary_expr { bin_op unary_expr }
bin_op      ::= '*' | '/' | '%'  /* 関係・等値はコマ4、論理はコマ13 */
              | '+' | '-'
unary_expr  ::= primary_expr
              | '-'  unary_expr
primary_expr ::= INT_LITERAL
               | IDENT
               | '(' expr ')'

AST を確認する

まず、変数を含むプログラムがどのような AST になるか確認する。

python3 scaffold/parse_viewer.py sessions/03_variables/tests/target.c

このプログラムの内容は次の通り。

int main() {
    int a;
    int b;
    int c;
    a = 3;
    b = 5;
    c = a + b;
    return c;
}

実行すると、次のようなS式が表示される。

(program
  (funcdef "main" :type int (params)
    (block (decl "a" :type int) (decl "b" :type int) (decl "c" :type int)
      (exprstmt
        (assign (var "a") (num 3)))
      (exprstmt
        (assign (var "b") (num 5)))
      (exprstmt
        (assign (var "c")
          (add (var "a") (var "b"))))
      (return (var "c")))))

新しく登場するノードは次の通り。

return c; の c も (var "c") として表される。 a = 3; の左側の a も、右辺で値を読む a も、AST上は同じ ND_VAR である。

式と文

ここからは、「式」と「文」を区別する必要がある。

式とは、評価すると結果の値が得られるものである。 得られた値は、別の計算に使い回せる。

例:

1 + 2
a
a + b * 3
a = 10

たとえば、1 + 2 は評価すると 3 になる。 その結果は、さらに別の式の一部として使える。

(1 + 2) * 4

この式では、まず 1 + 2 の結果 3 が得られ、その値を使って 3 * 4 を計算する。

変数参照 a も式である。 評価すると、変数 a に保存されている値が得られる。

代入 a = 10 も式である。 代入は a に 10 を書き込む処理を行い、さらに式全体の結果として 10 という値を持つ。 そのため、Cでは代入式の結果をさらに使うことができる。

b = (a = 10);

この場合、a = 10 の結果は 10 なので、b にも 10 が代入される。

一方、文とは、プログラムの中で実行される処理の単位である。 文そのものは、次の計算に使い回せる結果の値を返さない。

例:

int a;
a = 10;
return a;

a = 10 は式だが、; を付けた a = 10; は文である。 このように、式に ; を付けて文にしたものを「式文」という。

式文は、式を評価して副作用を起こすために使う。 ここでいう副作用とは、変数への書き込みなど、値を返す以外にプログラムの状態を変える処理のことである。

a = 10;

この文では、代入式 a = 10 の結果の値 10 は、それ以上使われない。 重要なのは、変数 a に 10 が書き込まれるという副作用である。

この回で出てくる文は次の通り。

一方、次のようなものは式である。

codegen と gen_stmt

式と文を区別すると、コード生成のメソッドも分けやすくなる。

self.codegen(node) は、式を処理するメソッドである。 式には結果の値があるため、self.codegen(node) が終わった時点で、その値が a0 に入っている、という約束にする。

self.gen_stmt(node) は、文を処理するメソッドである。 文は「処理の単位」であり、次に使い回す値を返す必要はない。 そのため、self.gen_stmt(node) には「結果を a0 に残す」という約束は置かない。 ただし、return 文だけは例外で、関数の戻り値を a0 に入れる必要がある。

これらのメソッドはすべて Codegen03 クラスのインスタンスメソッドである。 それぞれ match node.kind で処理を分けた後、対応する handler method（例: gen_stmt_Return）を呼ぶ。 スケルトンではディスパッチ部分はあらかじめ書かれている。

たとえば、a = 10; はAST上では次のように表される。

(exprstmt
  (assign (var "a") (num 10)))

外側の exprstmt は文なので gen_stmt() が処理する。 内側の assign は式なので codegen() が処理する。

return a; はAST上では次のように表される。

(return (var "a"))

外側の return は文なので gen_stmt() が処理する。 内側の (var "a") は式なので codegen() が処理する。

変数はどこに置くか

コンパイル後のプログラムでは、Python の辞書のような場所に変数を置けるわけではない。 実行時には、変数の値をメモリ上に保存する必要がある。

この回では、ローカル変数をスタック上に置く。

Codegen03 には、次のインスタンス変数が用意されている。

class Codegen03(prev.Codegen02):
    def __init__(self) -> None:
        super().__init__()
        self._locals: dict[str, int] = {}
        self._stack_offset: int = 0

self._locals は、変数名からスタック上の位置への対応表である（関数ごとにリセットされる）。

例:

{
    "a": -24,
    "b": -32,
    "c": -40,
}

この例では、変数 a は s0 - 24、変数 b は s0 - 32、変数 c は s0 - 40 に置かれる。

スタックフレーム

gen_func() は、関数ごとに _reset_func_state() を呼んで必要なフレームサイズを計算する。

addi sp, sp, -(frame_size + 16)
sd ra, frame_size + 8(sp)
sd s0, frame_size(sp)
addi s0, sp, frame_size + 16

この後、s0 は関数に入る前の sp と同じ位置を指す。 ローカル変数は s0 から負の方向に置く。

ra と保存した s0 の下にローカル変数が順に並ぶ。 1個目の変数 a は s0 - 24、2個目の b は s0 - 32、3個目の c は s0 - 40 に置かれる。

コマ2 では _reset_func_state() が 0 を返し、フレームサイズが固定だった。 コマ3 では _reset_func_state() を実装し、宣言された変数の数に応じて可変にする。 プロローグ・エピローグは、コマ2で frame_size を使って実装したものをそのまま使う。 固定の16バイトで実装していた場合は、両方を変数領域も含む形へ直すこと。 変数領域を確保しないと、ローカル変数と式の一時値が同じ場所に置かれてしまう。

宣言収集 — 関数本体は Block ノード

フレームサイズを決めるには、関数に入る前に「この関数がローカル変数を何個使うか」を 知っておく必要がある。そのために、コード生成の前に一度だけ AST を見て回り、 Decl を見つけるたびに alloc_local() する。この走査を collect_decls() と呼ぶ。

gen_func() が受け取る FuncDef ノードの body は、文の並びではなく 1 つの Block ノードである（先ほどの S 式の (block (decl "a") ... (return (var "c")))）。 そこで _reset_func_state() は、node.body をそのまま collect_decls() に渡す。

1. self._locals をクリアする
2. self._stack_offset を 0 にする
3. self.collect_decls(node.body) で宣言を収集する
4. align_to(self._stack_offset, 16) を frame_size として返す

collect_decls() は match node.kind で処理を分ける。

'Block' を開くのは、関数本体そのものが Block だからである。 1 段だけ開けば、関数本体の先頭に並んだ Decl が全部見える。

そこから先へ降りる必要はない。この言語で宣言を書けるのはファイルスコープと 関数本体の先頭だけで、if や while の中には文しか書けないからである （language_spec.md の「宣言」節）。 collect_decls_Block() はこの 1 段の展開だけなので、スケルトンに書いてある。

入れ子のブロックは新しいスコープを作らないので、関数内のローカル変数は すべて関数全体のフレームへ一律に確保してよい。

alloc_local の役割

self.alloc_local(name) は、新しいローカル変数にスタック上の位置を割り当てるメソッドである。 スケルトンにあらかじめ書かれているが、割り当て方を知らないとオフセットの意味が読めないので、 方針をここに示す。

方針は次の通り。

たとえば、a, b, c を順に割り当てると、次のようになる。

オフセットは s0 からの相対位置である。

rvalue と lvalue

変数を扱うときは、「値がほしい」のか「書き込み先のアドレスがほしい」のかを区別する必要がある。

たとえば、次の文を考える。

a = b + 1;

右辺の b は、変数 b に入っている値を読む必要がある。 一方、左辺の a は、値を読むのではなく、代入先として a のアドレスが必要である。

この区別のために、次の2つのメソッドを使い分ける。

この回の codegen_lval() は、'Var' だけ対応する最小形でよい。 codegen() と codegen_lval() を分ける設計はここが出発点で、以降ずっと使う （conventions.md の「守ってほしい設計」節）。 コマ7 で *p を代入先にできるよう 'Deref' の分岐を足して拡張するが、 'Var' の分岐と codegen_Assign() はこの回で書いたものをそのまま引き継ぐ。

変数参照の生成

'Var' を値として読む場合は、次の2段階で処理する。

1. self.codegen_lval(node) で変数のアドレスを a0 に入れる
2. ld a0, 0(a0) で、そのアドレスから値を読み込む

たとえば、a が s0 - 24 にあるなら、次のような命令になる。

addi a0, s0, -24
ld a0, 0(a0)

1行目で a のアドレスを作り、2行目でそのアドレスに保存されている値を読む。

代入の生成

a = 3; のような代入では、左辺のアドレスと右辺の値の両方が必要になる。

生成パターンは次の通り。

1. 左辺のアドレスを self.codegen_lval() で計算する
   -> a0 に左辺のアドレスが入る

2. 左辺のアドレスをスタックに退避する

3. 右辺を self.codegen() で計算する
   -> a0 に右辺の値が入る

4. 退避していた左辺のアドレスを a1 に戻す

5. sd a0, 0(a1) で、右辺の値を左辺のアドレスへ保存する

代入後、a0 には右辺の値を残しておく。 Cでは、代入式 a = 3 自体の値は 3 である。

gen_stmt の役割

self.gen_stmt(node) は、文ノードを受け取り、match node.kind で種類ごとに handler を呼ぶ。

'Block' の処理（body.stmts を順に gen_stmt()）はコマ2 の _emit_func_body がすでに行っている。

スケルトンでは dispatcher 部分があらかじめ書かれており、handler だけが TODO になっている。

編集するファイル

• mycc.py

コマ2 の Codegen02 を importlib で継承した Codegen03 を実装する。

コマ2 で埋めた TODO（_codegen_binary_value、codegen_Neg、codegen_Add 〜 codegen_Mod、 gen_stmt_Return、_emit_func_prologue / _emit_func_body / _emit_func_epilogue）は、 importlib の継承でそのまま引き継がれる。この回で書き直すものは無い。

次のものはスケルトンにあらかじめ書かれている（実装対象ではない）。

• align_to()、alloc_local()、lookup_var()
• codegen() / gen_stmt() / codegen_lval() のディスパッチ
• collect_decls() のディスパッチと collect_decls_Block()（関数本体の Block を 1 段開くだけの処理）

実装手順

1. スケルトンの Codegen03 が Codegen02 を importlib で継承していることを確認する（あらかじめ書かれている）
2. _reset_func_state(node) を実装する（self._locals と self._stack_offset を初期化し、self.collect_decls(node.body) を呼び、self.align_to(self._stack_offset, 16) を返す。どのテストでも必要）
3. collect_decls_Decl(node) を実装する（提供済みの self.alloc_local(node.name) を呼ぶだけ）
4. gen_stmt_Decl(node) を実装する（領域確保は手順3 で済んでいるので何も出力しない）
5. gen_stmt_ExprStmt(node) を実装する（node.operand が None でなければ self.codegen() に渡す）
6. codegen_lval_Var(node) を実装する（self.lookup_var(node.name, node.line) で s0 からのオフセットを引き、addi a0, s0, <offset> でアドレスを a0 に作る）
7. codegen_Var(node) を実装する（self.codegen_lval(node) でアドレスを作ってから ld a0, 0(a0)）
8. codegen_Assign(node) を実装する（node.lhs を codegen_lval → self._push_a0() → node.rhs を codegen → self._pop_into('a1') → sd a0, 0(a1)。sp は直接動かさない）

tests/

上から順に通していくと、どこで詰まっているかが1機能ぶんに絞られる。 「通る目安」は実装手順の番号である。

代入の前にローカル変数の宣言が必要である。宣言と同時に初期値を書くことはできず、初期値は代入文で設定する。

テスト

python3 scaffold/test_runner.py sessions/03_variables

tests/target.c がコンパイルでき、終了コード 8 になれば基本形は成功。

eight_locals.c は8変数のスロットが重ならず、必要なフレームを確保できるかを見る。 局所領域は8変数×8バイトで元から16の倍数なので、アラインメント調整の検査にはならない。 調整を確認するときは、1変数の single.c の生成アセンブリを読む。

python3 sessions/03_variables/mycc.py sessions/03_variables/tests/single.c > single.s

プロローグで addi sp, sp, -32 が出ることを確認する。 局所変数8バイトと退避領域16バイトの計24バイトを、16の倍数である32へ切り上げるためである。 qemuで動くだけでは、呼び出し規約のアラインメントを証明できない。

minimal.c はローカル変数が 0 個でも正しく動くかを見るテストである。

個別に動かす場合は、次のようにする。

python3 sessions/03_variables/mycc.py sessions/03_variables/tests/target.c \
  | riscv64-linux-gnu-gcc -x assembler -static - -o out

qemu-riscv64 ./out
echo $?

注意

この回では、同じ関数内で同じ名前の変数を2回宣言するケースは扱わない。

コマ3 ではローカル変数の数に応じて可変フレームを使う。 _reset_func_state() で collect_decls(node.body) を呼び、align_to(self._stack_offset, 16) で 16 バイト境界に調整する。 ここで作った _reset_func_state() と collect_decls() の形は、以降のコマでもそのまま使う。

生成したアセンブリのフレームサイズやオフセットを1命令ずつ追いたいときは、学習ツールの実行表示 に貼り付ける。

この回の完成形に相当する OCaml 版参考実装が ../../workbook/ocaml/README.md にある。完成相当の実装なので、まず自分の実装方針を検討してから確認すること。

この資料の原稿を見る