分割アルゴリズム

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

新しい実装では、特定のノードが多形になる場合、またはたとえばインラインキャッシュにエントリを追加することで多形性の「度合い」が増加する場合に、言語実装から情報を提供することを前提としています。このイベントは「多形特殊化」と呼ばれます。この情報は、特殊化が完了した後にNode.reportPolymorphicSpecializeメソッドを呼び出すことでランタイムに提供されます。

このガイドでは、reportPolymorphicSpecializeの呼び出し後に何が起こるかを説明します。多形特殊化を正しく報告する方法の詳細については、多形性の報告ガイドを参照してください。

アプローチ #

適切な分割候補の検出は、言語が多形特殊化を報告することに依存しています。特殊化が報告されると、多形性はコールターゲットの呼び出しチェーンのどこかから来ており、適切なコールターゲット（またはコールターゲット）を分割することで、このノードを単態状態に戻すことができると想定できます。

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

次の再帰アルゴリズム（擬似コードとして表現）は、「分割が必要」とマークする必要があるコールターゲットを決定するために使用されるアプローチの簡略化されたバージョンです。このアルゴリズムは、そのノードの1つが多形特殊化を報告すると、すべてのコールターゲットに適用されます。完全な実装は、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) コールターゲットに複数の既知の呼び出し元がある場合 - この場合、多形性はこれらの複数の呼び出し元の1つから来ていると仮定できます。したがって、コールターゲットを「分割が必要」としてマークします。

2) コールターゲットに既知の呼び出し元が1つしかない場合 - この場合、このコールターゲットを「分割が必要」としてマークしても、多形性を解消できないことがわかっています。しかし、多形性は、複数の呼び出し元があり、分割の候補となる可能性のある唯一の呼び出し元から、このコールターゲットに入力されている可能性があります。したがって、コールターゲットの呼び出し元にアルゴリズムを再帰的に適用します。

現時点ではアルゴリズムの戻り値とその使用方法を無視し、この1つと複数の呼び出し元の区別が必要な理由を説明するSimpleLanguageの例を検討してください。

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();
    }
}

この例では、add関数内の+を表すノードは、doubleが文字列引数"foo"で呼び出されると多形になり、これがランタイムに報告され、アルゴリズムが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関数の別の分割が発生します。

分割アルゴリズム

アプローチ #

お問い合わせ