Zenn
🐍

Pythonのコンパイラを作りたい #3 - 数値演算と型システム

2025/02/08に公開
Python
LLVM
compiler
tech

こんにちは。前回の記事（「#2 - Python AST から LLVM IR を生成するまでの概略」）では、Python の抽象構文木 (AST) をどのように LLVM IR へ変換して .ll ファイルを生成しているかを紹介しました。

今回のテーマは、数値演算と型システム です。
Python では int が自動的に大きな数に拡張されたり、float や Decimal など多彩な数値型が存在します。しかし、本プロジェクト pyc ではまず i32 を中心に扱う設計を採用しています。「Python はオブジェクト指向で何でもオブジェクト扱いなのに、なぜ i32？」と思われるかもしれませんが、これは実装を単純化して高速化を狙うために割り切った形です。

以下では、この i32 アプローチを選んだ理由や処理の流れを詳しく見ていきます。

リポジトリはこちら:
https://github.com/t3tra-dev/pyc

1. なぜ i32 に絞るのか？

1-1. オーバーヘッドの問題

当初は、CPython と同様に「すべてをオブジェクト (PyInt など) として扱い、メソッドテーブルを通して + 演算を呼び出す」という形を模倣しようとしました。
具体的には、仮に x + y があるときに「x.__add__(y) を呼ぶ」ような実装です。こうすると Python 的には柔軟な拡張が可能ですが、一方で LLVM IR ベースのコンパイラとして見ると、とても大きなオーバーヘッドが発生します。

  • 各オブジェクトが「型情報」「メソッドテーブル」「参照カウント or GC情報」などを持つ
  • 演算のたびに型判定や動的ディスパッチ (object.__add__) を行う
  • 小さな加算一つでも複数回の関数呼び出しや分岐を伴う

こうした要因から、CPython よりも更に3倍以上遅くなる ことが判明しました。

ここのコミットで動的な型付けやラップされた PyInt を排除するよう改修を行なっています。

https://github.com/t3tra-dev/pyc/commit/66e2831a9892c1e09b60c9d0e891df3543392429

特に、今回のように C 言語で簡易実装したランタイムでは、インタプリタレベルより低い部分の制御をすべて手書きする必要があり、結果として複雑な処理が増えてしまったのです。

1-2. ネイティブ i32 の手軽さ

そこで、「型アノテーション int が付いているものはネイティブの i32 にする」という割り切りを導入しました。
これは「Python の int = 任意精度、という規約を無視している」かもしれませんが、初期段階では性能と実装の簡易化を最優先にしています(勿論、今後の拡張の余地は残っています)。

例えば、以下のような Python 関数があるとします。

def add(x: int, y: int) -> int:
    return x + y

これを i32 前提でコンパイルすると、LLVM IR 上はかなりシンプルになります。

define i32 @add(i32 %x, i32 %y) {
entry:
  %t0 = add i32 %x, %y
  ret i32 %t0
}

このとき、Python オブジェクトとしての __add__ は使わず、単なる add i32 命令で済むため、高速であり、なおかつコード生成も比較的 straightforward です。

1-3. 64bit 整数や他の型への拡張

現在は（実験段階として）32bit 整数 (i32) しか扱っていませんが、本来であれば 64bit 整数 (i64) も簡単にサポート可能です。実際、Python における int は任意精度が保証されていますから、最終的には「 BigInt を使う」か「ある閾値以上で大きな構造に切り替える」などの実装が必要になるでしょう。
しかし、これらをすべて正しく再現しようとすると、途端に実装が爆発的に複雑化し、パフォーマンスも下がる恐れがあります。そこで現在の pyc では「まずは i32 のみ対応」という割り切りのもと、小さく始めている段階です。
将来的には、例えば「デフォルトは i32 だが、オーバーフローを検出したら任意精度整数オブジェクトに切り替える」ようなハイブリッド方式も考えられますが、それもまた実装コストと速度のトレードオフになります。

2. 型アノテーションとコンパイラの対応づけ

2-1. Python 3.5 以降の型アノテーション

Python 3.5 以降、関数定義などに型アノテーションが書けるようになりました。この機能を利用すると、例えば次のように Python コードを書けます。

def multiply(a: int, b: int) -> int:
    return a * b

pyc では、このアノテーションを見て「int という型が指定されている = i32 で扱う」という単純なマッピングを行っています。
逆に言えば、アノテーションがまったく無い場合は「型がわからない」ため、現状では動的型として ptr 扱い (オブジェクト) にフォールバックするか、ビルドエラーとするか、といった制限が生じています。

2-2. 「型がない」Pythonとの折り合い

Python は本来ダイナミック型言語であり、変数に型アノテーションを書かなくてもいいし、ランタイム中に型が変わることも許容しています。
しかし、その世界観をそのまま AOT コンパイラで再現しようとすると、どうしても大きなコストがかかる (CPythonレベルの複雑さをそっくり再現する必要がある) ため、pyc の目標としては「静的型に近い書き方」をすることで高速化と簡易実装を両立しようとしています。

  • 「型をつけた部分はネイティブ i32 / ptr / etc. で最適化」
  • 「型をつけない部分は動的型扱い (将来的にはラップオブジェクトにするかエラーにするか？」)

といった方針が、現在の手探り段階での落としどころです。

2-3. 開発初期の苦労: アノテーションのパース

ast.parse() で抽象構文木を取得した際、FunctionDef ノードなどの .returns, .args.args[].annotation といった属性に注釈が含まれています。そこから annotation.id が 'int' なのか 'str' なのかを取り出す作業が必要です。
こうした型情報を Visitor で適切に捕捉し、シンボルテーブルに「引数 x は i32」「引数 y は i32」と登録しておくと、後で演算処理や関数呼び出し時に「左辺・右辺が i32 だから add i32 でいいな」と即座に判断できるようになります。

3. BinOp ノード (加算・減算・乗除など) の処理例

3-1. ast.BinOp とは

Python の AST では、1 + 2 のような二項演算が ast.BinOp(left=Constant(1), op=Add(), right=Constant(2)) の形で表されます。
node.op には Add(), Sub(), Mult(), Div() などのクラスオブジェクトが入り、node.left / node.right が左辺と右辺のノードを持ちます。

3-2. Visitor のフロー

pyc では、以下のような流れで BinOp を処理します。

  1. visit_BinOp(node: ast.BinOp) を呼ぶ
  2. 左辺ノード (node.left) を再帰的に訪問し、返ってきた TypedValue を left_val とする
  3. 右辺ノード (node.right) も同様に訪問し、right_val とする
  4. node.op が何に当たるか (Add, Sub, Mult, etc.) を調べる
  5. 「left_val.type_ と right_val.type_ がどちらも i32 であるか」をチェック
    • i32 同士ならネイティブ演算を生成 (add i32, sub i32, mul i32, etc.)
    • そうでない場合はオブジェクト扱いに落とす（未実装ならエラー）
  6. IRBuilder に emit(f"{tmp} = add i32 {left_val.llvm_value}, {right_val.llvm_value}") のような命令を出力
  7. TypedValue(tmp, "i32") を返す

3-3. 具体例

def example():
    return 1 + 2

この単純な関数をコンパイルすると、実際には以下のような LLVM IR が生成されるイメージです。

define i32 @example() {
entry:
  ; 1 と 2 は一時変数にロードするまでもなく直接即値でもよいが、簡単にするため下記のように書く場合もある

  ; left(1)
  ; right(2)
  %t1 = add i32 1, 2

  ret i32 %t1
}

もし「return a * b - c」のような複合演算があっても、Visitor は再帰的にノードを巡り、BinOp を分解して順序どおりに命令列を生成していきます。
また、将来的に float や double を扱う場合は、このロジックを拡張して fadd, fmul などの命令を発行できるようにするだけで済むはずです。

4. i32 アプローチのメリット・デメリット

4-1. メリット

  1. 実装がシンプル
    すべてを Python オブジェクトとして扱う場合に比べて、コード生成のステップが圧倒的に少なくなります。加算なら単に add i32 と書くだけで済むのは大きな利点です。

  2. 高速
    ネイティブな整数演算を LLVM の最適化が丸ごと活用できるため、インタプリタ方式より大幅に高速になる可能性が高いです。CPU レジスタ上で直接演算する形に近いので、オーバーヘッドが最小限に抑えられます。

  3. 既存ツールとの相性が良い
    Clang や llc の最適化パイプラインで、基本的な整数演算については既にかなり洗練された最適化が行われます。デバッグもしやすく、アセンブリを読めばすぐに理解できます。

4-2. デメリット

  1. Python らしさの損失
    Python の int は任意精度であり、オーバーフローしないことが売りですが、この方式では 32bit の範囲外で普通にオーバーフローします。(1 << 33) のような計算は正しく扱えません。

  2. 動的型との相性問題
    変数が途中で文字列に化けるなど、Python の動的型付けの特徴をそのまま表現することは難しいです。型アノテーションに頼らないコードを書かれると、うまく最適化できないか、ビルドエラーの可能性があります。

  3. バイナリ互換性・拡張性
    i32 という固定長整数に限定するため、将来的に i64 や big int が必要になったときには大きな改修が必要です。段階的にハイブリッド方式を入れるにしても、型判定や切り替えロジックが増えて複雑化しがちです。

5. まとめ & 次回の話

今回は、Python の int を i32 で扱う方針を採用する理由や、その具体的な実装フローについて紹介しました。

  • すべてをオブジェクト扱いにすると CPython より遅くなる場合があり、割り切って i32 を使う設計にしている
  • 型アノテーションを活用することで、コンパイラが「ここは i32 演算を使っていいのだな」と判断し、ネイティブ命令を生成できる
  • BinOp ノードを Visitor パターンで処理する際に、「i32 同士なら add i32 を書く」というロジックを仕込んでいる

という流れです。

次回は、「関数定義とスコープ (簡易的な静的型付き関数) の扱い」を取り上げます。
def foo(x: int) -> int: といった関数定義をどうやって define i32 @foo(i32) の LLVM IR に落とし込むのか、また 変数スコープやシンボルテーブルをどのように管理しているのかを掘り下げて紹介する予定です。
引き続き、コンパイル時の型情報を使って「Pythonらしいけど静的型っぽい」世界をどこまでカバーできるか、試行錯誤しているポイントをお届けしたいと思います。

次回:
https://zenn.dev/t3tra/articles/be3bb28a5775d4

Discussion