拆分算法

本指南概述了 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();
    }
}

在此示例中，一旦 double 函数以字符串参数 "foo" 调用，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 函数的再次拆分。

拆分算法

方法 #

联系我们