高级/语义优化

Question

我在写一个编译器，我正在寻找资源上的优化。我编译成机器代码，所以在运行什么是不可能的。

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

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

即使这些功能完全内联，他们最终可能会调用的无法被内联OS记忆功能。我很想能够完全消除这种说法没有建立特殊情况的规则到编译器（毕竟，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能力（足够容纳准确的结果，而不会浪费内存）。

要完全诚实的，我不知道在哪里解决这个问题就要开始了，所以我希望的地方开始。已经有过在类似领域所做的任何工作？是否有已经在一般意义上实现这样的事任何编译器？

Answer 1

要在2个或多个操作做了优化，你必须了解 这两个操作的代数关系。如果您查看操作 在他们的问题域，它们往往有这样的关系。

您免费（malloc的（400））是可能的，因为自由和malloc的是逆 在存储分配域。 操作很多有逆和教学编译器，他们是逆， 并表明一个数据流的结果无条件地进入其他， 是需要什么。你必须确保你的逆真的是逆 并没有一个惊喜的地方; A / X * X看起来像刚刚值， 但如果x为零你得到一个陷阱。如果你不关心的陷阱，它是一个逆; 如果你对陷阱护理则优化更为复杂：       （如果（X == 0），则阱（）否则一） 这仍然是一个很好的优化，如果你认为鸿沟是昂贵的。

其他“代数的”关系是可能的。例如，有 可以幂等操作：归零变量（进行任何设置为相同 值反复），等有业务，其中一个操作行为 像标识元件; X + 0 ==> X为任何0。如果X和0是矩阵， 这仍然是真实的和节省大的时间。

可能会出现其他优化的时候可以对代码什么抽象推理 是在做。 “抽象解释”是推理一组技术 由结果分类成各种有趣仓（例如，该整数值 是未知的，零，负的或正的）。要做到这一点，你需要决定什么 垃圾桶是有帮助的，然后计算各点的抽象价值。这是非常有用 当存在于类别的测试（例如，“如果（X <0）{...”你知道 抽象地x是小于0;你可以将它们优化掉条件。

另一种方法是定义什么是计算是象征性做，并模拟计算才能见分晓。那你是怎么计算所需的缓冲区的有效大小;你计算缓冲区的大小象征性的循环开始前， 和模拟执行循环的各个版本的效果。 为此，您需要能够构建象征性的公式 表示节目的属性，构成这样的公式，并经常简化 这样的公式，当他们得到unusably复杂（种淡入淡出抽象成 解释方案）。你也想这样的符号计算考虑 帐户余上述代数性质。工具，做好这一点善于构建公式和程序转换系统往往是这个良好的基础。一个源到源程序变换系统，可以用来做这个 是 DMS软件再造工具包。

什么是难是决定哪些优化是值得做的，因为你可以结束 保持跟踪的大量的东西，这可能不还清。计算机周期 越来越便宜，所以它是有意义的在编译器跟踪代码的多个属性。

Answer 2

在百老汇框架可能是在静脉你要寻找的。上的“源极 - 到 - 源极转换”的论文将可能也有启发性的。