为什么允许gcc从结构中推测性地加载？

Question

显示可能出错的gcc优化和用户代码的示例

下面的代码段中的函数'foo'将只加载一个结构成员A或B; 至少这是未经优化的代码的意图.

typedef struct {
  int A;
  int B;
} Pair;

int foo(const Pair *P, int c) {
  int x;
  if (c)
    x = P->A;
  else
    x = P->B;
  return c/102 + x;
}

这是gcc -O3给出的:

mov eax, esi
mov edx, -1600085855
test esi, esi
mov ecx, DWORD PTR [rdi+4]   <-- ***load P->B**
cmovne ecx, DWORD PTR [rdi]  <-- ***load P->A***
imul edx
lea eax, [rdx+rsi]
sar esi, 31
sar eax, 6
sub eax, esi
add eax, ecx
ret

因此,似乎允许gcc推测性地加载两个结构成员以消除分支.但是,以下代码是否考虑了未定义的行为或者上面的gcc优化是非法的？

#include <stdlib.h>  

int naughty_caller(int c) {
  Pair *P = (Pair*)malloc(sizeof(Pair)-1); // *** Allocation is enough for A but not for B ***
  if (!P) return -1;

  P->A = 0x42; // *** Initializing allocation only where it is guaranteed to be allocated ***

  int res = foo(P, 1); // *** Passing c=1 to foo should ensure only P->A is accessed? ***

  free(P);
  return res;
}

如果在上述情况下发生负载推测,则加载P-> B可能会导致异常,因为P-> B的最后一个字节可能位于未分配的内存中.如果关闭优化,则不会发生此异常.

问题

上面显示的负载推测的gcc优化是否合法？规范在哪里说或暗示它没问题？如果优化是合法的,那么'naughtly_caller'中的代码如何变成未定义的行为？

Answer 1

读取变量(未声明为volatile)不被视为C标准规定的"副作用".因此,就C标准而言,程序可以自由地读取位置然后丢弃结果.

这很常见.假设您从4字节整数请求1字节数据.然后编译器可以读取整个32位,如果它更快(对齐读取),然后丢弃除请求的字节之外的所有内容.您的示例与此类似,但编译器决定读取整个结构.

形式上,这可以在"抽象机器"的行为中找到,C11章5.1.2.3.鉴于编译器遵循那里指定的规则,它可以自由地随意执行.列出的唯一规则是关于volatile对象和指令的顺序.在volatile结构中读取不同的struct成员是不可行的.

至于为整个结构分配太少内存的情况,这是未定义的行为.因为结构的内存布局通常不是由程序员决定的 - 例如,允许编译器在末尾添加填充.如果没有足够的内存分配,即使您的代码仅与结构的第一个成员一起使用,也可能最终访问禁止的内存.

Answer 2

不,如果*P正确分配P->B将永远不会在未分配的内存中.它可能没有初始化,就是全部.

编译器完全有权做他们所做的事情.唯一不允许的是通过P->B它未被初始化的借口来提供访问权限.但是他们做什么以及如何做到这一点取决于实施的自由裁量权而不是你的担忧.

如果你投的指针,通过返回块malloc到Pair*这是不能保证足够宽,能够容纳Pair你的程序的行为是不确定的.

Answer 3

这是完全合法的,因为在一般情况下读取一些内存位置不被视为可观察的行为(volatile会改变这种情况).

您的示例代码确实是未定义的行为,但我在标准文档中找不到明确说明这一点的任何段落.但我认为从N1570,§6.5p6开始,看看有效类型的规则就足够了:

如果通过具有非字符类型的左值的值将值存储到没有声明类型的对象中,则左值的类型将成为该访问的对象的有效类型以及不修改该值的后续访问的有效类型储值.

因此,您的写访问权*P实际上为该对象提供了类型Pair- 因此它只是扩展到您未分配的内存中,结果是超出访问范围.

Answer 4

后缀表达式后跟->运算符和标识符指定结构或联合对象的成员.该值是第一个表达式指向的对象的指定成员的值

如果调用表达式P->A是明确定义的,那么P实际上必须指向一个类型的对象struct Pair,因此P->B也是明确定义的.

Answer 5

a上的->运算符Pair *意味着Pair完整分配了整个对象.(@Hurkyl引用标准.)

x86(与任何普通架构一样)没有访问正常分配内存的副作用,因此x86内存语义与C抽象机器的非volatile内存语义兼容.编译器可以推测性地加载,如果/他们认为这将是他们在任何特定情况下调整的目标微架构的性能胜利.

请注意,在x86上,内存保护以页面粒度运行.只要触摸的所有页面都包含对象的某些字节,编译器就可以以读取对象外部的方式展开循环或向量化SIMD. 在x86和x64上读取同一页面内的缓冲区末尾是否安全？.strlen()在汇编中手工编写的libc 实现可以做到这一点,但是AFAIK gcc没有这样做,而是在自动向量化循环结束时使用标量循环用于剩余元素,即使它已经将指针与(完全展开的)启动循环对齐.(也许是因为它会使运行时边界检查valgrind变得困难.)

要获得您期望的行为,请使用const int *arg.

数组是单个对象,但指针与数组不同.(即使内联到已知两个数组元素都可访问的上下文中,我也无法让gcc像为结构那样发出代码,所以如果它的结构代码是一个胜利,那么它是一个错过的优化而不是在阵列上做它也是安全的.)

在C中,int只要c非零,就允许将此函数传递给单个指针.在为x86进行编译时,gcc必须假设它可以指向int页面中的最后一个,并且以下页面未映射.

Godbolt编译器资源管理器上的此变量和其他变体的源+ gcc和clang输出

// exactly equivalent to  const int p[2]
int load_pointer(const int *p, int c) {
  int x;
  if (c)
    x = p[0];
  else
    x = p[1];  // gcc missed optimization: still does an add with c known to be zero
  return c + x;
}

load_pointer:    # gcc7.2 -O3
    test    esi, esi
    jne     .L9
    mov     eax, DWORD PTR [rdi+4]
    add     eax, esi         # missed optimization: esi=0 here so this is a no-op
    ret
.L9:
    mov     eax, DWORD PTR [rdi]
    add     eax, esi
    ret

在C中,您可以将一个数组对象(通过引用)传递给函数,保证函数允许它接触所有内存,即使C抽象机器没有. 语法是int p[static 2]

int load_array(const int p[static 2], int c) {
  ... // same body
}

但是gcc没有利用,并且向load_pointer发出相同的代码.

关闭主题:clang以相同的方式编译所有版本(struct和array),使用a cmov无分支计算加载地址.

    lea     rax, [rdi + 4]
    test    esi, esi
    cmovne  rax, rdi
    add     esi, dword ptr [rax]
    mov     eax, esi            # missed optimization: mov on the critical path
    ret

这不一定是好的:它具有比gcc的结构代码更高的延迟,因为加载地址依赖于几个额外的ALU uop.如果两个地址都不安全,并且分支预测效果不佳,那就太好了.

我们可以从gcc和clang获得相同策略的更好的代码,使用setcc(除了一些非常古老的CPU之外的所有CPU上的1 uop,1c延迟),而不是cmovcc(在Skylake之前的Intel上2 uop). xor-zeroing总是比LEA便宜.

int load_pointer_v3(const int *p, int c) {
  int offset = (c==0);
  int x = p[offset];
  return c + x;
}

    xor     eax, eax
    test    esi, esi
    sete    al
    add     esi, dword ptr [rdi + 4*rax]
    mov     eax, esi
    ret

gcc和clang都把决赛mov放在关键路径上.在英特尔Sandybridge系列中,索引寻址模式不会与微软融合add.所以这会更好,就像在分支版本中做的那样:

    xor     eax, eax
    test    esi, esi
    sete    al
    mov     eax, dword ptr [rdi + 4*rax]
    add     eax, esi
    ret

与Intel SnB系列CPU上的其他模式相比,简单的寻址模式[rdi]或者[rdi+4]具有1c更低的延迟,因此Skylake实际上可能是更差的延迟(cmov价格便宜).该test和lea可以并行运行.

在内联之后,该决赛mov可能不会存在,而且它可能只是add进入esi.