compiler-construction - 自动抽取函数如何识别相似表达式？

Question

如何识别 AST 的结构公共(public)子树，以便将它们分解为单独的函数？

例如给出这个伪代码(假设该语言只允许纯终止函数):

f(a, b, c) {
    return (a + b) * c * 6;
}

g(x[4], k) {
    var y[4];
    for (i in 0..3)
        y[i] = f(x[i], 1, k);
    return y;
}

varying arr[4];
result = g(arr, 1);

...在完全特化和内联之后，我们最终会得到以下表示程序结果值的原始操作树:

(make-vec4
    (* (arr 0) 6)
    (* (+ (arr 1) 1) 6)
    (* (+ (arr 2) 1) 6)
    (* (+ (arr 3) 1) 6) )

(这是一个糟糕的例子，因为扩展后的结果在结构上仍然与输入非常相似……尽管假设更改可以传播到输入代码的结构边界)

对于人眼来说，很明显结果树包含三个相似的表达式，我们现在可以将它们重构为对函数的调用，例如 fn(i) { return 6 * (arr[i] + 1); }，因为instruction cache size mumble mumble etc(或者更现实地利用例如map或fold原语)。但是编译器如何将它们识别为相似的，以便将它们视为提取的候选对象？

消除相同 子表达式应该很容易，使用诸如散列运算之类的东西。但是你不能用它来解决这个问题，因为通过从叶子向上移动构建的散列不会以任何方式相互关联。有没有办法从根节点“向下构建”并确定两个表达式树之间的分歧点，以查看分支在何处成为参数？ (没有使用原始程序形式的任何知识，假设 - 已经扩展到无法识别的范围，并且无论如何可能没有被最佳分割)

感觉应该有某种方法可以通过排序子树和比较邻居来做到这一点，但这需要某种与元素位置无关的排序......？

Answer 1

你要做的就是所谓的“克隆检测”。您特别想要做的是检测抽象语法树上的克隆。

这篇技术论文(由我撰写)是(我上次查看时)关于如何执行此操作的引用次数最多的论文:Clone Detection Using Abstract Syntax Trees .

有一种基于这种方法的商业工具，称为 CloneDR。