jvm backend in PyPy

PyPy (正確には RPython toolchain) の jvm backend への翻訳処理の設計を知りたくてソースコードを追い掛けてみた.

ややメモ書きっぽい感じだが, ほぼ自分用メモということで許してください.

(以下, パスは全て pypy のルートディレクトリを起点としている.)

入口

pypy/translator/jvm/genjvm.py の GenJvm クラス. たぶんだけど. pydoc はこんな感じ.

""" Master object which guides the JVM backend along.  To use,
create with appropriate parameters and then invoke
generate_source().  *You can not use one of these objects more than
once.* """

バイトコード吐いてるのが pypy/translator/jvm/generator.py の JVMGenerator. 既存の何かを使ってたわけではなく, 自作していたのか…… しかも raise NotImplementedError がそこかしこに見える……

これ作った人すごいなぁ. javac 相当のものを RPython で実装しているし. Antonio Cuni さんの仕事はどこまでなんだろうか?

GenJvm#generate_source

これを呼ぶと処理をしてくれるらしいのでここから読む.

メソッドの実装はこんな感じ.

def generate_source(self):
    """ Creates the sources, and returns a JvmGeneratedSource object
    for manipulating them """
    GenOO.generate_source(self)
    self.jvmsrc.set_jasmin_files(self.db.jasmin_files())
    return self.jvmsrc

Jasmin という jvm アセンブラを使っているようだ. Jasmin home page 処理は, 親クラスである GenOO の generate_source メソッドに処理を投げて, 出来上がった jasmin ファイルを jvmsrc 属性に格納して返しているようだ.

さてこのメインの処理を行っていそうなメソッドを覗いてみよう.

pypy/translator/oosupport/genoo.py を開く.

GenOO#generate_source

def generate_source(self):
    self.ilasm = self.create_assembler()
    self.fix_names()
    self.gen_entrypoint()
    self.gen_pendings()
    self.db.gen_constants(self.ilasm)
    self.ilasm.close()

う〜む, 綺麗だ. 文句の付けようが無い. だいたいどんな処理をやっているのか分かりやすくて良い.

GenJvm#create_assembler

まず処理の主体となるであろうアセンブラを用意しているところから見る. デフォルト実装は raise NotImplementedError となっていて, GenJvm クラスでは以下の実装になっていた.

def create_assembler(self):
    """ Creates and returns a Generator object according to the
    configuration.  Right now, however, there is only one kind of
    generator: JasminGenerator """
    return JasminGenerator(self.db, self.jvmsrc.javadir)

JasminGenerator クラスは pypy/translator/jvm/generator.py にある.

JasminGenerator のコンストラクタはいったん置いといて, 次の処理の中身を見てみる.

GenOO#fix_names

def fix_names(self):
    # it could happen that two distinct graph have the same name;
    # here we assign an unique name to each graph.
    names = set()
    for graph in self.translator.graphs:
        base_name = graph.name
        i = 0 ...

初めての RPython Toolchain

タイトルは釣りっぽく見えるかもしれませんが, 理論にばっかり興味あったので, RPython をちゃんと触るのは初めてです.

発端

理論派で手を動かすのが億劫な俺が実装書いてみようと思った動機は, PyPy Sudden Death Calendar 27日目 - JVM Backend に完敗した件を受けて にある話にあります. ここでは ootype によって JVM 用に変換されたクラスがしっちゃかめっちゃかだ, ということを追っています. なんでこんなことになっているのか分からないので, まずは簡単なインタプリタを例に RPython Toolchain の動きを追っていく計画です.

プログラム仕様

このプログラムの仕様はすごく簡単で, 各行の先頭に暗黙の echo があるものとして動作します. プログラミング言語 ECHO とでも呼びましょうか.

実装

さっきのブログエントリの筆者でもある shoma さんが翻訳されている PyPy を使ってインタプリタを書く を参考に作りました.

"""
echo.py

programming language ECHO
implemented on top of PyPy

by cocoatomo
"""

import sys
import os

try:
    from pypy.rlib.jit import JitDriver
except ImportError:
    class JitDriver(object):
        def __init__(self, **kw): pass
        def jit_merge_point(self, **kw): pass
        def can_enter_jit(self, **kw): pass

jitdriver = JitDriver(greens=['pc', 'program'], reds=[])

def mainloop(program):
    pc = 0

    while pc < len(program):
        jitdriver.jit_merge_point(program=program, pc=pc)

        line = program[pc]

        # instead of print
        os.write(1, line)
        os.write(1, '\n')

        pc += 1

def parse(program):
    return program.split('\n')

def run(fp):
    program_contents = ''
    while True:
        read = os.read(fp, 4096)
        if len(read) == 0:
            break
        program_contents += read
    os.close(fp)

    program = parse(program_contents)
    mainloop(program)

def entry_point(argv):
    if len(argv) < 2:
        print("too few arguments. program file name needed.")
        return 1

    run(os.open(argv[1], os.O_RDONLY, 0777))
    return 0

def target(*args):
    return entry_point, None

def jitpolicy(driver):
    from pypy.jit.codewriter.policy import JitPolicy
    return JitPolicy()

if __name__ == "__main__":
    entry_point(sys.argv)

なんの変哲も無い処理系です.

PyPy は pypy-ja で fork している レポジトリ から取ってきました.

$ python ./pypyja/pypy/translator/goal/translate.py --opt=jit echo.py

とすると長々とビルドが走り, MBA によって俺の腿が温まりました.

$ cat input.echo
begin
1 ...

注釈器は何をしているのか? - PyPy Advent Calendar 2011

この記事は PyPy Advent Calendar 2011 の17日目の記事として書いています. 2周目ってけっこう速く来るんですね. 執筆時刻は気にしないように.

何を書くのか?

PyPy Toolchain には「注釈器 (annotator)」というものが含まれており, こいつは RPython に出てくる変数について, そのメタ情報である「注釈 (annotation)」を与えていきます.

この注釈器の具体的な動きの説明を書いていきます. 途中で力尽きる予定なので, その続きは後日書きます(エ

元ネタ

資料としては The Annotation Pass から参照されている Compiling Dynamic Language Implementations (←PDF です) という論文の §6 Annotator を使っています. 実質この記事は, §6の要約になっています.

この論文は 2005 年のものですが, 全体像を掴むのに良さそうなので選びました.

注釈とは

注釈というのは結局は型 (ある値の集合) なんだけど, Python の方の型とごっちゃになって面倒なので, 敢えて注釈という用語を使っています. 注釈が常に Python の型と一致しているわけではないし, そうなる必然性もありません. Python に新しい型システムを導入していると思ってください.

注釈付け

Python では初期化された瞬間でしか変数の型が分からないことが多いです. なので, 実行順序に沿って前の方から処理を追っていかねばなりません.

注釈付けの処理は本質的には型推論なのですが, Hindly-Milner のように前後に移動しながら型推論を行うことはできないので, それに比べると安直 (naive) な方法です.

ループとかプロシージャ呼び出しとかがあると変数の注釈がより緩い (general) 注釈に変更されることがあるのですが, その場合は再度最初から計算し直して, 注釈がこれ以上一般化 (generalize) されない状態にまで持っていきます.

注釈の種類

注釈の種類には, 型としてお馴染のものとやや Python では聞き慣れないものがあります.

  • Bot, Top: Bottom と Top. Java で言う「暗黙的にある null のクラス」と「Object」です.
  • Int, NonNegInt, Bool: Bool は特殊な Int として定義されています. (たぶん 0 と 1)
  • Str, Char: Char は長さ1の String です.
  • List(v): v はリストの要素のようです.
  • Pbc(set): set は実行時に定義される定数の有限集合だそうだ. function とか class とか method という callable もここに入っています.
  • None: Python の None です.

ここではリストに載せなかったけど, NullableStr みたいな注釈や dict, tuple, float, unicode point, iterator などなどの注釈もあるんだけど発想はストレートなものなので説明省略します.

そしてこれら注釈の間には包含関係があり, その関係による束 (lattice) を構成します. Top が一番上に来て最も緩い型を表し, Bot が一番下に来て最も狭い型 (=どんな値も取りようの無い型) を表します. これについては PDF の Figure 1 と 2 を見てください.

注釈器の目的

以下のように記号を置きます.

  • A: さっき出てきた注釈が成す束
  • V: 全ての変数の集合
  • E: 変数どうしの同値関係
  • b: 関数 V -> A

A, V は分かりやすいと思います. E は, 2つの変数が同じ値を指しているかどうかの情報を蓄えている, と捉えてください. b は, ある変数がどの注釈に属するのか (ある変数にどの注釈を付けるべきか) を表している, と捉えてください.

この記号を使って状態 (state) とその間の関係 (generality) を説明します.

状態というのは関数 b: V -> A と V 上の同値関係 E の組 (b, E) で, 要は注釈情報の集まりです. ある状態 (b', E') が状態 (b, E) より一般的 (general) というのは, ∀v ∈ V, b'(v) ≧ b(v) かつ E' ⊃ E であることを言います. (A 上の関係 ≧ は注釈の包含関係 ⊃ に等しい.) 言葉で説明すると, 全ての変数について同じかより広い注釈を付け, 同値関係にある変数の組が同じか増えている状況を言います.

最も一般的な状態 (b_max, E_max) というのは, ∀v ∈ V, b_min(v) = Top, E_max = {(v, v') | v, v' ∈ V} のことです. つまり, 型に関して何にも情報がありません. 逆に最も一般的でない状態 (b_min, E_min) というのは, ∀v ∈ V, b_min(v) = Bot, E_min = {(v, v) | v ∈ V} のことです. つまり, 全ての変数が値を取り得ないというへんてこりんな状況です.

ここまでで準備した言葉によって, 注釈器の目的を以下のように書くことができます.

解析対象のプログラムに対して, 最も一般的でない (狭い) 状態を求める.

語弊を恐れずに言うと, それぞれの変数が取り得る型の中で最も狭いものを求める, ということです.

まとめ

突然まとめに入ります.

PDF の 6.1 から 6.4 あたりを眺めて軽くまとめただけですが, 色々細かいところや 6.4 の後半以降を省いています. これがブログ記事だということもありますし, まだ自分がちゃんと読めてないという理由もあります. 元の論文が 2005 年に発表されたものなので, それ以降の情報なども加えつつ, これの続きに関してどこかでちゃんと説明したいと思っています.

次は Masahito さん です. よろしくお願いします.

それでは.

Licenses