コマ4: if/else + 比較演算

int main() {
    int a;
    int b;
    a = 10;
    b = 3;
    if (a > b) {
        return a - b;
    } else {
        return b - a;
    }
}

この回で扱う範囲

対象にするプログラムは、main 関数内に以下の要素を含むものに限定する。

while、for、関数呼び出し、ポインタはまだ扱わない。 コマ3までは末尾の return を1個だけ扱った。 この回から、途中や if の枝に置いた return でも、共通エピローグへ移って関数を終了できる。

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 } { stmt } '}'

stmt        ::= expr_stmt
              | block
              | if_stmt
              | 'return' expr ';'
expr_stmt   ::= expr ';'         /* 空文 ; はコマ5 */
block       ::= '{' { stmt } '}'
if_stmt     ::= 'if' '(' expr ')' stmt [ 'else' stmt ]

expr        ::= assign_expr
assign_expr ::= unary_expr '=' assign_expr   /* 右結合 */
              | cond_expr
cond_expr   ::= binary_expr [ '?' expr ':' cond_expr ]   /* 右結合 */
binary_expr ::= unary_expr { bin_op unary_expr }
bin_op      ::= '*' | '/' | '%'  /* 論理 && || はコマ13 */
              | '+' | '-'
              | '<' | '>' | '<=' | '>='
              | '==' | '!='
unary_expr  ::= primary_expr
              | '-'  unary_expr
primary_expr ::= INT_LITERAL
               | IDENT
               | '(' expr ')'

AST を確認する

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

python3 scaffold/parse_viewer.py sessions/04_if_else/tests/target.c

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

int main() {
    int a;
    int b;
    a = 10;
    b = 3;
    if (a > b) {
        return a - b;
    } else {
        return b - a;
    }
}

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

(program
  (funcdef "main" :type int (params)
    (block (decl "a" :type int) (decl "b" :type int)
      (exprstmt
        (assign (var "a") (num 10)))
      (exprstmt
        (assign (var "b") (num 3)))
      (if
        (cond
          (lt (var "b") (var "a")))
        (then
          (block
            (return
              (sub (var "a") (var "b")))))
        (else
          (block
            (return
              (sub (var "b") (var "a")))))))))

注目すべき点は2つある。

1つ目。元のCコードの条件式は a > b だが、ASTでは (lt (var "b") (var "a")) として表されている。 Parser は > を < に、>= を <= に、それぞれ左右を入れ替えて変換する。 そのため、AST上では ND_GT や ND_GE は決して現れない。

2つ目。if ノードは次の3つのフィールドを持つ。

比較演算

この回では、比較演算も式として扱う。 比較演算の結果は、真なら 1、偽なら 0 とする。

Parser が返す比較演算ノードは次の通り。

ND_GT や ND_GE は登場しないため、これらに対応するコードは不要である。

比較演算のコード生成

二項演算の共通パターンにより、比較命令を出す直前には次の状態になっている。

比較演算は次のように生成する。

seqz (set if equal to zero)、snez (set if not equal to zero)、slt (set if less than)、xori (xor immediate) はRV64の命令である。

たとえば、a < b のASTは (lt (var "a") (var "b")) であり、次のように生成される。

  # a1 = a, a0 = b の状態
  slt a0, a1, a0

a1 < a0 が成り立てば a0 = 1、成り立たなければ a0 = 0 となる。

条件分岐の考え方

Cでは、if の条件式の値が 0 なら偽、0 以外なら真として扱う。

if (cond) {
    文
}

このコードは、次のような流れに変換できる。

cond を計算する
もし cond の結果が 0 なら Lend に飛ぶ
文を実行する
Lend:

RV64では、beqz a0, label を使う。

beqz a0, .L1

これは、a0 が 0 なら .L1 にジャンプする、という意味である。 cond の計算結果は a0 に入っているため、beqz a0, Lend で「偽なら飛ばす」という動作になる。

ラベル生成

分岐の飛び先には、一意なアセンブリラベルが必要になる。

new_label() は、呼ばれるたびに異なる名前のラベルを返すメソッドである。

def new_label(self) -> str:
    self._label_counter += 1
    return f".L{self._label_counter}"

インスタンス変数 self._label_counter は __init__ で 0 初期化される。

ラベルの一意性は、この self._label_counter がプログラム全体で単調に増え続けることで保証される。 .L で始まる名前は慣用的にローカルラベルと呼ばれ、シンボル表に残らない（アセンブラや リンカが外部から参照する対象にしない）扱いを受けるが、名前の一意性そのものはアセンブラが 自動で保証してくれるわけではない。

if の生成パターン

if (cond) {
    文
}

これは、次のような命令の並びとして生成する。

# cond を codegen
beqz a0, Lend
# 文
Lend:

条件が偽なら beqz で Lend に飛び、文は実行されない。

if/else の生成パターン

if (cond) {
    then文
} else {
    else文
}

この場合は、then 側の実行後に else 側を飛ばす必要がある。

# cond を codegen
beqz a0, Lelse
# then
j Lend
Lelse:
# else
Lend:

こうしないと、then 側の実行後に else 側にも突入してしまう。

偽のときは beqz でラベルへ飛ぶ。 if/else では、then 側の最後に j Lend を置いて else 側を飛び越す。

else if の扱い

else if という専用ノードはない。 Parser は、else の中にさらに if が入っているものとして扱う。

たとえば、次のコードを考える。

if (score >= 90) {
    return 4;
} else if (score >= 70) {
    return 3;
} else {
    return 1;
}

ASTでは、else の中にもう一つの if が入る。

(if
  (cond ...)
  (then ...)
  (else
    (if
      (cond ...)
      (then ...)
      (else ...))))

else_ が指すノードの kind が ND_IF であるかどうかにかかわらず、gen_stmt(stmt.else_) を再帰的に呼べば、else if も自然に処理できる。 else_ が None になるまで、再帰が続く。

return と共通エピローグ

コマ3までは、return 文が関数の末尾にしか現れなかったため、return の後に直接エピローグを置けばよかった。

しかし、コマ4からは if の中などに return が現れる。

if (a > b) {
    return a;
}
return b;

この場合、if の中の return で関数をその場で終了しなければならない。 そのため、return 文では、戻り値を a0 に入れた後、関数末尾のエピローグラベルヘジャンプする。

return式を codegen する
j Lreturn

gen_func() では、関数ごとに _ret_label を作り、エピローグの直前に置く。

.Lreturn:
  ld s0, ...
  ld ra, ...
  addi sp, sp, ...
  ret

共通エピローグラベルを使うことで、関数内のどこに return があっても正しく関数を抜けられるようになる。

三項演算子: 値を持つ分岐（式と文の違い）

if/else と同じ回で、三項演算子 ?: も実装する。

int main() {
    int a;
    int b;
    a = 3;
    b = 8;
    return a > b ? a : b;
}

ここで「式と文の違い」がはっきり見える。

コード生成はどちらも同じ分岐で書ける。違いは、?: では選ばれた枝の 評価結果が a0 に残ることだけである。

def codegen_Cond(self, node):
    label_else = self.new_label()
    label_end = self.new_label()
    self.codegen(node.cond)
    self.emit(f'  beqz a0, {label_else}')
    self.codegen(node.then)      # 値が a0 に残る
    self.emit(f'  j {label_end}')
    self.emit(f'{label_else}:')
    self.codegen(node.else_)     # 値が a0 に残る
    self.emit(f'{label_end}:')

gen_stmt_If とほぼ同じ形だが、gen_stmt ではなく codegen （式のコード生成）の一員である点に注意する。AST 上は (ternary cond then else) というノードになる。

gen_stmt に追加する処理

コマ3 で実装した gen_stmt() に、さらに文の種類を追加する。

編集するファイル

• mycc.py

importlib でコマ3 の Codegen03 を継承した Codegen04 に、以下の機能を追加する。

実装手順

1. スケルトンの Codegen04 が Codegen03 を importlib で継承していることを確認する。ラベル採番の new_label() と、左右を評価して a1/a0 に載せる _binary(lhs, rhs)、codegen() / gen_stmt() のディスパッチはあらかじめ書かれている
2. _reset_func_state(node) を実装する（super()._reset_func_state(node) で frame_size を受け、self._ret_label = self.new_label() でこの関数専用の return ラベルを作る。どのテストでも必要）
3. _emit_func_epilogue(frame_size) を実装する（エピローグ本体の前に self._ret_label のラベル行を出す。その後の s0/ra 復元は親クラスの hook を呼んでよい）
4. gen_stmt_Return(node) を上書きする（式を codegen した後、その場で ret せず j <self._ret_label> へ飛ばす）
5. gen_stmt_Block(node) を実装する（node.stmts を先頭から順に self.gen_stmt() する）
6. codegen_Eq / codegen_Ne / codegen_Lt / codegen_Le を実装する（いずれも self._binary(node.lhs, node.rhs) の後に sub+seqz / sub+snez / slt a0, a1, a0 / slt a0, a0, a1+xori a0, a0, 1）
7. gen_stmt_If(node) を実装する（node.cond を codegen し、beqz と new_label() で then / else / end の制御フローを作る。node.else_ が None のときは then を抜けた直後に else ラベルだけを置く）
8. codegen_Cond(node) を実装する（if/else と同じ分岐を作り、選ばれた枝の値を a0 に残す。文ではなく式なので値が残るのがポイント）

tests/

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

テスト

python3 scaffold/test_runner.py sessions/04_if_else

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

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

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

qemu-riscv64 ./out
echo $?

注意

Parser は > と >= を正規化するため、ND_GT や ND_GE は AST上に現れない。 これらのノードに対応するコードは不要である。

ND_IF の cond は、比較演算に限らず、任意の式を取れる。 Cでは、0 が偽、0 以外が真である。

この言語で宣言を書けるのはファイルスコープと関数本体の先頭だけで、 if やブロックの中には文しか書けない（language_spec.md の「宣言」節）。 入れ子ブロックは新しいスコープも作らないので、nested_block.c の if の中の y は 関数先頭で宣言した y そのものである。 宣言の収集はコマ3 の collect_decls() が関数本体の先頭を見るだけで済み、 if や while の中まで降りる必要はない。

生成したアセンブリの分岐が期待どおりに飛ぶか確認したいときは、学習ツールの実行表示 に貼り付ける。

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

この資料の原稿を見る