第 3 章 仮想メソッド呼び出しの高速化
3.4 仮想メソッド呼び出しのデバーチャル化
3.4.4 デバーチャル化のアルゴリズム
本節では、コンパイラに仮想メソッド呼び出しのデバーチャル化を実装する場合の、デバー チャル化アルゴリズムを述べる。
3.3.1節 で 提 案 し た コ ー ド 書 き 換 え に よ る 直 接 デ バ ー チ ャ ル 化 は 、 実 装 の 容 易 さ と 、
preexistence 解析や局所クラス解析よりも広い適用範囲を特徴とする。しかし、制御フローに合
流点を生成することが、各種最適化によるコンパイル時間の増加や、補償コードによるコード 量の増加を招く可能性がある。従って、できる限り制御フロー上に合流点を生成しないデバー チャル化方式を適用したい。一方、制御フロー上に合流点を生成しない脱最適化方式は、本方 式と同様にコンパイル時にメソッドがオーバライドされていない全ての仮想メソッド呼び出し
50 第3章 仮想メソッド呼び出しの高速化
に適用可能である。しかし、脱最適化は4.2節の関連研究でも述べたが実装が非常に複雑である ため、手間を考えた場合、候補に挙げにくい。
制 御 フ ロ ー 上 に 合 流 点 を 生 成 し な い 直 接 デ バ ー チ ャ ル化に、3.2節の関連研究で述べた
preexistence 解析や局所クラス解析がある。適用範囲は本方式や脱最適化より狭いが、これらの
方式は実装が容易である。preexistence 解析によって要求されるメソッドの再コンパイルは、メ ソッドの次回の起動時に行えばよい。局所クラス解析はメソッドの再コンパイルの必要が無く、
解析は静的型付けを持つ言語では型に関するデータフロー方程式を解くだけでよい。これらの 方式は、制御フローの上に合流点がないため、脱最適化と同等のコードを生成できる。もし、
仮想メソッド呼び出しに対して preexistence 解析と局所クラス解析が適用できない場合、コード 書き換えによるデバーチャル化を適用する。
最後に、コンパイル時に仮想メソッド呼び出しが取るレシーバのクラス階層において、すで にメソッドがオーバライドされていた場合、メソッドテストによる間接デバーチャル化を適用 する。この方式では型テストが必要になり、制御フローの合流点が生成される。しかし、3.3.1 節で述べた最適化を行うことで、合流点によるオーバヘッドを低減できる。
従って、コンパイラに仮想メソッド呼び出しのデバーチャル化を実装する場合、実装の容易 さと最適化能力を考慮して、図 3.12のアルゴリズムに基づいてデバーチャル化を適用するのが 適切である。このアルゴリズムでは、コンパイル中のメソッド m()内の全ての仮想メソッド呼 び出しのレシーバに対して局所クラス解析と preexistence 解析が行われていること、実行中のプ ログラム P の現在のクラス階層全体に対してクラス階層解析が行われていること、を前提とし ている。
本方式と preexistence による仮想メソッド呼び出しの直接デバーチャル化は、コンパイル時の
最適化と実行時ルーチンの協調によって実現される。図 3.13に、実行時のアルゴリズムを示す。
また、図 3.12のアルゴリズムによって、各仮想メソッド呼び出しへ適用される各デバーチャ ル化の適用範囲の分類を、図 3.14に示す。
51 V = コンパイル中のメソッドm()の仮想メソッド呼び出しの集合。
F = コンパイル中のメソッドm()のインタフェースメソッド呼び出しの集合。
while (V が空でない && Fが空でない) do
f = Fから選んだインタフェースメソッド呼び出し。
Fからfを削除する。
Cf = fに関するインタフェースクラスを実装するクラス集合。
if (Cfが唯一のクラスを持つ) then
Cfを仮想メソッド呼び出しで宣言される静的なクラスとして、
インタフェースメソッド呼び出しfを仮想メソッド呼び出しに変換してVに登録し、
元のインタフェースメソッド呼び出しを含むコードを生成する。
/* プログラムPを実行中、fに関するインタフェースクラスが複数のクラスによって
実装された場合に、fを仮想メソッド呼び出しに変換したコードを無効にするための
コード書き換え要求を出す必要がある。 */
プログラム実行中のメソッドオーバライド時に参照される集合Lに以下のtupleを登録 （key：fに関するインタフェースクラス、
action：コード書き換え要求、情報：[書き換えアドレスAf、書き換えコードCf]）。
else
通常のインタフェースメソッド呼び出しを生成する。
endif
v = Vから選んだ仮想メソッド呼び出し。
Vからvを削除する。
Nv = クラス階層解析の結果に基づく、vにおける呼び出し先メソッドの集合。
if (Nvが唯一のメソッドを持つ) then
T = 局所クラス解析の結果に基づく、仮想メソッド呼び出しvのレシーバに到達する型集合。
if (Tがオブジェクト生成式の型と同一) then 仮想メソッド呼び出しvに対して、
制御フローの合流点を生成しない仮想メソッドの直接デバーチャル化を適用する。
elif (preexistence解析の結果より、
仮想メソッド呼び出しvのレシーバがメソッドm()の実行中に不変である) then
仮想メソッド呼び出しvに対して、
制御フローの合流点を生成しない仮想メソッド呼び出しの直接デバーチャル化を適用する。
/* プログラムPを実行中、メソッドn()がオーバライドされた場合に、
メソッドm()の次の実行時に再コンパイル要求を出す必要がある。*/
プログラム実行中のメソッドオーバライド時に参照される集合Wに以下のtupleを登録
（key：呼び出し先のメソッドn()、
action：再コンパイル要求、情報：コンパイル中のメソッド名m()）。
else
仮想メソッド呼び出しvに対して、
コード書き換えによる仮想メソッド呼び出しの直接デバーチャル化を適用し、
直接デバーチャル化されたコードと、元のメソッド呼び出しを含むコードを生成する。
/* プログラムPを実行中、メソッドn()がオーバライドされた場合に、
仮想メソッド呼び出しvのデバーチャル化されたコードを無効にするための
コード書き換え要求を出す必要がある。 */
プログラム実行中のメソッドオーバライド時に参照される集合Wに以下のtupleを登録
（key：呼び出し先のメソッドn()、
action：コード書き換え要求、情報：[書き換えアドレスAmv、書き換えコードCmv]）。
endif else
メソッドテストを適用して、間接デバーチャル化されたコードと、
元のメソッド呼び出しを含むコードの両方を生成する。
endif
図 3.12: 仮想メソッド呼び出しのデバーチャル化のコンパイラアルゴリズム
52 第3章 仮想メソッド呼び出しの高速化 プログラムPを実行する。
while TRUE do
if (動的クラスローディングが発生) then C = ロードされたクラス。
クラス階層解析を行う。
if (メソッドオーバライドが発生) then
n = メソッドオーバライドが発生したメソッド。
while (コンパイル時に登録した集合Wに、keyとしてnを含むtupleが存在する) do
T = Wから見つけたtuple。
WからTを除く。
switch T.action do case コード書き換え要求:
/* メソッドT.mに存在するメソッドnの仮想メソッド呼び出しの
コード書き換えを必要とする場合 */
アドレスT.Amvを指定された命令T.Cmvでアトミックに書き換えを行う。
break
case 再コンパイル要求:
/* メソッドnの仮想メソッド呼び出しを含むメソッドT.mが次に呼び出された際に
再コンパイルを必要とする場合 */
メソッドT.mのエントリのネイティブコードを、JITコンパイラを起動するための
スタブへの無条件分岐命令でアトミックに書き換えを行う。
break endswitch endwhile endif
while (コンパイル時に登録した集合Lに、
keyとしてCが実装するインタフェースクラスを含むtupleが存在する) do
T = Lから見つけたtuple。
LからTを除く。
switch T.action do case コード書き換え要求:
/* メソッドT.fに存在するインタフェースメソッド呼び出しの
コード書き換えを必要とする場合 */
アドレスT.Afを指定された命令T.Cfでアトミックに書き換えを行う。
break endswitch endwhile endif endwhile
図 3.13: 仮想メソッド呼び出しのデバーチャル化の実行時アルゴリズム
53
メソッド呼び出し
コード書換による直接デバーチャル化
（制御フロー上の合流点あり）
局所クラス解析による直接デバーチャル化
（制御フロー上の合流点なし）
静的メソッド呼び出し
非静的メソッド呼び出し
デバーチャル化手法
preexistence解析による直接デバーチャル化
（制御フロー上の合流点なし）
インタフェース メソッド呼び出し
メソッドテストによる間接デバーチャル化
（制御フロー上の合流点あり）
仮想メソッド 呼び出し
図 3.14: デバーチャル化手法の適用分類