为什么 memcmp(a, b, 4) 只有在某些情况下才会优化成 uint32 比较？

Question

考虑以下代码：

#include <string.h>

int equal4(const char* a, const char* b)
{
    return memcmp(a, b, 4) == 0;
}

int less4(const char* a, const char* b)
{
    return memcmp(a, b, 4) < 0;
}

GCC 7 在 x86_64 上引入了一个优化（Clang 长期以来一直有）：

    mov     eax, DWORD PTR [rsi]
    cmp     DWORD PTR [rdi], eax
    sete    al
    movzx   eax, al

但是第二种情况仍然调用了memcmp()函数:

    sub     rsp, 8
    mov     edx, 4
    call    memcmp
    add     rsp, 8
    shr     eax, 31

第二种情况能否应用类似的优化？对于这种情况，最好的汇编代码是什么？是否有任何明显的原因导致 GCC 或 Clang 没有执行这个操作？

在 Godbolt 的编译器浏览器上查看：https://godbolt.org/g/jv8fcf

- John Zwinck

---

我觉得有趣的是对齐的随意忽略；这在x86上可能有效，但在其他CPU上优化可能无效。 - Matthieu M.

@MatthieuM. 它只需要在目标架构上有效即可。 - Caleth

@Caleth：同意，但这让我想知道转换在哪个阶段完成。也就是说，gcc是否在其中间端（可能是抽象的）中使用目标特定的优化，或者它是降低的一部分。 - Matthieu M.

你可以通过添加 -fdump-tree-all -fdump-rtl-all 编译参数来获得更多信息（除了其他的开关）。这将在每个优化阶段后将中间表示内容转储到当前工作目录中的文件中，编号以便您可以按顺序阅读它们。(如果这样做，您将获得大约 300 个文件。"树" 转储比 "RTL" 转储更容易阅读。在尝试阅读 RTL 转储之前，您可能需要简略地浏览一下"内部手册"中的 "RTL" 和 "机器描述" 章节。) - zwol

Answer 1

如果你为一个小端平台生成代码，将四字节的memcmp优化为单个DWORD比较不正确。

当memcmp比较单个字节时，它会从低地址字节到高地址字节进行，无论平台如何。

为了使memcmp返回零，所有四个字节必须相同。因此，比较的顺序并不重要。因此，DWORD优化是有效的，因为你忽略结果的符号。

然而，当memcmp返回正数时，字节顺序很重要。因此，使用32位DWORD比较实现相同的比较需要特定的字节序：平台必须是大端，否则比较结果将不正确。

- Sergey Kalinichenko

---

x86中有一个bswap指令，ARM则使用rev指令。不过多了一个指令。 - MSalters

正如 dasblinkenlight 指出的那样，这足以区分 <0 和 >0。从算术上讲，CMP 寻找最高有效位差异，而 memcmp 按内存顺序查找第一个不同的字节。在大端系统中，第一个字节保存 MSB。bswap 将本机小端比特模式转换为大端，这就是原因。 - MSalters

@Kevin: 无论如何，您都不希望交换内存中的字节（然后恢复它们）！最佳汇编语言可能类似于：将两个4B块加载到寄存器中，并且在两者之间进行字节交换。因此，对于解码器来说，这需要额外的指令，并需要额外的融合域uops才能发出，因为您不能像“== 0”情况那样使用内存操作数进行cmp。例如，mov edi，[rdi] /mov esi，[rsi] / bswap edi / bswap esi / cmp edi，esi / seta和movzx。这些都是所有最新的Intel和AMD CPU上的单uop指令（http://agner.org/optimize/）。 - Peter Cordes

@Kevin和const-correct只适用于源代码。只要最终结果相同，CPU可以随意操作。 - OrangeDog

@BeeOnRope，你假设写入主内存，然而CPU仍然可以在内部执行任何操作。 - OrangeDog

Answer 2

这里的问题在于字节序。考虑以下输入：

a = 01 00 00 03
b = 02 00 00 02

如果您将这两个数组视为32位整数进行比较，则会发现a更大（因为0x03000001> 0x02000002）。在大端机器上，此测试可能会按预期工作。

- r3mainer

---

没错，但问题是如何优化掉memcmp()调用。在比较之前可以通过发出字节交换指令来完成这一操作，对吧？ - John Zwinck

我认为针对这个问题进行字节交换是处理一个非常特殊的情况，编译器编写者不会费心去处理它。 - Ruslan

编译器中充满了这样的小优化；我相信编译器开发人员会很乐意收到覆盖此问题的补丁......如果它确实有效。 - Matthieu M.

@MatthieuM.：如果在实际代码中很重要，您可以使用endian.h或类似的字节交换函数获取两个uint32_t整数进行比较，从当前编译器中获得更好的结果。请参见我的答案以获取示例。但是，如果编写可移植代码，则必须担心错误对齐加载等问题，因此如果您可以使用memcmp比较未知对齐的大端整数并获得最佳代码就太好了。 - Peter Cordes

Answer 3

正如其他答案/评论中所讨论的那样，使用 memcmp(a,b,4) < 0 相当于在大端整数之间进行无符号比较。在小端 x86 上，它不能像 == 0 那样高效地内联。

更重要的是，gcc7/8版本中这种行为仅查找memcmp() == 0或!= 0。即使在大端目标平台上，这种行为对于<或>也可以像内联一样有效，但gcc也不会这样做。（Godbolt的最新大端编译器是PowerPC 64 gcc6.3和MIPS/MIPS64 gcc5.4。mips是大端MIPS，而mipsel是小端MIPS。）如果使用未来的gcc进行测试，请使用a = __builtin_assume_align(a, 4)确保gcc不必担心非x86上的非对齐加载性能/正确性。（或者只需使用const int32_t*而不是const char*。）

如果/当gcc学会内联memcmp处理除了EQ/NE之外的情况，也许gcc在启发式告诉它额外的代码大小值得时，会在小端x86上执行。例如，在使用-fprofile-use（基于性能剖析的优化）编译时的热循环中。

---

如果您想编译器能够在这种情况下做得很好，您应该分配给一个uint32_t并使用类似ntohl的字节序转换函数。但请确保选择一个可以实际内联的函数; 显然Windows有一个将编译为DLL调用的ntohl。请参阅该问题的其他答案以获取一些可移植字节序内容，并查看某人不完美的portable_endian.h尝试，以及此其分支。我曾经研究过一个版本，但从未完成/测试或发布它。

将指针强制转换为const uint32_t*将导致未定义的行为，如果这些字节不是对齐的uint32_t或通过char*写入。 如果您对严格别名和/或对齐方式不确定，请使用memcpy到abytes或使用GNU C属性：有关解决方法，请参见另一个关于对齐和严格别名的Q&A。 大多数编译器都很擅长优化小型固定大小的memcpy。

// I know the question just wonders why gcc does what it does,
// not asking for how to write it differently.
// Beware of alignment performance or even fault issues outside of x86.

#include <endian.h>
#include <stdint.h>

static inline
uint32_t load32_native_endian(const void *vp){
   typedef uint32_t unaligned_aliasing_u32 __attribute__((aligned(1),may_alias));
   const unaligned_aliasing_u32 *up = vp;
   return *up;   // #ifndef __GNUC__  then use memcpy
}


int equal4_optim(const char* a, const char* b) {
    uint32_t abytes = load32_native_endian(a);
    uint32_t bbytes = load32_native_endian(b);

    return abytes == bbytes;
}


int less4_optim(const char* a, const char* b) {
    uint32_t a_native = be32toh(load32_native_endian(a));
    uint32_t b_native = be32toh(load32_native_endian(b));

    return a_native < b_native;
}

我在Godbolt上检查了一下，它编译出高效的代码（基本上与我下面写的汇编代码相同），尤其是对于大端平台和旧版本的gcc。它还比ICC17生成更好的代码，后者虽然内联了memcmp，但只是一个字节比较循环（即使是== 0的情况也是如此）。

---

我认为这个手工序列是实现less4()的最佳方式（适用于x86-64 SystemV调用约定，例如在问题中使用，其中const char *a在rdi中，b在rsi中）。

less4:
    mov   edi, [rdi]
    mov   esi, [rsi]
    bswap edi
    bswap esi
    # data loaded and byte-swapped to native unsigned integers
    xor   eax,eax    # solves the same problem as gcc's movzx, see below
    cmp   edi, esi
    setb  al         # eax=1 if *a was Below(unsigned) *b, else 0
    ret

这些都是自K8和Core2以来英特尔和AMD CPU上的单操作指令 (http://agner.org/optimize/)。

与== 0情况相比，必须对两个操作数执行bswap会增加额外的代码大小成本：我们无法将其中一个加载折叠到cmp的内存操作数中。(这可以节省代码大小和uops，因为微聚合。) 这还要加上两个额外的bswap指令。

在支持movbe的CPU上，它可以节省代码大小：movbe ecx，[rsi]是一种加载+ bswap。 在Haswell上，它是2个uops，因此可能解码为与mov ecx，[rsi] / bswap ecx相同的uops。 在Atom / Silvermont上，它直接处理在加载端口中，因此不仅uops更少而且代码大小更小。

查看我的异或清零答案中的setcc部分，了解为什么 xor/cmp/setcc（clang 使用）比 cmp/setcc/movzx（gcc 典型用法）更好。

在通常情况下，当这个代码嵌入到根据结果进行分支的代码中时，setcc+零扩展会被替换为jcc；编译器会优化掉在寄存器中创建布尔返回值的步骤，这是内联的另一个优点：库函数memcmp不需要创建整数布尔返回值，因为没有x86 ABI/调用约定允许在标志位中返回布尔条件（我也不知道有哪些非x86调用约定可以实现）。对于大多数库函数memcmp实现来说，选择策略的开销也很大，可能还要检查对齐方式。这可能很便宜，但对于大小为4的情况来说，其成本将超过所有实际工作的总和。

- Peter Cordes

---

我稍微研究了一下 GCC 的源代码。这种优化是由tree-ssa-strlen.c中名字有些不准确的handle_builtin_memcmp实现的。如果我没看错的话，它只实现了 == 和 != 两种情况：如果比较不是 EQ_EXPR 或 NE_EXPR，则在第 2102-3 行和 2108-9 行的检查导致它不执行任何操作，这意味着它只处理相等和不相等的情况。稍后，如果 !SLOW_UNALIGNED_ACCESS (mode, align)，即“我们能进行此加载而不担心对齐吗？”，也会导致它退出。 - zwol

@zwol：谢谢！我并不惊讶这个新功能的第一个实现只处理==/!=比较。真遗憾没有真正可移植的字节序函数，这会使得在编译器友好的方式下编写less4变得容易，而不需要一堆#ifdef。 - Peter Cordes

顺便提一下，别名规则是不对称的：char * 可以与任何类型别名，但 int * 官方上是不能与 char 别名的，至少在 char 被声明为 char 的情况下是如此；参见 https://dev59.com/-F0Z5IYBdhLWcg3w4jdy - zwol

值得一提的是，可移植代码库中有一个endian模块，似乎在这方面做得相当不错（就像库中的其他部分一样），而且质量很高，也在积极维护。 - BeeOnRope

Answer 4

字节序是一个问题，但有符号字符是另一个问题。例如，考虑你要比较的四个字节是0x207f2020和0x20802020。作为有符号字符的80是-128，7f是+127。但如果你比较这四个字节，没有任何比较会给出正确的顺序。

当然，你可以使用0x80808080进行异或，然后只需使用无符号比较即可。

- gnasher729

---

无论char是否有符号，使用memcmp进行比较时都需要将其视为unsigned char。 - user743382