分割アルゴリズム

このガイドでは、Truffleコール・ターゲット分割の実装で使用されるアルゴリズムの概要を示します。

新しい実装は、特定のノードが多相になるタイミング、またはインライン・キャッシュへのエントリの追加などによってその多相の程度が高まるタイミングに関する情報を提供する言語実装に依存します。このイベントは多相特殊化と呼ばれます。この情報は、特殊化が完了した後にNode.reportPolymorphicSpecializeメソッドをコールすることによってランタイムに提供されます。

このガイドでは、reportPolymorphicSpecializeのコール後の処理について説明します。多相特殊化を正しくレポートする方法の詳細は、多相のレポート・ガイドを参照してください。

アプローチ

適切な分割候補の検出は、多相特殊化をレポートする言語に依存します。特殊化がレポートされると、多相性は新たな多相ノードをホストするコール・ターゲットのコール元チェーンのどこかから生じていると想定でき、適切なコール・ターゲットを分割することで、このノードを単相状態に戻すことができます。

次に、分割によって単相化が生じる可能性があるコール・ターゲットを特定し、それらを「分割が必要」とマークします。その後の実行中に、「分割が必要」とマークされたコール・ターゲットへの直接コールをインタプリタが実行しようとすると、そのコール・ターゲットは分割されます(ルート・ノードの分割が許可されていない、ASTが大きすぎるなど、それを妨げる目立った要因がない場合)。これにより、クリーン・プロファイル(つまり、そのすべてのノードが初期化されていない状態に戻される)を持つ新しいコール・ターゲットが、このコール・サイト専用に再プロファイルされます。これはこの新しいコール・ターゲットをコールする唯一のコール・サイトであるためです。

次の再帰的アルゴリズム(擬似コードで表現)は、「分割が必要」とマークする必要があるコール・ターゲットを決定するために使用されるアプローチの簡略化されたバージョンです。このアルゴリズムは、そのノードのいずれかが多相特殊化をレポートすると、すべてのコール・ターゲットに適用されます。完全な実装は、com.oracle.truffle.runtime.OptimizedCallTarget#maybeSetNeedsSplitで確認できます。

setNeedsSplit(callTarget)
    if callTarget.needsSplit
        return false
    if sizeof(knownCallers(callTarget)) == 0
        return false
    if callCount(callTarget) == 1
        return false

    if sizeof(knownCallers(callTarget)) > 1
        callTarget.needsSplit = true
    else
        callTarget.needsSplit = setNeedsSplit(caller(callTarget))

    return callTarget.needsSplit

擬似コードの先頭には、早期終了条件を指定できます。コール・ターゲットがすでに「分割が必要」とマークされている場合は、続行する必要があります。また、コール・ターゲットに既知のコール元が存在しない場合(たとえば、それが実行のメインの場合)、分割は本質的に特定のコール・サイトのASTの複製に関連付けられているため、適用されません。最後に、これがコール・ターゲットの最初の実行中に発生している場合、ノードの多相性は避けられないため、分割は無意味です(つまり、コール元ではなく、そのコール・ターゲットの整数プロパティによるものです)。

擬似コードの2つ目の部分では、次の2つのケースが区別されます:

1)コール・ターゲットに既知のコール元が複数あります。この場合、多相性はこれらの複数のコール元のいずれかによるものであると想定できます。したがって、コール・ターゲットを「分割が必要」とマークします。

2)コール・ターゲットの既知のコール元が1つのみです。この場合、このコール・ターゲットを「分割が必要」とマークしても、多相性の排除に役立ちません。ただし、多相性が唯一のコール元からこのコール・ターゲットに到達している可能性があり、これに複数のコール元があり、分割の候補となる可能性があります。したがって、アルゴリズムをコール・ターゲットのコール元に再帰的に適用します。

ここでは、アルゴリズムの戻り値とその使用方法を無視し、次のSimpleLanguageの例を検討して、なぜこのように1つのコール元と複数のコール元を区別する必要があるのかについて説明します:

function add(arg1, arg2) {
    return arg1 + arg2;
}

function double(arg1) {
    return add(arg1, arg1);
}

function callsDouble() {
    double(1);
    double("foo");
}

function main() {
    i = 0;
    while (i < 1000) {
        callsDouble();
    }
}

この例では、文字列引数"foo"を指定してdoubleがコールされると、add関数の+を表すノードが多相になり、これがランタイムにレポートされ、アルゴリズムがaddに適用されます。早期戻りチェックはすべて失敗します(addは「分割が必要」とマークされておらず、既知のコール元があり、これは最初の実行ではありません)。addにはコール元が1つのみ(double)であるため、アルゴリズムをdoubleに適用します。早期戻りはすべて失敗します。doubleには複数のコール元があるため、「分割が必要」とマークし、その後の反復でdoubleのコールが分割されると、次の実行時状態のコード表現になります:

function add(arg1, arg2) {
    return arg1 + arg2; // + is polymorphic
}

function double(arg1) {
    return add(arg1, arg1);
}

function doubleSplit1(arg1) {
    return add(arg1, arg1);
}

function doubleSplit2(arg1) {
    return add(arg1, arg1);
}

function callsDouble() {
    doubleSplit1(1);
    doubleSplit2("foo");
}

function main() {
    i = 0;
    while (i < 1000) {
        callsDouble();
    }
}

ご覧のとおり、多相性のソースは分割されましたが、両方のスリットで同じadd関数がコールされ、多相性が残っているため、問題は解決されませんでした。ここで、アルゴリズムの戻り値が役立ちます。アルゴリズムがマークするターゲットの検出に成功した場合、そのターゲットのすべての推移的なコール先も「分割が必要」とマークする必要があります。この最後のステップを実行すると、前述の例の分割アプローチの最終実行時結果は次のソース・コードとして表すことができます:

function add(arg1, arg2) {
    return arg1 + arg2; // + is polymorphic
}

function addSplit1(arg1, arg2) {
    return arg1 + arg2;

}
function addSplit2(arg1, arg2) {
    return arg1 + arg2;
}

function double(arg1) {
    return add(arg1, arg1);
}

function doubleSplit1(arg1) {
    return addSplit1(arg1, arg1);
}

function doubleSplit2(arg1) {
    return addSplit2(arg1, arg1);
}

function callsDouble() {
    doubleSplit1(1);
    doubleSplit2("foo");
}

function main() {
    i = 0;
    while (i < 1000) {
        callsDouble();
    }
}

最後に、この時点で気付くのは、分割によって元のコール・ターゲットが削除されることなく、プロファイルに多相性が残っていることです。したがって、これらのコール・ターゲットへの新しいコールが作成された場合でも、それらは分割されます。前述の例のmainが次のようになっているかどうかを確認します。

function main() {
    i = 0;
    while (i < 1000) {
        callsDouble();
    }
    add(1,2); // this line was added
}

実行が新しく追加された行に到達した後、ここでの引数は多相を表すものではないため、多相+を指定してadd関数をコールしないようにします。幸いにも、addはすでに「分割が必要」とマークされているため、実行全体においてその状態が維持され、この最後のaddのコールによってadd関数がさらに分割されます。