2010年12月23日木曜日

Dalvik インタプリター生成に関する README (dalvik/vm/mterp/README.txt)

Dalvik "mterp" README

NOTE: 再ビルドの方法はこのファイルの末尾にあります.

NOTE: Find rebuilding instructions at the bottom of this file.


=== 概要 ===

==== Overview ====

これは Dalvik インタプリターのソースコードです. 元のバージョンの中核部分は単一の C 関数として実装されていましたが, パフォーマンスを改善するためにアセンブリで書きなおしました. 今回の, および将来のアセンブリ移植を容易にし, また不具合が混入しにくくするため, プラットフォーム固有コードの開発を一度に一オペコードずつとするためのモジュール的手法を採用しました.

This is the source code for the Dalvik interpreter.  The core of the original version was implemented as a single C function, but to improve performance we rewrote it in assembly.  To make this and future assembly ports easier and less error-prone, we used a modular approach that allows development of platform-specific code one opcode at a time.

元のオール・イン・ワン関数の C バージョンは「可搬性のある」インタプリターとしてまだ存在しており, プラットフォーム固有バージョンのインタプリターを生成するのと同じソースとツールを使用して生成されます. 可搬インタプリターの一形態として, プロファイリングとデバッギングをサポートするものがあり, プラットフォーム用に最適化された実装がある場合でも, この形態は含まれます.

The original all-in-one-function C version still exists as the "portable" interpreter, and is generated using the same sources and tools that generate the platform-specific versions.  One form of the portable interpreter includes support for profiling and debugging features, and is included even if we have a platform-optimized implementation.

コンフィギュレーションそれぞれに対して, ソースコードの生成方法を制御するための config-* というファイルが存在します. ソースは out ディレクトリに書き込まれ, Android ビルドシステムがそれらのファイルを利用します.

Every configuration has a "config-*" file that controls how the sources are generated.  The sources are written into the "out" directory, where they are picked up by the Android build system.

インタプリターを詳しく知るための一番の方法は, (例えば) armv5te 内にあるような種々のコンポーネントの切れ端を見ていくことではなく, out/InterpC-portstd.c といった "out" ディレクトリに生成されたファイルを見ることです.

The best way to become familiar with the interpreter is to look at the generated files in the "out" directory, such as out/InterpC-portstd.c, rather than trying to look at the various component pieces in (say) armv5te.


==== プラットフォーム別ソース生成 ====

==== Platform-specific source generation ====

アーキテクチャー固有の config ファイルにより, 二つの生成ファイル (InterpC[arch].c と InterpAsm-[arch].S) の内容が決定されます. 目標は, 初期段階の開発とテストの期間中に C とアセンブリソースを簡単に切り替えられるようにすることであり, また, アーキテクチャ固有バージョンの機械語を使用する方法を提供することです (例えば ARMv6 で PLD 命令を使用したり, ARMv4T で CLZ 命令を避けたり, など).

The architecture-specific config files determine what goes into two generated output files (InterpC-[arch].c, InterpAsm-[arch].S).  The goal is to make it easy to swap C and assembly sources during initial development and testing, and to provide a way to use architecture-specific versions of some operations (e.g. making use of PLD instructions on ARMv6 or avoiding CLZ on ARMv4T).

インタプリターの機械語に関して, 二つの基本的な前提があります.

Two basic assumptions are made about the operation of the interpreter:

  • アセンブリバージョンでは各インストラクションに対して (例えば 64 バイトなどの) 固定サイズが使用される. 「オーバーフロー」コードは末尾に追加される.
  • C の実装のほうが望ましい場合は, アセンブリバージョンは全てのローカル状態を「仲介」構造体にパックし, それを C 関数に渡す. 状態の更新は「仲介」構造体から取り出されてリターンされる.
  • The assembly version uses fixed-size areas for each instruction (e.g. 64 bytes).  "Overflow" code is tacked on to the end.
  • When a C implementation is desired, the assembly version packs all local state into a "glue" struct, and passes that into the C function. Updates to the state are pulled out of the "glue" on return.
「arch」の値は, 共通のプログラミング特性を持つアーキテクチャーを示していて, armv5te は全ての ARMv5TE CPU に対して機能しますが, 後方互換性や前方互換性はないかもしれません. (armv5t3-eabi といった, ABI モデルも同様に指定したいと思う「かも」しれませんが, 現在は記述が冗長になるだけで値は伴っていません.

The "arch" value should indicate an architecture family with common programming characteristics, so "armv5te" would work for all ARMv5TE CPUs, but might not be backward- or forward-compatible.  (We *might* want to specify the ABI model as well, e.g. "armv5te-eabi", but currently that adds verbosity without value.)


==== config ファイル・フォーマット ====

==== Config file format ====

config ファイルは先頭から下へと解析されます. ファイル内の各行は, 空行, ('#' ではじまる) コメント, もしくはコマンドです.

The config files are parsed from top to bottom.  Each line in the file may be blank, hold a comment (line starts with '#'), or be a command.

コマンドは次の通りです.

The commands are:

  handler-size [バイト数]

    アセンブリの範囲をバイト数で指定します. ほとんどのプラットフォームに
    おいて, 2 の累乗である必要があります.

  handler-size [bytes]

    Specify the size of the assembly region, in bytes.  On most platforms
    this will need to be a power of 2.

  import [ファイル名]

    指定されたファイルの内容が全て即座に読み込まれます. 置換処理は行われ
    ません. ".c" および ".h" ファイルは C 出力ファイルにコピーされ, ".S"
    ファイルはアセンブリ出力ファイルにコピーされます.

  import [filename]

    The specified file is included immediately, in its entirety.  No
    substitutions are performed.  ".c" and ".h" files are copied to the
    C output, ".S" files are copied to the asm output.

  asm-stub [ファイル名]

    指定されたファイルが, アセンブリ「スタブ」が必要となる箇所全てに読み
    込まれます. オペコード名に対してテキスト置換が行われます.

  asm-stub [filename]

    The named file will be included whenever an assembly "stub" is needed.
    Text substitution is performed on the opcode name.

  op-start [ディレクトリ]

    オペコードリストの開始を示します. いかなる op コマンドよりも先行しな
    ければなりません. 指定されたディレクトリは, 命令ファイルを取り出す
    デフォルトの場所となります.

  op-start [directory]

    Indicates the start of the opcode list.  Must precede any "op"
    commands.  The specified directory is the default location to pull
    instruction files from.

  op [オペコード] [ディレクトリ]

    op-start と op-end の間にのみ記述することができます. 指定されたオペ
    コードのデフォルトのソースファイル位置を上書きします. オペコードの
    定義は指定されたファイルから読み込まれます. 例えば「op OP_NOP armv5te」
    により armv5te/OP_NOP.S からロードが行われます. 置換辞書 (後述) が
    適用されます.

  op [opcode] [directory]

    Can only appear after "op-start" and before "op-end".  Overrides the
    default source file location of the specified opcode.  The opcode
    definition will come from the specified file, e.g. "op OP_NOP armv5te"
    will load from "armv5te/OP_NOP.S".  A substitution dictionary will be
    applied (see below).

  op-end

    オペコードの終わりを示します. これが現れたときには, 256 のオペコード
    が全て出力されており, 固定サイズの命令ハンドラー領域に収まらなかった
    コードがあとに続きます.

  op-end

    Indicates the end of the opcode list.  All 256 opcodes are emitted
    when this is seen, followed by any code that didn't fit inside the
    fixed-size instruction handler space.


op ディレクティブの順序は重要ではありません. 生成ツールは, VM のソースから順序の情報を取り出します.

The order of "op" directives is not significant; the generation tool will extract ordering info from the VM sources.

現在ほとんどのオペコードへの参照を含む形式は, 主に op-start ディレクティブ内で使用されています. 新しく移植を行うには, まず "c" から始め, アーキテクチャー固有の op エントリーを追加して命令を記述します. 完成すれば, それが対象のアーキテクチャーに対するデフォルトとなり, プラットフォーム固有コードを消すために "c" オペコードを挿入します.

Typically the form in which most opcodes currently exist is used in the "op-start" directive.  For a new port you would start with "c", and add architecture-specific "op" entries as you write instructions. When complete it will default to the target architecture, and you insert "c" ops to stub out platform-specific code.

op コマンドに指定された [ディレクトリ] は, "c" ディレクトリの場合は次の二点に関して特別に扱われます. (1) ソースは C コードであると仮定され, 生成される C ファイルに挿入される. (2) C 実装が出力されるとき, 「仲介スタブ」がアセンブリソースファイルに出力される. (生成スクリプトは常に 256 のアセンブリ命令を出力しますが, asm-stab がある場合はラベルだけを出力します.)

For the [directory] specified in the "op" command, the "c" directory is special in two ways: (1) the sources are assumed to be C code, and will be inserted into the generated C file; (2) when a C implementation is emitted, a "glue stub" is emitted in the assembly source file. (The generator script always emits 256 assembly instructions, unless "asm-stub" was left blank, in which case it only emits some labels.)


==== 命令ファイル・フォーマット ====

==== Instruction file format ====

アセンブリ命令ファイルは単なるアセンブリソースの断片です. セグメント型やアラインメントと同時に, 開始ラベルも生成ツールにより提供されます. 想定しているアセンブラは GNU as ですが, 他のアセンブラでも機能するでしょう (生成ツールが出力する仮想オペコードの幾つかについては調整作業が必要かもしれませんが).

The assembly instruction files are simply fragments of assembly sources. The starting label will be provided by the generation tool, as will declarations for the segment type and alignment.  The expected target assembler is GNU "as", but others will work (may require fiddling with some of the pseudo-ops emitted by the generation tool).

可搬インタプリターとコードを共有するため, C ファイルでは変わったことをいろいろやっています. (将来的にはそういうものの量は減っていくものと期待しています.)

The C files do a bunch of fancy things with macros in an attempt to share code with the portable interpreter.  (This is expected to be reduced in the future.)

全てのオペコードの断片に対して, それらが出力に追加される際, 置換辞書が適用されます. 置換対象は $value や ${value} という形式です.

A substitution dictionary is applied to all opcode fragments as they are appended to the output.  Substitutions can look like "$value" or "${value}".

辞書には常に次のものが含まれます.

The dictionary always includes:

  $opcode    オペコード名. 例えば OP_NOP.
  $opnum    オペコード番号. 例えば OP_NOP に対しては 0.
  $handler_size_bytes    命令ハンドラーのバイト単位の最大サイズ
  $handler_size_bits    命令ハンドラーの log 2 表現での最大サイズ

  $opcode - opcode name, e.g. "OP_NOP"
  $opnum - opcode number, e.g. 0 for OP_NOP
  $handler_size_bytes - max size of an instruction handler, in bytes
  $handler_size_bits - max size of an instruction handler, log 2

C のソースもアセンブリのソースも, C プリプロセッサーの処理が入るので, C 形式のコメントや #define のようなプリプロセッサー・ディレクティブを使用することができます.

Both C and assembly sources will be passed through the C pre-processor, so you can take advantage of C-style comments and preprocessor directives like "#define".

生成ツールに対する操作が幾つかあります.

Some generator operations are available.

  %include "ファイル名" [置換辞書]

    armv5te/OP_NOP.S といったファイルを読み込みます. 標準の Python 構文を
    使用し, 置換辞書の値を指定することができます. 例えば, 次のコード:

      %include "arm5te/unop.S" {"result":"r1"}

    により, "$result" が "r1" に変換された上で "arm5te/unop.S" が現在の
    位置に挿入されます.

  %include "filename" [subst-dict]

    Includes the file, which should look like "armv5te/OP_NOP.S".  You can
    specify values for the substitution dictionary, using standard Python
    syntax.  For example, this:
      %include "armv5te/unop.S" {"result":"r1"}
    would insert "armv5te/unop.S" at the current file position, replacing
    occurrences of "$result" with "r1".

  %default [置換辞書]

    標準の Python 構文を使用し, 置換辞書のデフォルトの値を指定します.
    「ベース」バージョンや「ベース」バリアントを用意するときに便利です.

  %default [subst-dict]

    Specify default substitution dictionary values, using standard Python
    syntax.  Useful if you want to have a "base" version and variants.

  %break

    命令ハンドラーの中心部分 (これは hander-size バイトに収まっていなけれ
    ばならない) と (命令ハンドラーブロックの末尾に追加される) 従属コード
    の間の区切りを示します.

  %break

    Identifies the split between the main portion of the instruction
    handler (which must fit in "handler-size" bytes) and the "sister"
    code, which is appended to the end of the instruction handler block.

  %verify "メッセージ"

    テストが必要な項目に関してメモを残します. (これはいつの日かもっと
    興味深いものになるかもしれません. 現在のところは, これに対しては,
    出力が生成される前に取り除く, という処理しか行われていません.)

  %verify "message"

    Leave a note to yourself about what needs to be tested.  (This may
    turn into something more interesting someday; for now, it just gets
    stripped out before the output is generated.)

生成ツールは, 命令が handler-size を超えていても警告を表示「せず」, 起動時にサイズ超過のハンドラーが検出された場合, VM は異常終了します. 固定幅命令のアーキテクチャーでは, これに取り組むのは容易ですが, そうでない場合はバイト数を数える必要があるでしょう.

The generation tool does *not* print a warning if your instructions exceed "handler-size", but the VM will abort on startup if it detects an oversized handler.  On architectures with fixed-width instructions this is easy to work with, on others this you will need to count bytes.


==== アセンブリソースから C 定数を使用する ====

==== Using C constants from assembly sources ====

common/asm-constants.h ファイルには, 定数値, 構造体サイズ, 構造体メンバーのオフセット, に関する定義が含まれています. 書式の自由度はかなり低いのですが, これは, C (書式が検証される場所) とアセンブリ (定義が使用される場所) の双方で使用できるように単純なマクロが使われているためです.

The file "common/asm-constants.h" has some definitions for constant values, structure sizes, and struct member offsets.  The format is fairly restricted, as simple macros are used to massage it for use with both C (where it is verified) and assembly (where the definitions are used).

ファイル内の定数の同期が取られていない場合, VM はエラーメッセージを出力し, 起動時に異常終了します.

If a constant in the file becomes out of sync, the VM will log an error message and abort during startup.


==== 開発のヒント ====

==== Development tips ====

作り始めたばかりのオペコードハンドラーの断片をデバッグする必要があり, デバッグコードがハンドラーサイズの上限を超えてしまう場合, 先頭に次の汎用ヘッダーを挿入してください.

If you need to debug the initial piece of an opcode handler, and your debug code expands it beyond the handler size limit, you can insert a generic header at the top:

    b       ${opcode}_start
%break
${opcode}_start:

    b       ${opcode}_start
%break
${opcode}_start:

既に %break を使ってしまっていても, そのまま残しておいて大丈夫です. 二番目の %break は無視されます.

If you already have a %break, it's okay to leave it in place -- the second %break is ignored.


==== 再ビルド ====

==== Rebuilding ====

ソースファイルの断片を何か変更したら, out ディレクトリ内にある合成されたソースファイル群を再ビルドする必要があります. out 内のファイルが編集可能であることを確認した上で, 次のコマンドを実行してください.

If you change any of the source file fragments, you need to rebuild the combined source files in the "out" directory.  Make sure the files in "out" are editable, then:

    $ cd mterp
    $ ./rebuild.sh

    $ cd mterp
    $ ./rebuild.sh

この文書を書いている時点では, Python 2.5 が必要です. 他のバージョンの Python をインストールしてある場合, 理解不能なエラーメッセージか, 単なる一般エラーを目にすることになるでしょう.

As of this writing, this requires Python 2.5. You may see inscrutible error messages or just general failure if you have a different version of Python installed.

最終ゴールは, このような別の手順を踏むことなく, ビルドシステムに必要な出力ファイルを生成させることですが, ビルドにおいて Python を必須とする準備はまだ整っていないのです.

The ultimate goal is to have the build system generate the necessary output files without requiring this separate step, but we're not yet ready to require Python in the build.