1

我正在编写一个编译器，我正在寻找优化资源。我正在编译为机器代码，所以运行时的任何事情都是不可能的。

我最近一直在寻找的是更少的代码优化和更多的语义/高级优化。例如：

free(malloc(400)); // should be completely optimized away

即使这些函数是完全内联的，它们最终也可以调用永远不能内联的操作系统内存函数。我希望能够完全消除该语句，而无需在编译器中构建特殊情况规则（毕竟，malloc它只是另一个函数）。

另一个例子：

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

在这种情况下，我希望能够将b' 的容量初始化为str.Length + 2（足以准确地保存结果，而不会浪费内存）。

老实说，我不知道从哪里开始解决这个问题，所以我希望从某个地方开始。有没有在类似领域做过任何工作？是否有任何编译器在一般意义上实现了类似的东西？

4

2 回答 2

2

要对 2 个或更多操作进行优化，您必须了解这两个操作的代数关系。如果您在他们的问题域中查看操作，他们通常具有这样的关系。

您的 free(malloc(400)) 是可能的，因为 free 和 malloc 在存储分配域中是相反的。许多操作都有逆向，并教导编译器它们是逆向的，并证明一个数据流的结果无条件地流入另一个数据流是需要的。你必须确保你的逆数确实是逆数，并且在某处没有意外；a/x*x 看起来只是值 a，但如果 x 为零，你会得到一个陷阱。如果你不关心陷阱，那就是逆向；如果您确实关心陷阱，那么优化会更复杂： (if (x==0) then trap() else a) 如果您认为除法很昂贵，这仍然是一个很好的优化。

其他“代数”关系也是可能的。例如，可能存在幂等操作：将变量归零（将任何内容重复设置为相同的值）等。有些操作中一个操作数就像一个单位元素；X+0 ==> X 对于任何 0。如果 X 和 0 是矩阵，这仍然是正确的，并且可以节省大量时间。

当您可以抽象地推理代码正在做什么时，可能会发生其他优化。“抽象解释”是一组通过将结果分类到各种有趣的箱中来推理值的技术（例如，这个整数是未知的、零、负的或正的）。为此，您需要确定哪些 bin 有用，然后计算每个点的抽象值。这在对类别进行测试时很有用（例如，“if (x<0) { ... ”并且您抽象地知道 x 小于零；您可以将它们优化掉条件。

另一种方法是象征性地定义计算正在做什么，并模拟计算以查看结果。这就是您计算所需缓冲区的有效大小的方式；您在循环开始之前象征性地计算了缓冲区大小，并模拟了对所有迭代执行循环的效果。为此，您需要能够构建表示程序属性的符号公式，编写此类公式，并在此类公式变得无法使用时经常简化此类公式（有点淡入抽象解释方案）。您还希望这种符号计算考虑到我上面描述的代数属性。做得好的工具擅长构建公式，而程序转换系统通常是这方面的良好基础。DMS 软件再造工具包。

难的是决定哪些优化值得做，因为你可以结束跟踪大量的东西，这可能没有回报。计算机周期越来越便宜，因此在编译器中跟踪代码的更多属性是有意义的。

于 2009-08-27T23:57:11.007 回答
1

Broadway框架可能符合您的要求。关于“源到源转换”的论文可能也会很有启发性。

于 2009-08-27T19:14:26.770 回答