为什么clang不愿意或者不能消除这里的重复加载

Question

考虑以下 C 程序：

typedef struct { int x; } Foo;

void original(Foo***** xs, Foo* foo) {
    xs[0][1][2][3] = foo;
    xs[0][1][2][3]->x = 42;
}

据我了解，根据 C 标准 Foo** 不能别名 Foo* 等，因为它们的类型不兼容。使用 clang 14.0 和 -O3 编译程序会导致重复加载：

    mov     rax, qword ptr [rdi]
    mov     rax, qword ptr [rax + 8]
    mov     rax, qword ptr [rax + 16]
    mov     qword ptr [rax + 24], rsi
    mov     rax, qword ptr [rdi]
    mov     rax, qword ptr [rax + 8]
    mov     rax, qword ptr [rax + 16]
    mov     rax, qword ptr [rax + 24]
    mov     dword ptr [rax], 42
    ret

我希望优化编译器能够：

(A) 直接赋值给 foo 上的 x 并将 foo 赋值给 xs（顺序任意）
(B) 对 xs 进行一次地址计算，并将其用于分配 foo 和 x.

Clang 正确编译 B:

void fixed(Foo***** xs, Foo* foo) {
    Foo** ix = &xs[0][1][2][3];
    *ix = foo;
    (*ix)->x = 42;
}

如下：（实际变成A）

    mov     rax, qword ptr [rdi]
    mov     rax, qword ptr [rax + 8]
    mov     rax, qword ptr [rax + 16]
    mov     qword ptr [rax + 24], rsi
    mov     dword ptr [rsi], 42
    ret

有趣的是 gcc 将这两个定义编译成 A。为什么clang不愿意或者不能优化original定义中的地址计算？

Compiler Explorer Playground

Answer 1

这是部分答案。

加载被执行了两次，因为优化器错过了优化。它成功检测到这种特定情况，但因报告以下错误而失败：

Missed - load of type ptr not eliminated in favor of load because it is clobbered by store
Missed - load of type ptr not eliminated because it is clobbered by store
Missed - load of type ptr not eliminated because it is clobbered by store
Missed - load of type ptr not eliminated because it is clobbered by store

在Godbolt中打开“优化输出”可以看到window

此优化由 LLVM 中的全局值编号 (GVN) 传递执行，具体错误似乎是从函数 reportMayClobberedLoad. The code states that the missed load-elimination is due to an intervening store (again). For more information, one certainly need to delve into the algorithm of this optimization pass. A good start seems to be the GVNPass::AnalyzeLoadAvailability 函数中报告的。还好代码有注释

注意一个简化的Foo** use-case被优化了，一个简化的Foo*** use-case默认没有优化，但是使用restrict修复了missed-optimization（看起来优化器错误地认为由于商店，别名可能是这里的一个问题）。

我想知道这是否可能是由于 LLVM-IR 似乎没有区分 Foo** 或 Foo*** 指针类型：它们显然都被视为原始指针.因此，存储转发优化可能会失败，因为存储可能会影响链的任何指针，并且由于别名（本身由于指针类型丢失），优化器无法知道是哪一个。这是生成的 LLVM-IR 代码：

define dso_local void @original(ptr nocapture noundef readonly %0, ptr noundef %1) local_unnamed_addr #0 !dbg !9 {
  call void @llvm.dbg.value(metadata ptr %0, metadata !24, metadata !DIExpression()), !dbg !26
  call void @llvm.dbg.value(metadata ptr %1, metadata !25, metadata !DIExpression()), !dbg !26
  %3 = load ptr, ptr %0, align 8, !dbg !27, !tbaa !28
  %4 = getelementptr inbounds ptr, ptr %3, i64 1, !dbg !27
  %5 = load ptr, ptr %4, align 8, !dbg !27, !tbaa !28
  %6 = getelementptr inbounds ptr, ptr %5, i64 2, !dbg !27
  %7 = load ptr, ptr %6, align 8, !dbg !27, !tbaa !28
  %8 = getelementptr inbounds ptr, ptr %7, i64 3, !dbg !27
  store ptr %1, ptr %8, align 8, !dbg !32, !tbaa !28
  %9 = load ptr, ptr %0, align 8, !dbg !33, !tbaa !28
  %10 = getelementptr inbounds ptr, ptr %9, i64 1, !dbg !33
  %11 = load ptr, ptr %10, align 8, !dbg !33, !tbaa !28
  %12 = getelementptr inbounds ptr, ptr %11, i64 2, !dbg !33
  %13 = load ptr, ptr %12, align 8, !dbg !33, !tbaa !28
  %14 = getelementptr inbounds ptr, ptr %13, i64 3, !dbg !33
  %15 = load ptr, ptr %14, align 8, !dbg !33, !tbaa !28
  store i32 42, ptr %15, align 4, !dbg !34, !tbaa !35
  ret void, !dbg !38
}

Answer 2

答案似乎是一个开放的 LLVM 问题：[TBAA] Emit distinct TBAA tags for pointers with different depths,types.

当我注意到所有加载都使用相同的 TBAA 元数据时，Jérôme 的回答提示我这可能与基于类型的别名分析 (TBAA) 有关。

现在 clang 只发出 ^* 以下 TBAA:

; Descriptors
!15 = !{!"Simple C/C++ TBAA"}
!14 = !{!"omnipotent char", !15, i64 0}
!13 = !{!"any pointer", !14, i64 0}
!21 = !{!"int", !14, i64 0}
!20 = !{!"", !21, i64 0}
; Tags
!12 = !{!13, !13, i64 0}
!19 = !{!20, !21, i64 0}

查看 LLVM 修订版，我认为最终 clang 可能会发出类似以下内容的内容：

; Type descriptors
!0 = !{!"TBAA Root"}
!1 = !{!"omnipotent char", !0, i64 0}
!3 = !{!"int", !0, i64 0}
!2 = !{!"any pointer", !1, i64 0}
!11 = !{!"p1 foo", !2, i64 0} ; Foo*
!12 = !{!"p2 foo", !2, i64 0} ; Foo**
!13 = !{!"p3 foo", !2, i64 0} ; Foo***
!14 = !{!"p4 foo", !2, i64 0} ; Foo****
!10 = !{!"foo", !3, i64 0} ; struct {int x}

; Access tags
!20 = !{!14, !14, i64 0} ; Foo****
!21 = !{!13, !13, i64 0} ; Foo***
!22 = !{!12, !12, i64 0} ; Foo**
!23 = !{!11, !11, i64 0} ; Foo*
!24 = !{!10, !3, i64 0}  ; Foo.x

（我仍然不确定我是否完全理解 TBAA 元数据格式，所以请原谅任何错误）

与下面的 LLVM 代码一起生成预期的程序集。

define void @original(ptr %0, ptr %1) {
  %3 = load ptr, ptr %0, !tbaa !20
  %4 = getelementptr ptr, ptr %3, i64 1
  %5 = load ptr, ptr %4, !tbaa !21
  %6 = getelementptr ptr, ptr %5, i64 2
  %7 = load ptr, ptr %6, !tbaa !22
  %8 = getelementptr ptr, ptr %7, i64 3
  store ptr %1, ptr %8, !tbaa !23

  %9 = load ptr, ptr %0, !tbaa !20
  %10 = getelementptr ptr, ptr %9, i64 1
  %11 = load ptr, ptr %10, !tbaa !21
  %12 = getelementptr ptr, ptr %11, i64 2
  %13 = load ptr, ptr %12, !tbaa !22
  %14 = getelementptr ptr, ptr %13, i64 3
  %15 = load ptr, ptr %14, !tbaa !23 ; : Foo*
  store i32 42, ptr %15, !tbaa !24

  ret void
}

Compiler Explorer Playground

* 编译器的资源管理器 LLVM IR 视图默认过滤掉这些，但您可以通过使用 -emit-llvm 并禁用“指令”过滤来查看它们

为什么clang不愿意或者不能消除这里的重复加载

Why is clang unwilling or unable to eliminate duplicate loads here

c

optimization

clang

llvm

strict-aliasing