编译器优化问题

发布于 2024-07-19 09:17:32 字数 110 浏览 8 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

待天淡蓝洁白时 2024-07-26 09:17:32

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

For 1, The name of the optimization you're looking for is common subexpression elimination (CSE). Depending on your representation, this can be fairly easy. Usually, a compiler will have some intermediate representation of a program where operations are broken down as much as possible and linearized. So for example, the expression c = a * b + a * b might be broken down as:

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

So you could do CSE at a very low level by looking for operations with the same operator and operands. When you encounter a duplicate (v2 in this case), you replace all instances of it with the original. So we could simplify the code above to be:

v1 = a * b
c = v1 + v1

This generally assumes that you only assign each variable once (single static assignment form), but you can implement something like this without that restriction. This gets more complicated when you try and perform this optimization across branches. As Zifre mentions, look into Partial Redundancy Elimination.

Either way, you get some basic improvement, and all you need to keep track of are basic expressions. You may want to take this a step further and look for arithmetic identities. For instance, a * b is the same as b * a. Also, x * (y + z) = x * y + x * z. This makes your optimization more complicated, and it's not clear that it would give you that much performance improvement. Anecdotally, most of the benefit from a CSE optimization comes from address computations like array accesses, and you won't need complicated identities like the ones above.

For 2, what strength reductions are useful really depends on the architecture you compile for. Usually this just involves transforming multiplications and divisions into shifts, additions, and subtractions.

回复收藏 0 原文

猫七 2024-07-26 09:17:32

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

高级编译器设计和编译器设计实现，作者：Steven S. Muchnick
构建优化编译器，作者：Robert Morgan

Muchnick 的书比较正式，但可读性很强，并且对所有重要的优化技术都有很好的描述。摩根的书具有更多的实践感觉，并且将成为专注于优化技术的编译器项目的良好基础。这两本书都没有太多关于词法分析或语法分析的内容，假设您了解这些主题。

回复收藏 0 原文

荒岛晴空 2024-07-26 09:17:32

我相信很多编译器都使用SSAPRE（静态单赋值部分冗余消除）来消除重复的表达式。这要求代码采用SSA 形式，允许更多优化。
我对此不太确定，但请查看此 LLVM 通行证列表。 LLVM 是一种针对编译器的优化 IR，其速度通常比 GCC 还要快。每个通道都有一个小解释。如果您需要更多信息，请查看这些通道的 LLVM 源代码。它是用 C++ 编写的，但非常干净且易于理解。

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

回复收藏 0 原文