拆分算法

本指南概述了 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

在伪代码的开头，您可以设置提前终止条件。如果调用目标已标记为“需要拆分”，则无需继续。此外，如果调用目标没有已知的调用者（例如，它是执行的“main”），则拆分不适用，因为拆分本质上与为特定调用站点复制 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();
    }
}

在此示例中，表示 add 函数中 + 的节点将在 double 使用字符串参数 "foo" 调用时变为多态，这将被报告给运行时，我们的算法将应用于 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 函数的另一次拆分。

拆分算法

方法 #

与我们联系