问题标签 [loop-unrolling]

在为布尔数组编写“不等式扫描”的过程中，我最终编写了这个循环：

我观察到的是 gcc 会展开 s=s*2 循环，但不会展开 s=s+s 循环。这有点不直观，因为加法的循环计数分析应该比 IMO 更简单。我怀疑 gcc 确实知道 s=s+s 循环计数，只是有点害羞。

有谁知道 gcc 的这种行为是否有充分的理由？我是出于好奇问这个...

[展开的版本，顺便说一句，运行速度比循环慢一点。]

谢谢，罗伯特

我有一个内部带有开关的循环，看起来像这样（但要复杂得多）。

ConstVal 在编译时未知，但在初始化例程期间已修复。有没有办法在不编译 for 循环的多个变体的情况下删除 switch 语句？鉴于 x86 具有间接分支，应该有一种简单的方法来内联汇编以跳转到我想要的情况，而不是每次迭代都回到循环的顶部。你会怎么做（在 gcc 中）？最后，能否在不干扰编译器优化分析的情况下做到这一点。我已经在手动展开循环，但我确信还有很多我不想破坏的优化正在进行。

据我了解，Julia 元编程功能使您可以访问解析器和抽象语法树。结合 JIT，您可以解决此类问题。我认为即使没有间接分支的语义，C 中也会有一些合理的解决方法。请注意，Duff 的设备不是解决方案，因为我想在每次循环迭代时返回相同的 case 语句。这个问题经常出现。

编辑

我发现没有条件间接分支 x86 指令。此外，gcc 内联汇编只允许固定标签。然而，使用 gcc 扩展，这仍然可以完成。例如，参见https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html#Labels-as-Values。

就是这样。在我的代码中，很难确定是否存在任何性能差异，但在另一台机器上或使用更小更简单的循环时，它可能会有所不同。

我已经用我自己的基于 gcc 扩展的实现替换了 for 循环，它可以访问机器级间接分支。有几种方法可以做到这一点。第一个是索引一个数组，该数组根据循环索引跳转到循环的条件开始或循环结束。另一种方法（注释）是每次有条件地设置分支寄存器。编译器应使用条件移动 (CMOV) 替换任何分支。

此解决方案存在许多明显的问题。(1) 不便携。(2) 通过自己实现循环，不仅代码更难理解，而且可能会干扰编译器优化（例如自动循环展开）。(3) 即使没有中断，编译器也无法联合优化整个 switch 语句，因为它在编译时不知道哪些语句将实际执行。但是，它可能能够以类似于其他人在下面的一些回复中指出的方式巧妙地重新组织开关。通过自己手动实现开关（结合 for 循环），我使编译器更难以进行任何此类优化，因为通过删除开关语义，我的意图被优化所掩盖。

尽管如此，如果它显着提高了性能，我仍然认为这比拥有多个代码副本要好。使用宏，可以有条件地编译不可移植的扩展；这基本上可以看起来像一个正常的循环。

编辑 2

我找到了一个更好的解决方案，它更便携、更有效。当您遇到可能的运行时确定选项数量较少的情况时，您可以围绕优化函数进行包装，修复所有运行时常量，然后为每个常量副本内联函数。如果只有一个常量，您可以使用函数指针查找表，每个指针设置常量并内联函数。如果您有更复杂的情况，您将需要一些 if-elseif-else 控制结构。其中一个函数可以保留所有自由变量，因此不失一般性。我认为这是一种编译时闭包。编译器正在完成所有艰苦的工作，没有任何凌乱的宏或其他重复的代码需要维护。

在我的代码中，这导致已经显着优化的代码的性能提高了 10% 到 20%（由于对各种常量进行了硬编码，而与开关本身没有任何关系）。在我的玩具示例中，更改看起来像这样。

通过内联 __foo，编译器将消除开关以及您传递的任何其他常量。当然，你最终会得到更多的编译代码，但对于一个小的优化例程来说，这应该没什么大不了的。

我制作了一个程序来展开循环并测量它对数组进行排序所花费的时间，但我遇到的问题是，有时展开的循环程序在纳秒内给我一个 0 的答案，而这是不可能的。我也用 MONOTONIC 试过，但没有帮助。这是我的代码：

我对编写特定类型的数值算法的代码风格有一个想法，您可以纯粹以与数据布局无关的方式编写算法。

即，您的所有函数都采用（一个或多个）标量参数，并（通过指针）返回一个或多个标量返回值。因此，例如，如果您有一个采用 3d 浮点向量的函数，而不是采用具有三个成员的结构或 float[3] xyz，您采用 float x、float y、float z。

这个想法是您可以更改输入和输出数据的布局，即您可以使用数组结构与结构数据布局的数组、缓存效率的平铺布局、SIMD 与多核粒度等...无需为所有数据布局组合重写所有代码。

该策略有一些明显的缺点：

• 你不能在你的函数中使用 for 循环来使你的代码更紧凑
• 您的函数在其签名中需要更多参数

...但是如果您的数组很短，这些都是可口的，并且它可以让您不必多次重写代码以使其快速。

但特别是，我担心编译器可能无法接受像 x+=a; 这样的东西。y+=b; z+=c; w+=d 并将其自动矢量化为单个 SIMD 向量添加，如果您想在调用堆栈的底部执行 SIMD，而不是在内联函数堆栈的顶部执行 SIMD。

clang 和/或 gcc 是否能够在 C 和/或 C++ 代码中“重新滚动”手动展开的循环（可能在内联函数之后）并生成矢量化机器代码？

我需要强制 Metal 编译器在我的内核计算函数中展开一个循环。到目前为止，我已尝试将其置于循环#pragma unroll(num_times)之前for，但编译器会忽略该语句。

似乎编译器不会自动展开循环 - 我比较了 1) 代码与for循环 2) 相同代码但手动展开循环的执行时间。手动展开的版本快 3 倍。

例如：我想从这个开始：

对此：

在 Metal C++ 语言中甚至有类似循环展开的东西吗？如果是，我怎么可能让编译器知道我想展开循环？

我想通过使用展开循环来优化我的代码。我试图应用展开，但我认为我做不到，我看不到我的问题。我想将展开循环应用于外循环。

这个循环做矩阵的转置。

这是我应用展开循环的循环：

这是我的展开循环：

似乎该部分Unroll Loops下的优化设置在Apple LLVM 8.0 - Code Generation最新的 XCode 8.2.1 中默认关闭，即使对于Release配置也是如此。有什么好的理由吗？我认为循环展开是最基本的优化之一。

我有许多 C 源代码文件，我想在这些文件上执行某种类型的静态分析。首先，我需要摆脱控制流图中的任何循环，为此我使用以下单行代码：

我想知道生成的字节码是否target.bc仍然包含一些循环，例如因为无法使用给定的参数展开它。

一种选择是使用llvm-dis，将结果解析为控制流图，然后检查是否存在任何循环。

但是，我想避免重新发明轮子并使用现有的命令行工具。

问：您能指点我其中一个这样的工具，以及如何使用它吗？

#pragma unroll遇到指令时，我们对 nvcc 的展开能力了解多少？它有多复杂？有没有人尝试过越来越复杂的循环结构来看看它放弃了什么？

例如，

肯定会展开（达到相当大的行程计数，请参阅此答案）。关于什么：

循环行程计数在这里是未知的，但它有一个恒定的上限，并且可以执行循环的完全展开，并带有一些条件跳转。

然后，怎么样：

哪个应该编译成与上面相同的东西？

注意：如果您打算回答“进行自己的实验”，那么 - 我打算这样做，至少在我的示例中，如果没有人知道一般答案，请查看 PTX，在这种情况下，我将部分回答这个问题。但我更喜欢更权威和基于更广泛经验的东西。

我想知道是否展开这个循环：

进入

将在自动矢量化方面帮助编译器。

我可以想象它无论如何都会对第一个循环进行矢量化。但是，明确的帮助吗？