• 首頁
• 最新
• GraalVM 作為平台
• 語言實作框架
• 分割

分割演算法

本指南概述了 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 相關。最後，如果這發生在呼叫目標的第一次執行期間，則分割沒有意義，因為節點的多型性質是不可避免的（即，不是來自呼叫者，而是該呼叫目標的整體屬性）。

在虛擬程式碼的第二部分中，區分了兩種情況

1) 呼叫目標有多個已知的呼叫者 - 在這種情況下，您可以假設多型來自這些多個呼叫者之一。因此，您將呼叫目標標記為「需要分割」。

2) 呼叫目標只有一個已知的呼叫者 - 在這種情況下，您知道將此呼叫目標標記為「需要分割」無助於消除多型。但是，多型可能從其唯一呼叫者進入此呼叫目標，而該呼叫者可能有多個呼叫者，並且可能是分割的候選者。因此，您會將該演算法遞迴地套用至我們呼叫目標的呼叫者。

現在忽略我們演算法的傳回值及其用途，並考慮以下 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();
    }
}

在此範例中，一旦使用字串引數 "foo" 呼叫 double，則表示 add 函式中 + 的節點將轉變為多型，並且這將回報給執行階段，而且我們的演算法將套用至 add。所有提早回傳檢查都會失敗（add 未標記為「需要分割」，它有已知的呼叫者，而且這不是它的第一次執行）。觀察到 add 只有一個呼叫者 (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 函式的分割。