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

5 回答 5

6

对于 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，什么强度降低是有用的实际上取决于您编译的架构。通常这只涉及将乘法和除法转换为移位、加法和减法。

于 2009-05-06T00:35:36.287 回答
5

我强烈推荐两个关于这些主题的印刷参考资料：

  1. Steven S. Muchnick 的高级编译器设计与实现
  2. Robert Morgan构建优化编译器

Muchnick 的书是正式的，但可读性很强，并且对所有重要的优化技术都有很好的描述。Morgan 的书具有更多的动手能力，对于专注于优化技术的编译器项目来说，这将是一个很好的基础。这两本书都没有太多关于词法分析或解析的内容，假设您对这些主题有所了解。

于 2009-05-06T00:44:10.930 回答
3

  1. 相信很多编译器都会使用 SSAPRE（Static Single Assignment Partial Redundancy Elimination）来消除重复的表达式。这要求代码采用SSA 形式，允许进行更多优化。

  2. 我不太确定这个，但看看这个 LLVM 通行证列表。LLVM是一种针对编译器的优化 IR，通常比 GCC 还要快。每一关都有一个小的解释。如果您需要更多信息，请查看这些通行证的 LLVM 源代码。它是用 C++ 编写的，但非常简洁易懂。

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

于 2009-05-06T00:27:42.657 回答
1

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

于 2009-05-07T23:05:33.943 回答
0

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

查看Keith Cooper 的讲义，它似乎很好地描述了这些技术。

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

  • 它相当复杂
  • 它需要全局值编号（因此 SSAPRE 不提供值编号，因为它预期已经存在）。
  • 如果您的语言不支持指向堆栈变量的指针，它不会提供任何东西（如果支持，请停止编写您自己的分析并使用 LLVM 或 gcc）。
  • gcc 使用了 HSSA 一段时间，但他们已经远离它。
  • LLVM 对其进行了试验，但 AFAIK 他们不再使用它。

编辑：

Muchnick的书有详细的描述，它链接在另一个答案中。

于 2009-07-30T15:07:12.493 回答