编译器优化问题

Question

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

Answer 1

对于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 2

我强烈推荐这些主题的两个印刷参考:

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

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

Answer 3

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

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

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