是否存在重复n次而不计算某些条件的循环构造？

Question

这个问题出现在优化代码以消除潜在分支预测失败的上下文中...事实上，一起删除分支。

在我的示例中，典型的For循环使用以下语法：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main()
{
    bool *S = calloc(N + 1, sizeof(bool));
    int p = 2;
    for (int i = p * p; i <= N; i += p)
        S[i] = 1;

    return 0;
}

据我所知，生成的汇编代码将包含某种JMP指令来检查i是否

我能想到在汇编中这样做的唯一方法是重复相同的汇编指令n次，每次重复i都会递增。然而，对于大的n，产生的二进制文件将是巨大的。

所以，我想知道，是否有循环构造可以重复n次而不计算一些条件？




Answer 1

完全展开是唯一实用的方法，您是对的，它不适用于大量迭代计数（通常不适用于迭代计数不是编译时常量的循环）。它非常适合具有已知迭代计数的小循环。

对于您的特定情况，在给定的距离上将内存设置为1，x86具有rep stosb，它在微码中实现了memset。它不会在当前Intel CPU上遭受分支错误预测，因为微码分支无法预测/推测执行并停止（或其他），这意味着它在进行任何存储之前有大约15个周期的启动开销。请参阅REP做什么设置？对于大型对齐缓冲区，rep stosb/d/q非常接近优化的AVX循环。

因此，您不会出现预测失误，但您确实会获得固定的启动开销。（我认为这会阻碍指令的发出/执行，因为微码序列器会在发出所有UOP之前接管前端。而且在执行之前，微码序列器无法知道何时发出指令。一些查看rcx的指令会按顺序发出。因此，直到>rep stos（代表stos）确定要发布的UOP。存储不必执行，但微码分支可以执行。）Icelake应该有“快速short REP MOV”，这可能最终解决启动开销问题。可能通过为rep-mov和rep-stos添加专用硬件状态机，就像@KrazyGlew在设计Intel P6 uarch（ppro/PII/PIII）中的快速字符串时所希望的那样，当前Intel CPU的前身仍然使用非常类似的微码实现。AFAIK和AMD类似，但我还没有看到他们的rep-Sto启动开销的数字或细节。

大多数体系结构都没有这样的单一指令集，因此x86在计算机体系结构中绝对是一个特例。但一些旧电脑（如Atari ST）可能有一个“blitter”芯片来卸载拷贝内存，尤其是用于图形目的。他们将使用DMA与CPU单独进行复制。这与在芯片上构建硬件状态机来运行rep-movs非常相似。

考虑一个正常的阿斯姆循环，比如

.looptop:                do {
    # loop body includes a pointer increment
    # may be unrolled some to do multiple stores per conditional branch
    cmp   rdi, rdx
    jb    .looptop       } while(dst < end_dst);

在循环运行了一段时间后，分支最终会得到强烈的预测。

对于大的迭代次数，一个分支错误预测会在所有循环迭代中摊销，并且通常可以忽略不计。（循环底部的条件分支被预测为被占用，因此循环分支错误预测了一次它没有被占用。）

一些分支预测器对循环分支有特殊的支持，带有一个模式预测器，可以对模式进行计数，如执行30次/未执行。由于最大迭代次数的一些较大限制，他们可以正确预测。

或者现代TAGE预测器（如英特尔Sandybridge系列）使用分支历史来索引条目，因此它“自然地”为您提供一些模式预测。例如，在我的测试中，Skylake正确预测了内部循环的循环退出分支，最多可进行大约22次迭代。（当有一个简单的外部循环以相同的迭代次数重复重新运行内部循环时。）我在ash而不是C中进行了测试，因此我可以控制完成了多少展开。

一个中等长度的循环太长而无法正确预测退出是最坏的情况。例如，如果它是一个内部循环，在无法预测的CPU上重复运行约30次迭代，则它足够短，以至于经常发生对循环退出的错误预测。

上次迭代中一次错误预测的成本可能相当低。如果乱序执行可以“看到”一个简单的循环计数器的几个迭代，它可以在花费大量时间在错误预测的分支之外的实际工作之前执行分支本身。通过快速恢复分支未命中（而不是使用分支顺序缓冲区之类的东西来刷新整个乱序管道），您仍然会在循环后的几个周期内失去开始独立工作的机会。如果循环在依赖链的延迟上遇到瓶颈，但计数器本身是一个单独的链，则最有可能出现这种情况。这篇关于分支失误的真实成本的论文也很有趣，并提到了这一点。

（请注意，我假设分支预测已经“准备就绪”，因此第一次迭代可以正确地预测所执行的循环分支。）

不切实际的方式：

@哈迪提出了一个有趣的想法：与其正常运行代码，不如以一种奇怪的方式进行编译，其中控制和指令都是数据，例如x86只使用带有x86寻址模式寄存器的mov指令。（以及一个大块底部的无条件分支）。有没有可能在大会上不使用“jump”和“goto”来做决定？这非常低效，但实际上没有任何条件分支：一切都是数据依赖。

它使用不同形式的MOV（寄存器之间、寄存器立即数以及加载/存储），因此它不是一台单指令集计算机。

另一个不那么疯狂的版本是解释器：被解释代码中的不同指令/操作在解释器中变成了控制依赖关系（为解释器带来了难以解决的效率问题，请参阅Darek Mihocka的“重新审视通用CPU解释器循环”但是来宾代码中的数据和控制流都是解释器中的数据。来宾程序计数器只是解释器中的另一段数据。