🐍
Pythonのコンパイラを作りたい #2 - Python AST から LLVM IR を生成するまでの概略

2025/02/07に公開
2件
こんにちは。前回の記事（「#1 - 開発の背景と概要」) では、Python コードを LLVM IR にコンパイルするプロジェクトの全体像や開発のモチベーションなどを紹介しました。
今回は、「Python AST から LLVM IR を生成するまでの概略」 についてご説明します。

具体的には、次のようなステップを追います。
Python のソースコードを ast モジュールでパースして抽象構文木 (AST) を得る
AST の各ノードを巡回 (Visitor パターン) して「どのように LLVM IR に変換するか」を決める
LLVM IR をテキストとして組み立て、.ll ファイルとして出力
Clang や llc などのコンパイラツールチェーンを利用して最終的なバイナリに変換
本記事では特に 1 〜 4 の部分を中心に、サンプルコードを交えつつ解説していきます。
リポジトリはこちら:
https://github.com/t3tra-dev/pyc

 1. PythonのASTを取得する
 1-1. ast モジュールによるパースPython には標準ライブラリとして ast モジュールが用意されており、ast.parse(code: str) を呼ぶだけでソースコードを抽象構文木 (AST) に変換できます。これは Python インタプリタがコードを解釈するときに内部で行っている処理を、私たちが直接扱えるようにしたものです。たとえば、次のような source.py ファイルがあったとします。
# source.py
def add(x: int, y: int) -> int:
    return x + y

print(add(3, 5))
このファイルを ast.parse() でパースすると、Module, FunctionDef, Call などのノードが階層構造として得られます。
Python インタプリタ上で以下のように実行してみましょう:
import ast

with open("source.py") as f:
    code = f.read()

tree = ast.parse(code)
print(ast.dump(tree, indent=2))
出力は (やや冗長ですが) 下記のような構造になるはずです。
Module(
  body=[
    FunctionDef(
      name='add',
      args=...,
      body=[...],
      decorator_list=[],
      returns=...,
      ...
    ),
    Expr(
      value=Call(
        func=Name(id='print', ctx=Load()),
        args=[
          Call(
            func=Name(id='add', ctx=Load()),
            args=[Constant(value=3), Constant(value=5)],
            keywords=[]
          )
        ],
        keywords=[]
      )
    )
  ],
  type_ignores=[]
)
ここでは最上位が Module オブジェクトになっており、その下に FunctionDef (関数定義) や Expr (式文) などの要素が並んでいるのがわかります。さらに Expr の中には Call ノードがあり、Call の中には Name(id='print') や Call(func=Name(id='add', ...)) がネストされています。このように AST はツリー構造 (再帰的な入れ子) でコードの構文を表現しているわけです。

 1-2. なぜ AST が重要なのかコンパイラの流れとしては、
ソースコード (文字列) をパースして AST を構築する
AST を解析・変換して LLVM IR などの中間表現を生成する
中間表現から最終的な機械語やバイナリを吐き出す
というステップが定番です。
AST を使うメリットとしては、「文法要素ごとに綺麗にノードが分かれているので、処理を分割しやすい」という点が挙げられます。Python でもこの仕組みが標準ライブラリで提供されているため、独自パーサを書かずに済むのは大きな恩恵です。

 2. VisitorパターンでASTを巡回する
 2-1. AST ノードをどのように扱うかAST の各ノード (例: FunctionDef, Return, Call, BinOp, Assign, Name など) は、それぞれ Python の文法要素を表しています。

例えば、

FunctionDef(name='add', ...) は関数定義を意味する

Call(func=Name(id='print', ...)) は print(...) の呼び出しを意味する

BinOp(left=..., op=Add(), right=...) は二項演算(加算)を意味する
といった具合です。
このように、ノードの種類ごとに必要な処理 (実際には IR をどう書き出すか) が異なります。そこで「ノードの型ごとに対応する処理を実装する」という目的で、Visitor パターンを使うケースがとても多いです。

 2-2. Visitor パターンとは？Visitor パターンとは、「処理対象のオブジェクト構造と、その処理ロジックを分離する」ための設計パターンです。抽象的には「visit_Xxx メソッドをノードの型ごとに用意しておき、ノードを再帰的にたどる」という方法になります。
実際の実装イメージ:
class MyVisitor:
    def visit(self, node):
        node_type = type(node).__name__
        method_name = f"visit_{node_type}"
        if hasattr(self, method_name):
            return getattr(self, method_name)(node)
        else:
            # 未対応ノードなどの処理
            raise NotImplementedError(...)

    def visit_FunctionDef(self, node: ast.FunctionDef):
        # 関数定義ノード用の処理
        ...

    def visit_Return(self, node: ast.Return):
        # return文ノード用の処理
        ...

    def visit_Call(self, node: ast.Call):
        # 関数呼び出しノード用の処理
        ...
こうすることで、visit(node) を呼ぶだけで node の型に合わせたメソッドが自動的に呼ばれ、結果としてすべてのノードを適切に処理できるようになります。

 2-3. 数値リテラルと加算の極めて単純な例例えば、以下のようなごく単純な Python コードがあったとします。
def example():
    return 1 + 2

example という関数定義ノード (FunctionDef)
その中の Return(value=BinOp(left=Constant(1), op=Add(), right=Constant(2))) というノード
これを IR に落とし込むなら、「1 と 2 をそれぞれレジスタにロードし、add i32 命令を出力して、最後に ret i32 する」程度のイメージになります。

Visitor パターンを使うことで、visit_BinOp() 内に「左オペランドの値を取り出す」「右オペランドの値を取り出す」「add i32 left, right を書く」というロジックをまとめられ、加算演算がどこに現れても同じ処理を適用できるわけです。

 3. IRBuilder でテキストを組み立てる
 3-1. なぜ IRBuilder が必要なのかPython の AST から LLVM IR を生成する際には、最終的に LLVM IR のテキスト ( .ll ファイル ) を出力する必要があります。

ここで単に文字列操作を都度行うのも良いのですが、複雑になってくると管理が面倒になる恐れがあります。そこで pyc では「テキストの断片 (命令) を蓄積していき、最後に一括で出力する」クラスとして IRBuilder を用意しています。

 3-2. IRBuilder のイメージVisitor がノードを処理する中で、
self.builder.emit(f"  {tmp_var} = add i32 {left}, {right}")
のように emit() メソッドを呼び出し、命令文を1行ずつ追加していきます。最終的に全ノードの処理が終わると、IRBuilder には LLVM IR を構成する命令が全部揃っているわけです。
また、文字列だけでなく、「現在の一時変数カウンタは何番目か」「ラベルを何番生成したか」「グローバル文字列をどう埋め込むか」などの管理も IRBuilder にやらせると、コード生成がシンプルになります。

たとえば次のような機能をまとめるケースが多いです:

get_temp_name() : %t0, %t1, %t2 のような一時変数名を連番で発行

get_label() : label0, label1 といったジャンプ先ラベルの連番管理

add_global_string("Hello!") : 文字列をグローバル領域に登録し、 @.str.0 などのシンボル名を返す
こうした仕組みを作っておけば、Visitor の各メソッドは「AST ノードをどう変換するか」というロジックのみに専念でき、出力フォーマットの煩雑さから解放されるというメリットがあります。

 3-3. print("Hello!") を例にたとえば print("Hello!") を IR に落とし込みたいとき、次のように考えます。
文字列リテラル "Hello!" をグローバル領域に格納しておく

create_string 関数で文字列オブジェクト (String*) を作る呼び出しを生成 (call ptr @create_string(ptr @.str.0) など)
生成されたポインタを引数にして call void @print(ptr %tmp) を呼び出す
pyc の場合、print はランタイム側で void print(String* s) として定義しておきます。LLVM IR 上では declare void @print(ptr) という宣言を加えて呼び出し可能にしています。

Visitor が ast.Call(func=Name("print"), ...) を見つけたら、「あ、これは組み込みの print 呼び出しだな」と判断し、上記のような IR コードを IRBuilder に emit していくわけです。

 4. 実際に .ll ファイルを生成してみる
 4-1. コマンドラインでの実行ここまでの仕組みを組み合わせて、python -m pyc --emit-llvm source.py というコマンドを実行すると、次のような処理が行われます。
source.py を読み込んで ast.parse() する
Visitor パターンを用いて AST を再帰的にたどり、対応する LLVM IR 命令を IRBuilder に書き込む
完成した IR を .ll ファイルとして書き出す
例えば、source.py.ll というファイルが生成され、そこには以下のように @.str.0 や call void @print(...) といった命令が記述されているはずです。
@.str.0 = private unnamed_addr constant [7 x i8] c"Hello!\00", align 1

; ========== External runtime declarations ==========
declare void @print(ptr)

define i32 @main(i32 %argc, i8** %argv) {
entry:
  %t0 = call ptr @create_string(ptr @.str.0)
  call void @print(ptr %t0)
  ret i32 0
}
このように IR のテキストを眺めると、「文字列を作ってから print 関数を呼んでる」ことが明確にわかります。実際のプロジェクト pyc ではもっと多くのノード (関数定義、リスト操作、ディクショナリ操作など) に対応しており、それらがすべてこのような形で IR に変換されるというわけです。

 4-2. 出力された IR の確認LLVM IR は慣れないと独特な書式ですが、基本的な構造を把握してしまえば難しくありません。関数定義が define i32 @main(...) { ... } の形で書かれることや、二項演算が add i32, mul i32, 関数呼び出しが call ... になることなどを順に見ていくと、だんだん読めるようになります。

 5. Clang や llc で最終バイナリに
 5-1. .ll ファイルを機械語へ.ll ファイルは LLVM IR のテキスト形式なので、これを最終的に実行ファイルにするには、Clang や llc + ld といったツールチェーンを使います。

たとえば Clang を使う場合は:
clang -O2 source.py.ll runtime.o -o source
ここで runtime.o は、プロジェクト pyc 内にある C 言語のランタイムをあらかじめ make して得られたオブジェクトファイルです。具体的には PyInt, PyList, PyDict, create_string, print などの実装が含まれています。

これをリンクすることで、IR 中にある call void @print(ptr) などが C ランタイムの実装 (print(String*)) と結びついて正しく動作するようになるわけです。

 5-2. LLVM の最適化を活用する-O2, -O3 などのフラグを指定すれば、通常の C/C++ と同じように LLVM の強力な最適化が適用されます。Python コードから生成した IR であっても、ループ展開や定数伝搬などの最適化が効く場合は勝手にやってくれるのが嬉しいポイントです。

また、ターゲットを変えれば WebAssembly 用の .wasm を作ることも可能で、今後 pyc を使ってブラウザ上で Python コードを動かすことも期待できます。

 6. まとめ & 次回の話今回は、Python ソースを AST で解析し、Visitor パターンを使って LLVM IR を生成するまでの大まかな流れを解説しました。

大枠としては、

ast.parse() でツリー構造を得る
Visitor パターンでノードを巡回し、対応する LLVM IR 命令を IRBuilder に書き込む
出来上がった .ll ファイルを Clang などでコンパイルして実行ファイルを得る
という、非常にシンプルな仕組みです。
次回は「数値演算や型システム」にもう少し踏み込み、int 型をどう扱うか、i32 にマッピングした際のオブジェクト指向的な要素との兼ね合い、そして Python 的に多種多様な型を混在させるための工夫など、もう少し詳しい話題に入っていきます。

「Python は動的型付き言語なのに、どうやってコンパイル時に型を決めるのか？」という疑問を、どのように (簡易的に) 解決しているのか、実装の試行錯誤をシェアしようと思います。
次回:

https://zenn.dev/t3tra/articles/6be1531fdf9fe6
Discussion

高宮　はるきー
次の記事、楽しみにしています。
t3tra
ありがとうございます！
Pythonのコンパイラを作りたい #2 - Python AST から LLVM IR を生成するまでの概略

1. PythonのASTを取得する

1-1. `ast` モジュールによるパース

1-2. なぜ AST が重要なのか

2. VisitorパターンでASTを巡回する

2-1. AST ノードをどのように扱うか

2-2. Visitor パターンとは？

2-3. 数値リテラルと加算の極めて単純な例

3. `IRBuilder` でテキストを組み立てる

3-1. なぜ `IRBuilder` が必要なのか

3-2. IRBuilder のイメージ

3-3. `print("Hello!")` を例に

4. 実際に .ll ファイルを生成してみる

4-1. コマンドラインでの実行

4-2. 出力された IR の確認

5. Clang や llc で最終バイナリに

5-1. .ll ファイルを機械語へ

5-2. LLVM の最適化を活用する

6. まとめ & 次回の話

Discussion
