llvm学习（二十四）：表情包引发的悬案，浅谈编译器优化

Posted on Edited on In

前言

某日在群里看到这张很怪的表情包，想着这不是扯淡么，一看到运行结果顿时傻眼了。。。

尝试复现

1
2
3
4
5
6
7
#include <stdio.h>
int main(){
    while(1) ;
}
void unreachable(){
    printf("HelloWorld\n");
}

先放一个在线编译C代码的网站：https://godbolt.org/

编译选项 结果
gcc全版本 -O0/O1/O2 死循环
g++全版本 -O0/O1/O2 死循环
clang（C语言） 全版本 -O0/O1/O2 死循环
clang++（C++） >= 13.0.0 -O0 死循环
clang++（C++） >= 13.0.0 -O1/O2 打印并正常退出

初步结果：只有在比较新的C++上才会触发，稳定复现，因此选定 clang++ test.cpp -O1 作为目标进行研究。

分析问题引入位置

objdump/gdb 误入歧途

通过 objdump -d a.out 可以看到，_start 函数直接调用了 unreachable 函数。（一口盐汽水就喷了在屏幕上。。。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Disassembly of section .text:

0000000000001050 <_start>:
    1050:       f3 0f 1e fa             endbr64
    1054:       31 ed                   xor    %ebp,%ebp
    1056:       49 89 d1                mov    %rdx,%r9
    1059:       5e                      pop    %rsi
    105a:       48 89 e2                mov    %rsp,%rdx
    105d:       48 83 e4 f0             and    $0xfffffffffffffff0,%rsp
    1061:       50                      push   %rax
    1062:       54                      push   %rsp
    1063:       45 31 c0                xor    %r8d,%r8d
    1066:       31 c9                   xor    %ecx,%ecx
    1068:       48 8d 3d d1 00 00 00    lea    0xd1(%rip),%rdi        # 1140 <_Z11unreachablev>
    106f:       ff 15 6b 2f 00 00       call   *0x2f6b(%rip)        # 3fe0 <__libc_start_main@GLIBC_2.34>
    1075:       f4                      hlt
    1076:       66 2e 0f 1f 84 00 00    cs nopw 0x0(%rax,%rax,1)

gdb 调试，很诡异，也直接就断在了 unreachable 里，说明二进制确实执行到了这里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
gdb a.out
(gdb) b main
Breakpoint 1 at 0x1140
(gdb) r
Starting program: /tmp/a.out
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, 0x0000555555555140 in unreachable() ()
(gdb) disassemble $pc
Dump of assembler code for function _Z11unreachablev:
=> 0x0000555555555140 <+0>:     push   %rax
   0x0000555555555141 <+1>:     lea    0xebc(%rip),%rdi        # 0x555555556004
   0x0000555555555148 <+8>:     call   0x555555555030 <puts@plt>
   0x000055555555514d <+13>:    pop    %rax
   0x000055555555514e <+14>:    ret
End of assembler dump.
(gdb)

什么？还有程序没有main、从别的函数开始执行？这连接器是抽什么风？

readelf 初见端倪

说实话，我还是第一次见到 “没有main函数、但是能运行” 的程序，于是查看符号表，发现main函数还在，和unreachable指向同一个偏移，但函数大小为0

1
2
3
4
5
6
7
8
9
readelf -s a.out
Symbol table '.symtab' contains 37 entries:
  Num:    Value          Size Type    Bind   Vis      Ndx Name
  22: 0000000000001140     0 FUNC    GLOBAL DEFAULT   15 main
  23: 0000000000001140    15 FUNC    GLOBAL DEFAULT   15 _Z11unreachablev

objdump -t a.out
0000000000001140 g     F .text  0000000000000000              main
0000000000001140 g     F .text  000000000000000f              _Z11unreachablev

也就是说，main函数的函数体被清空了，恰好指向了unreachable的位置，“越界”执行了下一个函数的代码。

查看汇编

clang++ -c -S test.cpp -O1 得到 test.s 汇编文件。 我去掉了汇编大部分不必要的注释，但故意保留了一部分，才能让读者知道，他读的是汇编 。可以看到，main函数里一条指令都没有，全部都是点开头的或者井号开头的注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
        .globl  main                            # -- Begin function main
        .p2align        4, 0x90
        .type   main,@function
main:                                   # @main
        .cfi_startproc
# %bb.0:
.Lfunc_end0:
        .size   main, .Lfunc_end0-main
        .cfi_endproc
                                        # -- End function

        .globl  _Z11unreachablev                # -- Begin function _Z11unreachablev
        .p2align        4, 0x90
        .type   _Z11unreachablev,@function
_Z11unreachablev:                       # @_Z11unreachablev
        .cfi_startproc
# %bb.0:
        pushq   %rax
        leaq    .Lstr(%rip), %rdi
        callq   puts@PLT
        popq    %rax
        retq

去除全部注释后就是，main 和 _Z11unreachablev 指向同一段汇编代码：

1
2
3
4
5
6
7
main:                                   # @main
_Z11unreachablev:                       # @_Z11unreachablev
        pushq   %rax
        leaq    .Lstr(%rip), %rdi
        callq   puts@PLT
        popq    %rax
        retq

查看IR

clang++ -emit-llvm -S -c test.cpp -O1 得到 test.ll IR文件。可以看出，确实在IR阶段main的内容就发生了变换，由原先的死循环被替换成了 unreachable。注意，这个unreachable是一条名叫UnreachableInstruction的指令，并非函数名

1
2
3
4
; Function Attrs: mustprogress nofree norecurse noreturn nosync nounwind readnone uwtable willreturn
define dso_local noundef i32 @main() local_unnamed_addr #0 {
  unreachable
}

对比 -O0 的输出结果。

1
2
3
4
5
6
7
8
9
; Function Attrs: mustprogress noinline norecurse nounwind optnone uwtable
define dso_local noundef i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  br label %2

2:                                                ; preds = %0, %2
  br label %2, !llvm.loop !6
}

最终，可以得到结论，这个反常的现象是在IR层面的编译器优化引起的。

寻找优化的Pass

背景知识

2022年我也遇到过编译器优化引发的逻辑错误，被 dmxcsnsbh 一眼看穿，并推荐我文章：https://www.blackhat.com/eu-20/briefings/schedule/#finding-bugs-compiler-knows-but-doesnt-tell-you-dissecting-undefined-behavior-optimizations-in-llvm-21128 。于是我第一反应就是 LLVM 进行了优化，但这个是不是 UB 引起的，一眼没看出来。

dump llvm ir transform

通过命令：clang++ -mllvm --print-before-all -mllvm --print-after-all test.cpp -O1 拿到每个pass的所有输入和输出。

经过搜索，找到如下日志，表明经过 LoopDeletionPass 的处理，原先的循环被替换成了 unreachable instruction：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
*** IR Dump Before LoopDeletionPass on Parallel Loop at depth 1 containing: %1<header><latch> ***

; Preheader:
  br label %1

; Loop:
1:                                                ; preds = %0, %1
  br label %1, !llvm.loop !5

*** IR Dump After LoopDeletionPass on Parallel Loop at depth 1 containing: %1<header><latch> (invalidated) ***
; ModuleID = 'test.cpp'
source_filename = "test.cpp"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [12 x i8] c"HelloWorld\0A\00", align 1
@str = private unnamed_addr constant [11 x i8] c"HelloWorld\00", align 1

; Function Attrs: mustprogress nofree norecurse noreturn nosync nounwind readnone uwtable willreturn
define dso_local noundef i32 @main() local_unnamed_addr #0 {
  unreachable
}

粗略阅读代码

代码位于：https://llvm.org/doxygen/LoopDeletion_8cpp_source.html

1
2
3
4
// This file implements the Dead Loop Deletion Pass. This pass is responsible
// for eliminating loops with non-infinite computable trip counts that have no
// side effects or volatile instructions, and do not contribute to the
// computation of the function's return value.

大意就是，删除对执行无影响的死循环。个人观点，已经是死循环了，所以标记为 unreachable 也是说得过去的。

LoopDeletionPass 继承了 LoopPass，实现 runOnLoop，调用 deleteLoopIfDead，内部使用 isLoopDead 判断是否需要被移除，移除时调用来自 LoopUtils.h 的 deleteDeadLoop 来执行。

而 deleteDeadLoop 中，出现了关键的 CreateUnreachable ：

1
2
3
4
5
6
7
8
} else {
  assert(L->hasNoExitBlocks() &&
          "Loop should have either zero or one exit blocks.");

  Builder.SetInsertPoint(OldTerm);
  Builder.CreateUnreachable();
  Preheader->getTerminator()->eraseFromParent();
}

答案：所以答案很简单。。。

  1. 因为删除了死循环，导致main函数里只有一句 unreachable instruction
  2. 在codegen阶段，后端认为 main 里只有一句 unreachable，不需要创建对应的汇编指令，只有一个符号，函数长度为0
  3. 恰好在该位置，生成了与main函数相邻的函数，而main的长度为0，所以main实际指向了相邻的函数（没有人规定两个符号不能指向同一个偏移）
  4. 后续连接过程不会遇到任何问题，造成诡异的情况发生了

到底是不是Undefined Behavior？

C++里是UB。https://en.cppreference.com/w/cpp/language/ub ，Infinite loop without side-effects 。

C语言里不是UB，见 ISO/IEC 9899 J.2 Undefined behavior 后，并没有找到和loop相关的关键词。

包括官方还给了一个demo，优化后fermat直接返回true（不解释了，不会，自行领悟）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
 
bool fermat()
{
    const int max_value = 1000;
 
    // Endless loop with no side effects is UB
    for (int a = 1, b = 1, c = 1; true; )
    {
        if (((a * a * a) == ((b * b * b) + (c * c * c))))
            return true; // disproved :)
        a++;
        if (a > max_value)
        {
            a = 1;
            b++;
        }
        if (b > max_value)
        {
            b = 1;
            c++;
        }
        if (c > max_value)
            c = 1;
    }
 
    return false; // not disproved
}
 
int main()
{
    std::cout << "Fermat's Last Theorem ";
    fermat()
        ? std::cout << "has been disproved!\n"
        : std::cout << "has not been disproved.\n";
}

番外篇：为什么只有cpp会有该优化、而c语言没有该优化（超出能力范围了。。。）

获得两个未经处理的 ll 文件：clang test.c -O0 -emit-llvm -c -S -o test.c.ll 和 clang++ test.cpp -O0 -emit-llvm -c -S -o test.cpp.ll。

将 optnone 移除掉：sed -i 's/optnone//' test.c.ll 和 sed -i 's/optnone//' test.cpp.ll。

使用 opt 将 LoopDeletionPass 作用于 C 的 IR 和 CPP 的 IR。（因为需要编译llvm，因为要看LLVM_DEBUG的日志，需要开启 DLLVM_ENABLE_ASSERTIONS=TRUE）

二者执行起来日志分别为：

opt作用于C语言

1
2
3
4
opt -debug-only=loop-delete -passes=loop-deletion test.c.ll -S -o /dev/null
Analyzing Loop for deletion: Loop at depth 1 containing: %2<header><latch>
Could not compute SCEV MaxBackedgeTakenCount and was not required to make progress.
Loop is not invariant, cannot delete.

opt作用于C++语言

1
2
3
opt -debug-only=loop-delete -passes=loop-deletion test.cpp.ll -S -o /dev/null
Analyzing Loop for deletion: Parallel Loop at depth 1 containing: %2<header><latch>
Loop is invariant, delete it!

显然，二者出现了偏差，略微diff一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-; Function Attrs: noinline nounwind  uwtable
-define dso_local i32 @main() #0 {
+; Function Attrs: mustprogress noinline norecurse nounwind  uwtable
+define dso_local noundef i32 @main() #0 {
   %1 = alloca i32, align 4
   store i32 0, i32* %1, align 4
   br label %2

 2:                                                ; preds = %0, %2
-  br label %2
+  br label %2, !llvm.loop !6
 }

+!6 = distinct !{!6, !7}
+!7 = !{!"llvm.loop.mustprogress"}

不清楚哪里引起的，把这个6和7补上去，C语言就可以正确地被处理为unreachable了，研究了很久，超出知识范围了，看不懂，反正就 LoopPass 认为 MaxBackedgeTakenCount 的数据不对，不给删。

结合上文说的C里不算UB、C++里算UB，编译器这么做也是完全正确的。

总结：绝知此事要躬行

有时我自己也写点死循环，UB竟在我身边，UB竟是我自己。