问题标签 [strength-reduction]

我知道add比mul函数更快。

我想知道如何在下面的代码中使用add而不是mul以提高效率。

示例代码：

我需要在代码的热路径中执行一些整数除法。我已经通过分析和循环计数确定整数除法正在花费我。我希望我能做些什么来加强将师减少到更便宜的东西。

在这条路径中，我除以 2^n+1，其中 n 是可变的。本质上，我想优化此功能以删除除法运算符：

如果我除以 2^n，我只需将 div 替换为右移 n。如果我除以一个常数，我会让编译器的强度降低那个特定的除法，很可能把它变成一个乘法和一些移位。

是否有适用于 2^n+1 的类似优化？

编辑：这里的 a 可以是任意 64 位整数。n 只取 10 到 25 之间的几个值。我当然可以为每个 n 预先计算一些值，但不能为 a。

这个函数（为了方便而用 C 语言编写，但这对问题并不重要）决定了数组的大小。我确信它可以转换为 if-else 链，甚至可以转换为方程，但我不够聪明，不知道如何。（我试图写下明显的 if-else 链，但在某些情况下陷入困境。）

如果有一种通用的、万无一失的技术可以将这种循环转换为算术，那将是一个理想的答案。如果做不到这一点，这个实例的解决方案就可以了。

考虑以下简单的程序（改编自这个问题）：

我相信它在功能上等同于以下一个：

然而clang 3.7.1、gcc 5.3和icc 13.0.1似乎无法进行这样的优化，即使使用-Ofast. （注意生成的程序集在编译器之间是如何大不相同的！）。但是，当从等式中删除mul2和时， clang能够执行类似的优化，即使是.x2-O2

是什么阻止了两个编译器将第一个程序优化为第二个程序？

假设 %edi 包含 x 并且我想仅使用 2 个连续的 leal 指令以 37*x 结束，我该怎么做？

例如，要获得 45 倍，您会这样做

我一生都无法弄清楚用什么数字代替 8 和 4，这样结果 (%eax) 将是 37x

是否有任何示例（例如在https://godbolt.org/上）当使用指针迭代而不是数组索引表示的算法时，CLang 会生成更糟糕的代码？例如，它可以在一种情况下矢量化/展开，但在另一种情况下不能？

在简单的例子中显然没关系。这是一个指针迭代样式：

这是索引样式的逻辑相同的代码：

在这里忽略任何 UB 和/或关闭一个错误。

编辑：关于索引是糖的论点是无关紧要的，因为去糖不会改变算法风格。所以以下基于指针的代码仍然是索引样式：

请注意，基于索引的循环只有 1 个变化变量，而基于指针的循环有 2 个，编译器必须推断它们总是一起变化。

您应该在https://en.wikipedia.org/wiki/Induction_variable和https://en.wikipedia.org/wiki/Strength_reduction的上下文中查看此内容。指针样式本质上是强度降低的索引样式，因为添加被增量替换。这种减少在一段时间内对性能有益，但不再有效。

所以我的问题归结为是否存在编译器无法执行或逆转这种强度降低的情况。

另一种可能的情况是索引不是归纳变量。因此，相应的指针代码包括“任意跳转”，并且由于过去迭代的“历史”，它在某种程度上更难以转换循环。