为什么（无限）递归在 clang 和 w/o -O3（和 gcc/g++）中给出不同的结果？
Why does (infinite) recursion give different results with and w/o -O3 in clang (and gcc/g++)?
当我编译 运行 这段代码时
#include <stdio.h>
int collatz(int a) {
return a == 1 ? 1 : collatz((a%2) ? 3*a+1 : a/2);
}
int main() {
for (int a = 0; a < 10; ++a)
printf("%d: %d\n", a, collatz(a));
}
在 clang (10.0.0-4ubuntu1) 中它崩溃了，但是当我添加 -O3 时它 运行 没问题。 （当将其作为 C 或 C++ 代码传递给 clang 时，这两者都成立。）
我知道它在没有优化标志的情况下崩溃，因为用 0 调用 collatz 会导致无限递归。但是，-O3 是 returns 0: 1，这是错误的。这是优化中的（已知）错误还是我遗漏了什么？
(gcc/g++ (9.3.0) 也没有优化就崩溃，编译挂起 -O3。)
编辑：只是补充一点，我不是在寻找程序挂起/失败的原因（很明显），而是为什么编译器显然可以自由 return 一些值，而程序不应该 return （而是进入无限循环）。
编辑 2：为什么我没有选择一个更简单的例子？好吧，就是这样，这给出了相同的行为
int divide(int i) {
return i == 1 ? 1 : divide(i/2);
}
Is that a (known) bug in the optimization or am I missing something?
这不是优化中的错误。这是正在编译的程序中的错误。该程序的行为在 C++ 中未定义。
it returns 0: 1, which is wrong
当程序的行为未定义时，不存在“错误”行为。
but the compilation hangs with -O3
这可能是一个编译器错误。
how can the compiler just decide to return something, whereas, if you follow the program logic, it should not.
当程序的行为未定义时，编译器可以决定做任何事情或什么都不做。没有什么特别应该做或不应该做的。未定义的程序没有逻辑。
why the behaviour is undefined
C++ 标准说：
[intro.progress]
The implementation may assume that any thread will eventually do one of the following:
- terminate,
- make a call to a library I/O function,
- perform an access through a volatile glvalue, or
- perform a synchronization operation or an atomic operation.
如果参数为 0，线程将永远不会做任何这些事情，因此允许 [语言] 实现假定永远不会使用参数 0 调用该函数。当您调用具有此类参数的函数，您与此假设相矛盾，并且行为未定义。
注意：我的答案只在 C 中是正确的。正如在 C++ 中的其他答案中所说，程序中有 UB。这是您不应使用 C++ 编译器编译 C 代码的原因之一。
我试图通过godbolt获取clang 10.0.0生成的程序集。我知道不是每个人都知道如何阅读汇编，所以我会尽量简洁地解释我们可以从列表中推断出什么。这是我生成的：
与clang -S main.c:
collatz(int):
push {r11, lr}
mov r11, sp
sub sp, sp, #16
str r0, [r11, #-4]
ldr r0, [r11, #-4]
cmp r0, #1
bne .LBB0_2
b .LBB0_1
.LBB0_1:
mov r0, #1
str r0, [sp, #8] @ 4-byte Spill
b .LBB0_6
.LBB0_2:
ldr r0, [r11, #-4]
add r1, r0, r0, lsr #31
bic r1, r1, #1
sub r0, r0, r1
cmp r0, #0
beq .LBB0_4
b .LBB0_3
.LBB0_3:
ldr r0, [r11, #-4]
add r0, r0, r0, lsl #1
add r0, r0, #1
str r0, [sp, #4] @ 4-byte Spill
b .LBB0_5
.LBB0_4:
ldr r0, [r11, #-4]
add r0, r0, r0, lsr #31
asr r0, r0, #1
str r0, [sp, #4] @ 4-byte Spill
b .LBB0_5
.LBB0_5:
ldr r0, [sp, #4] @ 4-byte Reload
bl collatz(int)
str r0, [sp, #8] @ 4-byte Spill
b .LBB0_6
.LBB0_6:
ldr r0, [sp, #8] @ 4-byte Reload
mov sp, r11
pop {r11, lr}
bx lr
main:
push {r11, lr}
mov r11, sp
sub sp, sp, #16
mov r0, #0
str r0, [r11, #-4]
str r0, [sp, #8]
b .LBB1_1
.LBB1_1: @ =>This Inner Loop Header: Depth=1
ldr r0, [sp, #8]
cmp r0, #9
bgt .LBB1_4
b .LBB1_2
.LBB1_2: @ in Loop: Header=BB1_1 Depth=1
ldr r0, [sp, #8]
str r0, [sp, #4] @ 4-byte Spill
bl collatz(int)
ldr r1, .LCPI1_0
str r0, [sp] @ 4-byte Spill
mov r0, r1
ldr r1, [sp, #4] @ 4-byte Reload
ldr r2, [sp] @ 4-byte Reload
bl printf
b .LBB1_3
.LBB1_3: @ in Loop: Header=BB1_1 Depth=1
ldr r0, [sp, #8]
add r0, r0, #1
str r0, [sp, #8]
b .LBB1_1
.LBB1_4:
ldr r0, [r11, #-4]
mov sp, r11
pop {r11, lr}
bx lr
.LCPI1_0:
.long .L.str
.L.str:
.asciz "%d: %d\n"
在这里，事情看起来很正常，函数已定义，它的行为看起来没问题，循环在 main 中正确形成，所以正如我们所料，当它调用 collatz(0) 时，堆栈溢出。
与clang -S -O3 main.c:
collatz(int):
mov r0, #1
bx lr
main:
push {r4, r10, r11, lr}
add r11, sp, #8
ldr r4, .LCPI1_0
mov r1, #0
mov r2, #1
mov r0, r4
bl printf
mov r0, r4
mov r1, #1
mov r2, #1
bl printf
mov r0, r4
mov r1, #2
mov r2, #1
bl printf
mov r0, r4
mov r1, #3
mov r2, #1
bl printf
mov r0, r4
mov r1, #4
mov r2, #1
bl printf
mov r0, r4
mov r1, #5
mov r2, #1
bl printf
mov r0, r4
mov r1, #6
mov r2, #1
bl printf
mov r0, r4
mov r1, #7
mov r2, #1
bl printf
mov r0, r4
mov r1, #8
mov r2, #1
bl printf
mov r0, r4
mov r1, #9
mov r2, #1
bl printf
mov r0, #0
pop {r4, r10, r11, lr}
bx lr
.LCPI1_0:
.long .L.str
.L.str:
.asciz "%d: %d\n"
铿锵到这里彻底醉了。它确实像我们预期的那样优化了循环，但它出于某种原因决定 collatz(0) = 1 并且它编译了一个 very 奇怪的 collatz 版本，只是从不调用它。你可能会说 clang 是一个 C++ 编译器，所以它做意想不到的事情是有意义的，但事实并非如此，clang 将自己宣传为“Clang C、C++ 和 Objective-C 编译器”。对我来说，这是一个编译器错误。让我们尝试使用 clang 12.0.1 以防错误在更高版本中得到解决。
使用最新版本clang -S -O3 main.c:
.text
.file "main.c"
.globl collatz # -- Begin function collatz
.p2align 4, 0x90
.type collatz,@function
collatz: # @collatz
.cfi_startproc
# %bb.0:
# kill: def $edi killed $edi def $rdi
cmpl , %edi
jne .LBB0_2
jmp .LBB0_5
.p2align 4, 0x90
.LBB0_3: # in Loop: Header=BB0_2 Depth=1
leal (%rdi,%rdi,2), %edi
addl , %edi
cmpl , %edi
je .LBB0_5
.LBB0_2: # =>This Inner Loop Header: Depth=1
testb , %dil
jne .LBB0_3
# %bb.4: # in Loop: Header=BB0_2 Depth=1
movl %edi, %eax
shrl , %eax
addl %edi, %eax
sarl %eax
movl %eax, %edi
cmpl , %edi
jne .LBB0_2
.LBB0_5:
movl , %eax
retq
.Lfunc_end0:
.size collatz, .Lfunc_end0-collatz
.cfi_endproc
# -- End function
.globl main # -- Begin function main
.p2align 4, 0x90
.type main,@function
main: # @main
.cfi_startproc
# %bb.0:
.p2align 4, 0x90
.LBB1_1: # =>This Inner Loop Header: Depth=1
jmp .LBB1_1
.Lfunc_end1:
.size main, .Lfunc_end1-main
.cfi_endproc
# -- End function
.ident "clang version 12.0.1"
.section ".note.GNU-stack","",@progbits
.addrsig
这里，main 函数由一个 while(1) 循环组成，这是我们在给定输入时所期望的。
总而言之，我认为 gcc 和 clang 10.0.0 都有一个错误，尽管一个比另一个更容易被视为错误
当我编译 运行 这段代码时
#include <stdio.h>
int collatz(int a) {
return a == 1 ? 1 : collatz((a%2) ? 3*a+1 : a/2);
}
int main() {
for (int a = 0; a < 10; ++a)
printf("%d: %d\n", a, collatz(a));
}
在 clang (10.0.0-4ubuntu1) 中它崩溃了，但是当我添加 -O3 时它 运行 没问题。 （当将其作为 C 或 C++ 代码传递给 clang 时，这两者都成立。）
我知道它在没有优化标志的情况下崩溃，因为用 0 调用 collatz 会导致无限递归。但是，-O3 是 returns 0: 1，这是错误的。这是优化中的（已知）错误还是我遗漏了什么？
(gcc/g++ (9.3.0) 也没有优化就崩溃，编译挂起 -O3。)
编辑：只是补充一点，我不是在寻找程序挂起/失败的原因（很明显），而是为什么编译器显然可以自由 return 一些值，而程序不应该 return （而是进入无限循环）。
编辑 2：为什么我没有选择一个更简单的例子？好吧，就是这样，这给出了相同的行为
int divide(int i) {
return i == 1 ? 1 : divide(i/2);
}
Is that a (known) bug in the optimization or am I missing something?
这不是优化中的错误。这是正在编译的程序中的错误。该程序的行为在 C++ 中未定义。
it returns 0: 1, which is wrong
当程序的行为未定义时，不存在“错误”行为。
but the compilation hangs with -O3
这可能是一个编译器错误。
how can the compiler just decide to return something, whereas, if you follow the program logic, it should not.
当程序的行为未定义时，编译器可以决定做任何事情或什么都不做。没有什么特别应该做或不应该做的。未定义的程序没有逻辑。
why the behaviour is undefined
C++ 标准说：
[intro.progress]
The implementation may assume that any thread will eventually do one of the following:
- terminate,
- make a call to a library I/O function,
- perform an access through a volatile glvalue, or
- perform a synchronization operation or an atomic operation.
如果参数为 0，线程将永远不会做任何这些事情，因此允许 [语言] 实现假定永远不会使用参数 0 调用该函数。当您调用具有此类参数的函数，您与此假设相矛盾，并且行为未定义。
注意：我的答案只在 C 中是正确的。正如在 C++ 中的其他答案中所说，程序中有 UB。这是您不应使用 C++ 编译器编译 C 代码的原因之一。
我试图通过godbolt获取clang 10.0.0生成的程序集。我知道不是每个人都知道如何阅读汇编，所以我会尽量简洁地解释我们可以从列表中推断出什么。这是我生成的：
与clang -S main.c:
collatz(int):
push {r11, lr}
mov r11, sp
sub sp, sp, #16
str r0, [r11, #-4]
ldr r0, [r11, #-4]
cmp r0, #1
bne .LBB0_2
b .LBB0_1
.LBB0_1:
mov r0, #1
str r0, [sp, #8] @ 4-byte Spill
b .LBB0_6
.LBB0_2:
ldr r0, [r11, #-4]
add r1, r0, r0, lsr #31
bic r1, r1, #1
sub r0, r0, r1
cmp r0, #0
beq .LBB0_4
b .LBB0_3
.LBB0_3:
ldr r0, [r11, #-4]
add r0, r0, r0, lsl #1
add r0, r0, #1
str r0, [sp, #4] @ 4-byte Spill
b .LBB0_5
.LBB0_4:
ldr r0, [r11, #-4]
add r0, r0, r0, lsr #31
asr r0, r0, #1
str r0, [sp, #4] @ 4-byte Spill
b .LBB0_5
.LBB0_5:
ldr r0, [sp, #4] @ 4-byte Reload
bl collatz(int)
str r0, [sp, #8] @ 4-byte Spill
b .LBB0_6
.LBB0_6:
ldr r0, [sp, #8] @ 4-byte Reload
mov sp, r11
pop {r11, lr}
bx lr
main:
push {r11, lr}
mov r11, sp
sub sp, sp, #16
mov r0, #0
str r0, [r11, #-4]
str r0, [sp, #8]
b .LBB1_1
.LBB1_1: @ =>This Inner Loop Header: Depth=1
ldr r0, [sp, #8]
cmp r0, #9
bgt .LBB1_4
b .LBB1_2
.LBB1_2: @ in Loop: Header=BB1_1 Depth=1
ldr r0, [sp, #8]
str r0, [sp, #4] @ 4-byte Spill
bl collatz(int)
ldr r1, .LCPI1_0
str r0, [sp] @ 4-byte Spill
mov r0, r1
ldr r1, [sp, #4] @ 4-byte Reload
ldr r2, [sp] @ 4-byte Reload
bl printf
b .LBB1_3
.LBB1_3: @ in Loop: Header=BB1_1 Depth=1
ldr r0, [sp, #8]
add r0, r0, #1
str r0, [sp, #8]
b .LBB1_1
.LBB1_4:
ldr r0, [r11, #-4]
mov sp, r11
pop {r11, lr}
bx lr
.LCPI1_0:
.long .L.str
.L.str:
.asciz "%d: %d\n"
在这里，事情看起来很正常，函数已定义，它的行为看起来没问题，循环在 main 中正确形成，所以正如我们所料，当它调用 collatz(0) 时，堆栈溢出。
与clang -S -O3 main.c:
collatz(int):
mov r0, #1
bx lr
main:
push {r4, r10, r11, lr}
add r11, sp, #8
ldr r4, .LCPI1_0
mov r1, #0
mov r2, #1
mov r0, r4
bl printf
mov r0, r4
mov r1, #1
mov r2, #1
bl printf
mov r0, r4
mov r1, #2
mov r2, #1
bl printf
mov r0, r4
mov r1, #3
mov r2, #1
bl printf
mov r0, r4
mov r1, #4
mov r2, #1
bl printf
mov r0, r4
mov r1, #5
mov r2, #1
bl printf
mov r0, r4
mov r1, #6
mov r2, #1
bl printf
mov r0, r4
mov r1, #7
mov r2, #1
bl printf
mov r0, r4
mov r1, #8
mov r2, #1
bl printf
mov r0, r4
mov r1, #9
mov r2, #1
bl printf
mov r0, #0
pop {r4, r10, r11, lr}
bx lr
.LCPI1_0:
.long .L.str
.L.str:
.asciz "%d: %d\n"
铿锵到这里彻底醉了。它确实像我们预期的那样优化了循环，但它出于某种原因决定 collatz(0) = 1 并且它编译了一个 very 奇怪的 collatz 版本，只是从不调用它。你可能会说 clang 是一个 C++ 编译器，所以它做意想不到的事情是有意义的，但事实并非如此，clang 将自己宣传为“Clang C、C++ 和 Objective-C 编译器”。对我来说，这是一个编译器错误。让我们尝试使用 clang 12.0.1 以防错误在更高版本中得到解决。
使用最新版本clang -S -O3 main.c:
.text
.file "main.c"
.globl collatz # -- Begin function collatz
.p2align 4, 0x90
.type collatz,@function
collatz: # @collatz
.cfi_startproc
# %bb.0:
# kill: def $edi killed $edi def $rdi
cmpl , %edi
jne .LBB0_2
jmp .LBB0_5
.p2align 4, 0x90
.LBB0_3: # in Loop: Header=BB0_2 Depth=1
leal (%rdi,%rdi,2), %edi
addl , %edi
cmpl , %edi
je .LBB0_5
.LBB0_2: # =>This Inner Loop Header: Depth=1
testb , %dil
jne .LBB0_3
# %bb.4: # in Loop: Header=BB0_2 Depth=1
movl %edi, %eax
shrl , %eax
addl %edi, %eax
sarl %eax
movl %eax, %edi
cmpl , %edi
jne .LBB0_2
.LBB0_5:
movl , %eax
retq
.Lfunc_end0:
.size collatz, .Lfunc_end0-collatz
.cfi_endproc
# -- End function
.globl main # -- Begin function main
.p2align 4, 0x90
.type main,@function
main: # @main
.cfi_startproc
# %bb.0:
.p2align 4, 0x90
.LBB1_1: # =>This Inner Loop Header: Depth=1
jmp .LBB1_1
.Lfunc_end1:
.size main, .Lfunc_end1-main
.cfi_endproc
# -- End function
.ident "clang version 12.0.1"
.section ".note.GNU-stack","",@progbits
.addrsig
这里，main 函数由一个 while(1) 循环组成，这是我们在给定输入时所期望的。
总而言之，我认为 gcc 和 clang 10.0.0 都有一个错误，尽管一个比另一个更容易被视为错误