TAO/SILENTのバイトコード実行方式

山崎憲一(NTT), 天海良治(NTT), 竹内郁雄(電通大), 吉田雅治(NTT)

1. はじめに

我々は,実時間記号処理カーネルTAO/SILENTシステムを構築中である.この研 究の目的は,実世界の問題を扱うプログラムのための環境を提供することであ る.我々は,実世界の問題を扱うためには次のことが重要と考える. 我々は,これらを満たした言語・システムの実行機構として,プログラム言語 (TAO) をバイトコードにコンパイルし,これを専用マシン(SILENT)で実行する という方式を採用した.本稿では,まず一般のバイトコード実行方式の特性を 検討し,その問題点をTAO/SILENTにおいてどのように解決したかについて述べ る.また,Javaを例に取りバイトコード設計の際の選択肢について考察する.

2. 設計方針

なぜバイトコード方式か

bytecodeという言葉が広く知られるようになったのは, Smalltalk-80[goldberg83]のVMの実装が発表されてからであろうと思われる. (文献[koopman89]によれば,言語EULERのためのIBM360/30マイクロコードによ るバイトコードインタプリタが1967に報告されている.しかし,その当時にこ れをバイトコードと呼んでいたかは不明である.)しかし,それに類するもの には,Lisp Machineのmacrocode[greenblatt86],Pascalのp-code[nori81]な どがある.また,最近では,Javaがバイトコードを採用している.バイトコー ド,あるいはそれに類したコード体系の特性をまとめると以下のようになる. バイトコードに明確な定義はないが,これらをもってバイトコードの定義とす ることも可能であろう. これらのことから,次のような特徴が生ずる. これらに加え,Javaのようにプログラムの証明を行なう,あるいはコードを実 行中に書きかえる (quick命令) といったことも可能となる.これらのメタ・リ フレクティブ風の操作を,RISCの機械語コードに対して行なうのは容易ではな いし,強い最適化が行なわれたコードではさらに困難となろう.

我々がバイトコード実行方式を採用したのは,特に以下の理由による.

バイトコードをより高速化する方式として,JITがあるが,JITでは当然のこと ながら実時間性の保証はできない.

なぜ専用マシンか

バイトコードを,JITなどを用いずに直接解釈実行する場合,バイトコードの フェッチ/デコードは大きなオーバーヘッドとなる.SILENTでは,幾つかのバ イトコード専用ハードウェアを設けることで,バイトコードの実行を高速化し た (後述).専用マシンを採用した,これ以外の理由としては次がある.
  1. 動的検査を行なっても速度が低下しない. 型検査,範囲検査など実行時にしかできない検査が行なえる.
  2. デバグ情報を残しても速度があまり低下しない. すなわち,デバグと最終実行を区別する必要がない.
  3. 各パラダイムをサポートする専用ハードウェアを用意できる.
最後に付け加えるべきもう一つの理由として,ハードウェア製造の低コスト化 があげられる.Lispマシンなどの専用計算機が盛んに研究されていた時代には, 新規ハードウェアの製作はいろいろな意味でコストが高く,専用マシンには 10 倍程度の高速化が期待されていた.しかし,ハードウェアの製造コスト は年々低下し,実際,SILENTでは約10万ゲートのCPUとその周辺回路を一人の 研究者が設計/製作した.このため,ハードとソフトをコデザインしながら, ハードとソフトの役割分担を決定することが,より容易にできるようになった. SILENTには,このような実験としての意味もある[竹内97].

3. TAOのバイトコード

3.1 SILENTの概要

SILENTは,マイクロプログラム制御のプロセッサであるが,バイトコード実行 支援ハードウェアが用意されており,バイトコードをSILENTの機械語と考える こともできる.本稿では,このバイトコードのレベルを中心に述べ,マイクロ プログラムレベルのハードウェアには最小限しか触れない.このレベル (つま り最も低いアーキテクチャレベル) の主な仕様は次のとおりである. また,本稿の主題ではないが,SILENTの重要な特徴であるパラダイム支援ハー ドを列挙する. なお,SILENTは,大枠としては専用マシンELISのアーキテクチャを踏襲してい る.このため,本論文では本論文で提案する技法の評価を ELISを比較対象と して行なう.

3.2 TAOの実行方式

TAOの実行方式に起因する制約について述べる.

3.3 ダイトコード

TAOバイトコードは,1語が10bitである.このためバイトコードではなく decimalの dを取って,dyte (ダイト) コードと呼ぶ.ダイトが10bit幅である のは,タグ部(8bit)+データ部(32bit)の中にちょうど4ダイトが入るためであ る.SILENTでは,タグはデータ部とは別のメモリ空間にあり,データ部にのみ 連続したバイトアドレスが割り当てられている (他プロセッサとのバス結合に よるメモリ共有のため).ダイトもバイトも一つのデータ部に4つ入ることから, 共通のアドレスが割り当てられ,ハードウェア上もソフトウェア上も,ダイト を自然に扱うことができる.さらに,コード幅が8bitから10bitと広がったこ とで,様々な最適化が可能となった (後述).

TAOの (一つのプロセスの) 実行モデルでは,メモリはヒープ領域と 1本の スタックからなる.関数呼出しの制御,引数渡し,catch/throwなどの動的制 御は,すべてこの 1本のスタック上で行なわれる.

主なレジスタには,以下のものがある.

ef (environment frame): 環境フレームを指す
dynalink (dynamic link): 動的フレームを指す
ip (instruction pointer): ダイト命令のアドレスを指す
sp (stack pointer): スタックトップレジスタ

基本的な実行モデルはスタックマシンであり,関数呼出しは,呼出す関数の 取り出し,引数のスタックへのプッシュ,関数本体の実行というステップから なる.代表的なダイトコードを示す.[〜]はオペランドを表し,→はスタック の変化を表す.

car[]: セルのcarをとる.
        <arg> → <argのcar>

const[tag+bit1-0, bit11-2, bit21-12, bit31-22]: 40bit定数のプッシュ
        <> → <40bit定数>

symbol[bit9-0, bit19-10, bit29-20]: シンボルのプッシュ
        <> → <symbolタグ付き32bit定数>

small-int[bit9-0]: 10bitに収まる正の数のプッシュ
        <> → <intタグ付き10bit定数>

make-symbol-fn-frame[symL,symM,symH,offset]:
                        関数呼出しのためのフレーム作成
                        symは関数名.offsetはipとリターンアドレスの距離.
        <> → <関数フレーム>

call-fn-ef[offset]: 関数呼出し (offsetはefと関数呼出しフレームの距離)

exit-fn[]: 関数からのリターン

4. ハードウェアによる高速化

4.1 ダイトコード実行支援機構

ここではダイトコードを実行支援するためのSILENTのハードウェアについて述 べる.ダイトのデコードとディスパッチを行なう専用ハードウェアは下図のよ うに構成される.

━━━┯━━━━━━━━━━━━━━━━━━━ Aバス(40bit)
      │                  ↑
  ━━┿━━┯━━━━━━┿━━━━━━━━━━ Bバス (40bit)
      │    │            │↑
      │    │            ││                          ┌──────┐
      │    │            ││                          │ ipレジスタ │
      │    │            ││                          └──┬───┘
      ↓    ↓       10bit││                                ↓
    ┌────┐        ┌┴┴─────────┐      ┌──────┐
    │  ALU   │        │ダイトバッファ(11dyte)│←─→│ メモリ制御 │
    └─┬──┘        └───────────┘      └──────┘
        │                │                                  ↑
        ↓                ↓                                  │80bit
  ━━━━━━━━━    ┌─────┐                        ↓
    Yバス (40bit)       │シーケンサ│                   外部メモリバス
                        └─────┘

                図.ダイトバッファに関連するデータパス
ipレジスタは,現在実行中のダイトアドレスを指す.ダイトコードは,11ダイ ト (110bit) のバッファに格納され,一つデコードされるたびに自動的に 1ダイトシフトされる.バッファの残りが3ダイト以下になると,自動的に次の8 ダイトがフェッチされる.自動的なフェッチは,ipへのアドレスセットでも 起こる.

ダイトをディスパッチするには,マイクロプログラムのdyte命令を使う. 例えば,空リスト() をプッシュするコード (push-empty)は,

        (       (mov empty -<sp>) dyte)
である.push-emptyは 656番なので, このマイクロコードがダイトディスパッチ表の656番目に置かれている.ディ スパッチによってこの命令が実行されると,スタックに空リストがプッシュされる. 同時にdyte命令によってipがインクリメントされ,次のダイト がディスパッチされる.

このハードウェア自身は,LispマシンCADR[Greenblatt86]に既に採用されているが,ダイトの 語長が 10bitという処理しにくい大きさであるため,ハードウェアディスパッ チが極めて有効である.

4.1 スタックマシンとレジスタマシン

TAOは原則としてスタックマシンモデルを採用する.これを高速化するために, 次のような専用ハードウェアが用意されている.

スタックは,ハードウェアスタックであり,独自のバスを持ち,メモリアクセ スと並行してアクセス可能である.スタックポインタは3本用意されており, スタックの中間を自由に指すことができる.さらに,スタックポインタの指し ている場所の値が自動的にキャッシングされるレジスタが用意されており,こ のレジスタのアクセスは,通常のレジスタと同じ速度でアクセス可能である.

スタックアクセスで最も頻繁に行なわれるのは,スタック中に置かれた変数の プッシュである.SILENTでは,これを高速に行なう命令lapvarを用意している. 例えば,環境フレームポインタ(ef)から4番目にある変数を,スタックにプッ シュする命令var4は,次のようなコードにより実行される (ここで,4wはマイ クロプログラムアセンブラによって,4語分の値16に変換される).

        (       (- ef 4w sp0) lapvar dyte)
sp0は,lapvar用の特別なスタックポインタである.lapvarは,sp0にセットさ れたアドレスから値を読出し,これをスタックにプッシュする.lapvarの次 の命令でスタックをアクセスしない限り,この動作は陰で並行して行なわれる. このため,通常は変数のプッシュに1サイクルしか要しない.(次の命令で, スタックアクセスをすると自動的に待ちが入る.)

スタックポインタが3本あるため,スタックトップを指すレジスタを除いた2本 は,プログラムで自由に使うことができる.実時間GCや,catch/throwなどの 動的構文の処理では,スタックを高速にスキャンできることが重要である.2 本のレジスタを用いるとインターリーブしながらのスタックアクセスが可能とな る.

融合型言語であるTAOでは,論理型計算をも効率よく実行する必要がある.論 理型言語の実装では,WAM (Warren Abstract Machine) が有名であるが,この 実行モデルはレジスタマシンである.スタックベースで論理型言語を実装する 研究[Zhou96]もあるが,通常はWAMの方が高速である.しかし,バイトコードの レベルからレジスタを直接操作することは難しい.例えば,

        add     R1, R2, R3
という命令を解釈実行するCのコードは,
        case ADD:
                reg[*(pc+3)] = reg[*(pc+1)] + reg[*(pc+2)];
                pc += 4;
                break;
のようになり,オペランドのアクセスとレジスタのアクセスが頻繁に生ずる. ELISにおいてもWAMをこのように実現していたが,SILENTではこれを高速化す るため,ダイトバッファにあるオペランドの値を用いて間接的に実レジスタに アクセスする機構を設けた.例えば,あるレジスタに () をセットするという 命令 (put-empty,1オペランド) は,
        (       (mov empty <nql>+) dyte)
というマイクロコードによって実現される.ここで,<nql>は,ダイトバッファ の先頭にあるダイトコード (すなわち,put-empty というダイト命令のオペラン ド) の下位5ビットに応じて,r32〜r63をアクセスする.例えば,オペランドが1 ならば,<nql>はr33を指すことになる.<nql>+は,アクセス と同時に,ダイトバッファを 1ダイトシフトする.

4.2 デコード表の切り換え

状態に応じてデコードの意味を変えたいことがある.例えば, WAMの単一化のコードの実行には,readモードとwriteモードがあり, 同じコードでもその意味が異なる. また,ダイトコードの種類が1024 (= 2 ^ 10) を越えた時も, prefixをつけてダイトコードの意味を変える必要がある.

このために,SILENTは,2つの方法を提供する.一つは,1024多重分岐命令で ある.例えば,

        (       (br nd9-0 prefixed-table))      ; br は BRanch,ndは Next Dyte
という命令では,prefixed-tableというアドレスにダイトコードの値 (0〜1023)を加えた値に制御が移る.TAOの論理型プログラムでは,これを用 いてモードを実現している.

一方,比較的長い時間に渡ってデコード表を変更したい時には,dytbas (dyte base) というレジスタに,別のデコード表のベースアドレスをセット する.これは,システム立ち上げ用のダイトと通常実行のダイトを切り換え る時などに使用している.また,これを用いて,現在のダイトを保持したまま 例えば新たにC用のダイトを追加したりすることが可能となろう.

5. ソフトウェアによる高速化技法

ソフトウェアの面でも幾つかの高速化技法を用いている.通常の言語のコンパ イラと同じ意味での最適化も幾つか行なっているが,この章では,バイトコー ドを高速化するという意味での最適化についてのみ述べる.

5.1 オペランドの細分類化

頻繁に現われるオペランドのパターンや,オペコード自身の動作を分類して, プログラムが高速になるようにオペコードを細かく設定する.例えば,変数 アクセスには,オフセットが2〜17までの専用命令 (var2〜var17)が用意され ている.小さい整数のプッシュは,
small-int[bit0-9]: 10bitに収まる正の数のプッシュ
small-mint[bit0-9]: 10bitに収まる負の数のプッシュ
のように符号拡張が容易となるよう細分化した.

5.2 定数命令

定数命令は,バイトコードの体系に入れにくい命令である (RISCでも定数ロー ドは何かと不便である).例えば40bitの定数を,ダイトコードに埋め込むと, オペコードと合わせて 5ダイトを消費してしまう.また,そのような4ダイト を,一つの40bitに組み立てることに時間を要するという欠点もある.ELISで は,定数表をレジスタに保持し,バイトコードにはその表の中のオフセットを 入れていた.これによって256種類あるいは65536種類の定数にアクセス可能と なる.

しかし,ELISよりもクロックが高速になったSILENTでは,メモリ読出しは重い 処理である.そこで,SILENTでは,ダイトコードに定数を埋め込むこととした. 埋め込みにより多くのダイトを消費するという問題については,例えば0〜 1023の整数用,0〜1048575の整数用,シンボル用,キーワード用など多くのオペ コードを用意することでコード量を押さえた.また,40bitデータの組み立て は,2ダイトを20bitとして読みだすハードウェアを用意することで高速化した (ただし現バージョンのSILENTでは,ハードウェアのバグによりこれは動作 していない.).

定数をダイトコードに埋め込むことにより,GCからその定数がマーキングされ なくなるという問題が生ずる.これを避けるため,ダイトコードに埋め込まれ た定数の表を別に持っている.これはダイトコードの実行に際してアクセスさ れることはなく,GCのみが参照する表である.したがってレジスタに保持する 必要はなく,GCが辿れるところに存在すれば十分である.

5.3 リエゾン

既に述べたように,変数アクセスは1命令で可能であるが,これはその次の命 令でスタックアクセスをしない場合に限られる.しかし,
        (+ x y)
といった式は,例えば,
        var2            ; 2番目のスロットの値をpush
        var3            ; 3番目のスロットの値をpush
        +
といった命令列にコンパイルされる.ここで,var2とvar3,var3と+はそれぞ れスタックアクセスを伴なう命令である.特にvar3と+は,プッシュした直後 にポップするという無駄な動作になる.そこで,特定の2命令が連続した時に は,それらのコードを修正する最適化を行なう (これをリエゾンと呼ぶ).例 えば,上のコードは,
        var2
        var3^
        ^+
というコードになる.ここで,^がついたコードは,スタックトップの代わり に特定のレジスタを使って値を受け渡すこと以外は,リエゾンを受ける前のコー ドと同じ動作をする.さらに,var2とvar3はスタック操作が連続するが,これ も2つの変数を先にロードしてしまって,プッシュを連続させることで,若干 の高速化が可能となる.結局,上のコードは,
        vars/--^[2,3]
        ^+
というコードになる.

リエゾンは文献[Ertl95]のスタックキャッシング最適化に類似しているが,きわめて 簡単な処理で高速化が可能である.TAOのようにコンパイル速度を高速化した い場合は特に有用である.

6. 評価

現時点では,すべての機能の実装が終わっておらず,大規模なプログラムは実 行できない.ここでは,Lispのappendの速度を測定した.

SILENT(33MHz)  ELIS (5.6MHz)
append100 143.22μs 1593.0μs

ELISは,前述の専用ハードウェアを持っておらず,ソフトウェアとしての最適 化も不十分であった.この結果だけでは,それぞれの最適化の効果を調べるこ とはできないが,総合的にはクロック換算で約2倍の効果があったと言える. 一方,論理型プログラムについては,レジスタ転送の最適化器が完成しておら ず,この部分を手で簡単に最適化したところでは,appendで690KLIPSという速 度が得られている (ELISは41KLIPS).Lispで書かれたappendの速度を換算する と約700KLIPSとなるから,ほとんど同程度の速度となっている.ただし,論理 型プログラムであることに由来するオーバーヘッド,つまり,論理型ではテー ルマージ最適化を行っている,関数では再帰最適化が行なわれていない,など の理由から厳密に比較することはできない.

7. 考察 - Javaバイトコードとの比較 -

本節では,Javaのバイトコードを例に取り,バイトコード設計の際に考慮すべ き設計ポイントについて検討する.

[コード幅]
TAOのリエゾンや変数アクセスなどの最適化は,ダイトが10bit,すなわち1024 種類ものオペランドが表現可能なことに依存している.Javaでは,現在規定さ れているバイトコードがすでに202種類あり,ほとんど拡張性がない.一般の アーキテクチャでは,ダイトコードのように8の整数倍でないビット数を単位 とすることは難しいが,例えば 16bit単位のコードとすることは可能である. バイトコードの利点の一つは,コードがコンパクトなことである.16bitとす ることで,コード量が増えるが,2オペランドのものはそのままなので,2倍に なるわけではない.このことをJavaのバイトコードで調査した.Javaでは,オ ペランド個数ごとのコード種の数は,以下のようになる (ただし,Nは可変長 の命令).

オペランド数オペコード種類
0 148
1 15
2 34
3 1
4 2
N 2

JDKのAWTに関するクラスを調べたところ,命令長の分布は以下のようになった.

オペランド数 出現数 バイト数 16bit化
05463 5463 10926
11495 2990 2990
2405112153 16204
3 4 16 16
4 103 515 618
N 7 - -
Nを除く合計1112321137 30754

この表で,16bit化とは,コード単位を16bitとし,奇数オペランドをオペコー ドに埋め込んだ場合のバイト数である.16bit化により,コード量が45%程度増 加することがわかる.

16bit化によって命令種類を増やすことが可能となり, 例えばオペコードのマージができる. AWT中の連続した2命令の出現頻度を数えると,以下のようになる.

出現回数   出現パターン
754aload_0,getfield
201return,aload_0(実行シーケンスとしては無意味)
196putfield,aload_0
172aload,getfield
144getfield,invokevirtual
143invokevirtual,aload_0
142aload_0,invokevirtual
134aload_1,getfield
132ldc1,invokevirtual
132invokevirtual,invokevirtual

最初のパターンは典型的なインスタンス変数のアクセスであるが,これはスタッ クのプッシュとポップが連続するから,マージすることにより高速になる可能 性がある.

参考までに,AWT中の(静的な)出現頻度順で上位のオペコードは以下のようになる.

1454  aload_0/0    (selfのロード)
1336  getfield/2
896  invokevirtual/2
552  aload_1/0
540  iload/1
367  putfield/2
328  aload_2/0
307  return/0
293  aload/1
275  iconst_0/0

[レジスタマシンかスタックマシンか]
前述のようにレジスタマシンのバイトコードを,ソフトウェアで効率よくエミュ レートするのは難しい.しかし,WAMなどレジスタマシンを前提としたコード もあり,必ずスタックマシンのコードを出せるわけではない.また,ハードウェ ア化した場合には,レジスタマシンの方が高速化が容易であるが,本稿で述べ たリエゾンなどを適用すれば,スタックマシンでもある程度の高速化が可能で ある.前述のように,SILENTでは関数型プログラムと論理型プログラムとは, 同等の実行速度となっている.

また,レジスタマシンは,レジスタ数という物理的な制限を隠せないことも 問題である.仮想マシン上では無限個のレジスタを仮定するのが通常であるが, 当然そのまま実装することはできない.実行時にレジスタ数の溢れチェックが 必要になるなどの問題がある.

コード量も大きな問題である.Javaのフィボナッチプログラムに対し,仮想的 なレジスタマシンコードでコーディングしてみたところ48バイトとなった ( オリジナルのJavaコードは23バイト).コード幅を増やすよりも,実行モ デルをレジスタマシンとすることの方が,コードの増加量は大きい.

これらをまとめるとスタックマシンは,エミュレーション時の速度,物理層の 隠蔽,コード量の点で有利である.

[定数ロード]
Javaでは,定数は定数プールからロードする.前述のようにELISでも同様の方 式を取っていた.しかし,この方式では,毎回一回のメモリアクセスを必要と する.さらに ELISでは,定数表が関数ごとに用意されていたため,関数呼出 しとリターン時に表を指すレジスタを退避回復する必要があった.Javaでは, 定数プールはクラスごとに用意されているため,毎回オブジェクトから定数テー ブルを辿るか,定数テーブルをレジスタにキャッシングしておくなどの方法が 必要となり,いずれにしても速度は期待できない.TAOのように定数を直接埋 め込む方法では,コードが増えるという欠点はあるが高速である.なお,Java の定数プールアクセスをすべて4バイト埋め込みにすると,AWTのコード量は, 33% (7061バイト)増加する.

ただし,直接埋め込む方法では,定数を組み立てることに時間を要する場合が ある.任意のバイト境界からメモリ読出しができるプロセッサであれば問題 はないが,それ以外の場合は定数表方式の方が速い可能性もある.

[動的機構の性能]
バイトコードとは直接の関係はないが,多くの場合,バイトコードを採用する 言語は,インタープリタに近い言語であり,動的プリミティブを持ってい る.Javaでは,例外処理がこれに当たるが,この処理を重視したフレーム構造 となっていないため,極めて遅い処理となっている.TAOでは,動的フレームが 環境フレームとは別のリンクになっており,極めて高速に処理される.本稿では, こういった言語実装一般については論じなかったが,重要な問題である.

[ハードウェア化 - Javaチップ -]
Javaをハードウェアで直接動かすいわゆるJavaチップは,正式には発表され ていないが,SUNのpicoJavaチップに関する資料[Sun98]によれば,以下のようなハー ドウェアが特に高速化に効果があるとしている.

  1. 12バイトのバイトコードキャッシュ
  2. 64語のスタックキャッシュと stack dribbling
  3. folding operation
1は,SILENTのダイトバッファ同様のバイトコードのためのバッファである.2 は,スタックトップから64語分のデータをチップ内のキャッシュに格納してお き,キャッシュ内のデータ量とスレッショルドを比較し,自動的にスタックか らロードあるいはスタックへセーブする仕組みである.このような方式では, 64語より深い場所へのアクセスは重くなるが,Javaでは,そのようなことはあ まり発生しない.一方TAOでは,動的にスタックを探すこと (catch/throwや, 動的変数など) の速度も重視しており,このような方式は取れない.3は,ロー カル変数の値をスタックトップにプッシュした直後にその値を使用するという パターンをハードウェアで検出し高速化する仕組みである.TAOのリエゾンに 類似している.

[他のバイトコードとの比較]
本章ではJavaとの比較について述べてきたが,最後に参考として,他のバイト コードとの比較を示す.

 TAO Smalltalk-80p-codeoaklispJavaWAM(sicstus)macrocode
処理単位 (bit) 10830固定1681616固定
オペコード数 7022486235202265-
引数埋込 2661084bit8bit5359-
定数ロード 直接表間接コード埋込直接表間接直接-
実行モデル 混合スタックスタックスタックスタックレジスタスタック

ここで,「引数埋め込み」は引数埋め込みによって展開されたオペコード数を指す. また,TAOのオペコード数は,論文執筆時点のものである.

8. まとめ

TAO/SILENTのダイトコード実行方式と,その高速化技法について述べた.専用 ハードウェアとして,ダイトコードバッファとディスパッチャ,およびレジス タ間接アクセス機能を設けた.ソフトウェアとしては,定数埋め込み,および リエゾン最適化を行なった.これらの最適化を行なうことで,バイトコードを 極めて高速に実行できる.

バイトコードは,従来から多くの言語・処理系で用いられてきており,今後も 使われていくと思われる.バイトコードの設計に際し検討すべき点を,Javaを 例に取り示した.

謝辞: 初期のバイトコードマシンに関する情報を教えて頂いた電気通信大学の 山内斉助手,前田敦司助手に感謝します.

参考文献