C语言 为什么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

这是部分答案。

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

ptr类型的漏载没有被消除，因为它被store
打败了，因为它被store
打败了，所以ptr类型的漏载没有被消除，因为它被store
打败了，所以ptr类型的漏载没有被消除，因为它被store
打败了，所以ptr类型的漏载没有被消除。

您可以通过打开"优化输出">

这个优化是由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
}

Answer 2

答案似乎是一个开放的LLVM问题:[TBAA]为不同深度，类型的指针发出不同的TBAA标记。

Jérôme的答案提示我，这可能与基于类型的别名分析(TBAA)有关，当我注意到所有加载使用相同的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和禁用"指令"来看到它们。过滤