编译器优化问题

Question

1. 编译器消除重复的子表达式重新计算的方法有哪些？你如何跟踪子表达式？以及如何识别重复的？
2. 除了使用按位运算符之外，常见编译器还使用哪些强度降低技术？

Answer 1

1. 我相信很多编译器都使用SSAPRE（静态单一赋值部分冗余消除）来消除重复的表达式。这要求代码在 SSA表单中，允许更多优化。

2. 我对此不太确定，但请查看此LLVM通行证列表。 LLVM 是编译器的优化IR，通常比GCC更快。每个传球都有一个小的解释。如果您需要更多信息，请查看这些传递的LLVM源。它是用C ++编写的，但非常干净且易于理解。

编辑：顺便说一句，如果您正在开发编译器，我强烈推荐LLVM，它非常易于使用并生成高度优化的代码。

Answer 2

对于1，您正在寻找的优化名称是常见的子表达式消除（CSE）。根据您的表示，这可能相当容易。通常，编译器将具有程序的一些中间表示，其中操作尽可能地被分解并且线性化。例如，表达式 c = a * b + a * b 可能会被细分为：

v1 = a * b
v2 = a * b
c = v1 + v2

因此，您可以通过查找具有相同运算符和操作数的操作来以非常低的级别执行CSE。遇到重复项（在本例中为v2）时，将其所有实例替换为原始实例。所以我们可以将上面的代码简化为：

v1 = a * b
c = v1 + v1

这通常假定您只分配一次变量（单个静态赋值形式），但是您可以在没有该限制的情况下实现这样的操作。当您尝试跨分支执行此优化时，这会变得更加复杂。正如Zifre所提到的那样，请考虑部分冗余消除。

无论哪种方式，您都会得到一些基本的改进，而您需要跟踪的只是基本表达式。您可能希望更进一步，寻找算术身份。例如， a * b 与 b * a 相同。此外， x *（y + z）= x * y + x * z 。这使得您的优化变得更加复杂，并且不太清楚它会给您带来如此多的性能提升。有趣的是，CSE优化的大部分好处来自于数组访问等地址计算，您不需要像上面那样复杂的身份。

对于2，有用的强度降低实际上取决于您编译的体系结构。通常这只涉及将乘法和除法转换为移位，加法和减法。

Answer 3

我强烈推荐这两个主题的两个印刷参考文献：

1. Advanced Compiler Design＆amp;由Steven S. Muchnick执行
2. 由Robert Morgan 构建优化编译器

Muchnick的书是正式的，但是非常易读，并且对所有重要的优化技术都有很好的描述。摩根书籍具有更多动手实践的感觉，并且将成为专注于优化技术的编译器项目的重要基础。这两本书都没有太多关于词汇分析或解析的知识，假设这些科目的知识。

Answer 4

要在建议列表中再添加一本书，请查看“Hacker's Delight” ; 由Henry S. Warren撰写。这是优化常见操作的技术概要，例如将整数除法转换为乘法。

Answer 5

您正在寻找部分冗余消除（PRE）。CSE（来自其他答案）和循环不变代码运动都包含在 PRE 中。（PRE 的一个变体是 Lazy Code Motion，我认为这是最佳的）。

查看 基思·库珀的讲义, ，这似乎很好地描述了这些技术。

做 不是 使用 SSAPRE。AFAIK，这需要一种称为 HSSA 的特殊形式的 SSA，它有一些缺点：

• 它相当复杂
• 它需要全局值编号（因此 SSAPRE 不提供值编号，因为它预计已经存在）。
• 如果您的语言不支持指向堆栈变量的指针，它不会提供任何内容（如果支持，请停止编写自己的分析并使用 LLVM 或 gcc）。
• gcc 使用 HSSA 有一段时间了，但他们已经放弃它了。
• LLVM 尝试过它，但据我所知他们不再使用它了。

编辑：

穆奇尼克的书有详细的描述，它链接在另一个答案中。