为什么Clang在这里不愿意或无法消除重复的加载

5
请看以下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) 直接将x分配给foo,并将foo分配给xs(任何顺序)。 (B)xs执行一次地址计算,并将其用于分配foox
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


2
如果gcc进行了优化,那么最有可能的解释是这种优化是合法的,而clang只是错过了它。 - Nate Eldredge
我正在开发一个玩具编译器,很好奇为什么clang/llvm会错过它。在LLVM IR级别上,转换看起来非常简单,在我的实际代码中,第二个参数foo不存在 - 相反,我使用malloc,所以我知道它是noalias(由于这不影响问题,我已经删除了malloc)。 - Maciej Goszczycki
@NateEldredge:请注意,优质的编译器应该在能够证明所有情况下都是安全的情况下才会尝试进行优化。虽然很容易制作出玩具示例,其中优化可以被证明是安全的,但大多数简单的规则来识别可以证明优化是安全的情况并不适用于足够“现实世界”的代码,并且不值得一试。 - supercat
@supercat,我认为根据C规范和Nate的说法,优化是“可靠的”。LLVM开发人员似乎也认为更严格的分析可能会有所不同。当然,问题在于很容易意外违反C的别名模型。 - Maciej Goszczycki
@MaciejGoszczycki:当操作以源代码所示的方式表达时,分析可能是正确的,但在执行优化之前,高质量的编译器还必须确保相同的操作序列不能由先前的优化传递生成,这些传递了优化不正确的代码。与尝试优化晦涩的情况相比,更好的做法是努力找出更好的抽象模型,以确保代码不会被一个传递转换为另一个传递将其视为调用UB的代码。 - supercat
2个回答

2
这是一个部分答案。
由于优化器错过了优化,因此需要执行两次负载。它成功检测到了这种特定情况,但未能通过报告以下错误来实现:

未命中-指针类型的负载未被消除,因为它被存储所覆盖
未命中-指针类型的负载未被消除,因为它被存储所覆盖
未命中-指针类型的负载未被消除,因为它被存储所覆盖
未命中-指针类型的负载未被消除,因为它被存储所覆盖

您可以通过在Godbolt中打开“优化输出”窗口来查看。
这个优化是由LLVM中的全局值编号(GVN)传递执行的,特定的错误似乎是从函数reportMayClobberedLoad报告的。该代码说明未命中的负载消除是由于干预存储(再次)导致的。要了解更多信息,必须深入研究此优化传递的算法。一个很好的开始似乎是GVNPass :: AnalyzeLoadAvailability函数。幸运的是,代码有注释。
请注意,默认情况下,简化的Foo **用例进行了优化,而简化的Foo ***用例未经优化,但使用restrict可以修复错过的优化(看起来优化器错误地认为别名问题可能会由于存储而出现)。
我想知道这是否是由于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
}

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
}

编译器资源管理器Playground

* 编译器资源管理器的LLVM IR视图默认会过滤掉这些内容,但你可以使用-emit-llvm参数并禁用“指令”过滤来查看它们。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接