如何识别自动函数提取的类似表达式？

如何识别AST的结构共同子树，以便将它们分解为单独的函数？如何识别自动函数提取的类似表达式？

例如鉴于此伪代码（假设语言只允许纯，终止功能）：

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); }之类的函数的调用，因为指令高速缓存大小嘟m等（或更现实地利用例如一个map或fold基元）。但是，编译器如何将它们识别为相似的，以便将它们视为提取的候选对象？

消除相同子表达式应该很容易，使用类似散列的方式。但是你不能用这个来解决这个问题，因为从树叶向上移动构建的哈希将不会以任何方式相互关联。有没有办法从根节点“建立起来”，并找出两个表达式树之间的分歧点，以查看分支成为参数的位置？（没有使用任何知识的原始程序的形式，其中 - 假设 - 已扩大超出所有承认，并可能不会被最佳分解）通过排序子树和比较邻居来做到这一点，但这需要某种与元素位置无关的排序...？

来源

2014-11-20 Leushenko

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

这篇技术论文（由我）是（上次我看了）关于如何做到这一点的最引用论文：Clone Detection Using Abstract Syntax Trees。

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

来源

2014-11-20 18:05:25

如何识别自动函数提取的类似表达式？

回答

相关问题