【0到1的设计之路】从C语言到二进制程序

C程序如何从源代码生成指令序列(二进制可执行文件)

预处理 -> 编译 -> 汇编 -> 链接 -> 执行

预处理

预处理 = 文本粘贴

#include <stdio.h>
#define MSG "Hello \
World!\n"
int main() {
  printf(MSG /* "hi!\n" */);
#ifdef __riscv
  printf("Hello RISC-V!\n");
#endif
  return 0;
}

gcc -E a.c

头文件是如何找到的?

方法: 阅读工具的日志(查看是否支持verbose, log等选项)

gcc -E a.c --verbose > /dev/null

通过man gcc并搜索-I选项可得知头文件搜索的顺序

echo '#warning I am wrong!' > stdio.h
gcc -E a.c --verbose
mkdir aaa bbb
gcc -E a.c -Iaaa -Ibbb --verbose > /dev/null
echo '#warning I am wrong, too!' > bbb/stdio.h
echo '#define printf(...)' >> bbb/stdio.h
gcc -E a.c -Iaaa -Ibbb --verbose

类函数宏

#define max(a, b) ((a) > (b) ? (a) : (b))

• 好的编程习惯 -> 总是用括号包围参数
• 好的编程习惯 -> 一个参数尽量不要展开多次

define max(a, b) ({ int x = a; int y = b; x > y ? x : y; })

上述代码使用了GNU C Extension, 跨平台移植时需要注意

预处理的其他工作

• 去掉注释
• 连接因断行符(行尾的)而拆分的字符串
• 处理条件编译 #ifdef/#else/#endif

riscv64-linux-gnu-gcc -E a.c  # apt-get install g++-riscv64-linux-gnu

• 字符串化 #
• 标识符连接 ##

#define _str(x) #x
#define _concat(a, b) a##b
_concat(pr, intf)(_str(RISC-V));

IOCCC(国际混乱C代码大赛)

套路: 借助预处理机制编写不可读代码

编译

编译是一个比较复杂的过程

词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成 -> 优化 -> 目标代码生成

借助合适的工具(clang), 我们来看看每一个阶段都在做什么

• clang功能上等价于gcc, 但能向我们更好地展示编译的中间步骤

#include <stdio.h>
int main() { // compute 1 + 2
  int x = 1, y = 2;
  int z = x + y;
  printf("z = %d\n", z);
  return 0;
}

词法分析

clang -fsyntax-only -Xclang -dump-tokens a.c

识别并记录源文件中的每一个token

• 标识符, 关键字, 常数, 字符串, 运算符, 大括号, 分号…
• 还记录了token的位置(文件名:行号:列号)

C代码 = 字符串

• 词法分析器本质上是一个字符串匹配程序

语法分析

clang -fsyntax-only -Xclang -ast-dump a.c

按照C语言的语法将识别出来的token组织成树状结构

• AST(Abstract Syntax Tree), 可以反映出源程序的层次结构
• 报告语法错误, 例如漏了分号

语义分析

按照C语言的语义确定AST中每个表达式的类型

• 相容的类型将根据C语言标准规范进行类型转换

• 算术类型转换

• 报告语义错误

• 未定义的引用
• 运算符的操作数类型不匹配(如struct + int)
• 函数调用参数的类型和数量不匹配
  …

但大多数编译器并没有严格按阶段进行词法分析, 语法分析, 语义分析

• clang的-ast-dump把语义信息也一起输出了

• man clang可以得知clang的阶段划分

静态程序分析

在不运行程序的情况下对其进行分析

• 本质就是分析AST中的信息

AST（Abstract Syntax Tree）是源代码的抽象语法结构的树状表现形式，也就是源代码的抽象语法结构的一种树状图表示。

在编译原理中，AST是源代码和编译器之间的一种数据结构。编译器将源代码转换为AST，然后对AST进行一系列的转换，最终生成目标代码。AST的结构和形式是由源代码的语法决定的，因此AST也被称为源代码的抽象语法。

AST可以用于静态分析，即在程序运行之前对其进行分析。通过分析AST，可以了解程序的结构、语法错误、潜在的逻辑错误等等。例如，一些代码质量检查工具、代码格式化工具、编译器优化等都可以使用AST进行分析。

在不运行程序的情况下对其进行分析，本质就是分析AST中的信息。通过解析源代码生成AST，然后对AST进行分析，可以获取程序的各种信息，如变量使用情况、函数调用关系、代码覆盖率等等。这些信息可以用于代码质量评估、性能优化、错误检测和修复等等。

可以检查/分析以下方面

• 语法错误,
• 代码风格和规范,
• 潜在的软件缺陷,
• 安全漏洞,
• 性能问题

#include <stdlib.h>
int main() {
  int *p = malloc(sizeof(*p) * 10);
  free(p);
  *p = 0;
  return 0;
}

clang use-after-free.c --analyze -Xanalyzer -analyzer-output=text

中间代码生成

clang -S -emit-llvm a.c

中间代码(也称中间表示, IR) = 编译器定义的, 面向编译场景的指令集

define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 1, i32* %2, align 4
  store i32 2, i32* %3, align 4
  %5 = load i32, i32* %2, align 4
  %6 = load i32, i32* %3, align 4
  %7 = add nsw i32 %5, %6
  store i32 %7, i32* %4, align 4
  %8 = load i32, i32* %4, align 4
  %9 = call i32 (i8*, ...) @printf(i8* noundef getelementptr inbounds ([8 x i8], [8 x i8]* @.str, i64 0, i64 0), i32 noundef %8)
  ret i32 0
}

将C语言状态机翻译成IR状态机

• 变量 -> %1, %2, %3, %4, …
• 语句 -> alloca, store, load, add, call, ret, …

中间代码作为抽象层

为什么不直接翻译到处理器ISA?

基于抽象层进行优化很容易

可以支持多种源语言和目标语言(硬件指令集)

clang使用的中间代码叫LLVM IR, gcc的叫GIMPLE

• 我们不需要理解其中的细节, 研究它是编译专家的事情
• 知道一些基本概念, 会连蒙带猜看一看即可(可RTFM了解更多)

优化

如果两个状态机在某种意义上 “相同”, 就可以用 “简单”的替代 “复杂”的

• “简单” = 状态少(变量少), 激励事件少(语句少)…
  
• 最 “复杂” = 严格按照语句的语义来翻译(严格的状态转移)
  
• “相同” = 程序的可观测行为(C99 5.1.2.3节第6点)的一致性
  
• 对volatile修饰变量的访问需要严格执行
  
• 程序结束时, 写入文件的数据需要与严格执行时一致
  
• 交互式设备的输入输出(stdio.h)需要与严格执行时一致
  

这给编译器优化提供了非常广阔的空间

• 也是因为太广阔, 以至于编译器里面有很多bug
• 理论上来说, “判断任意两个程序的可观测行为是否一致”是不可判定的
• 如果这个问题可判定, 那么借助它可判定图灵停机问题(阅读材料)

例: 常数传播

clang -S -foptimization-record-file=- a.c
clang -S -foptimization-record-file=- a.c -O1

加个volatile试试

#include <stdio.h>
int main() { // compute 1 + 2
  int x = 1, y = 2;
  volatile int z = x + y;
  printf("z = %d\n", z);
  return 0;
}

目标代码生成

clang -S a.c
clang -S a.c --target=riscv32-linux-gnu
gcc -S a.c   # 也可以用gcc生成
# apt-get install g++-riscv64-linux-gnu
riscv64-linux-gnu-gcc -march=rv32g -mabi=ilp32 -S a.c

将IR状态机翻译成处理器ISA状态机

• %1, %2, %3, %4, … -> {R,M}
• alloca, store, load, add, call, ret, … -> ISA的指令
• 同时进行目标ISA相关的优化

• 把经常使用的变量放到寄存器, 不太常用的变量放到内存
• 选择指令数量较少的指令序列
• 有很多优化的空间, 这里不深入讨论

可以通过time report观察clang尝试了哪些优化工作

clang -S a.c -ftime-report

踏入二进制的世界

汇编

gcc -c a.c
riscv64-linux-gnu-gcc -march=rv32g -mabi=ilp32 -c a.c
# alias rv32gcc="riscv64-linux-gnu-gcc -march=rv32g -mabi=ilp32"

根据指令集手册, 把汇编代码(指令的符号化表示)翻译成二进制目标文件(指令的编码表示)

二进制文件不能用文本编辑器打开来阅读了

• 需要binutils(Binary Utilities)或者llvm的工具链

objdump -d a.o
riscv64-linux-gnu-objdump -d a.o
# alias rvobjdump="riscv64-linux-gnu-objdump"
llvm-objdump -d a.o # llvm的工具链可以自动识别目标文件的架构, 用起来更方便

链接

gcc a.c
riscv64-linux-gnu-gcc a.c  # apt默认不安装rv32的glibc库, 无法链接到glibc, 这里用rv64演示

合并多个目标文件, 生成可执行文件

• 哪里来的多个目标文件呢?

让我们来看日志!

gcc a.c --verbose
gcc a.c --verbose 2>&1 | tail -n 2 | head -n 1 | tr ' ' '\n' | grep '\.o$'

有很多crtxxx.o的文件

crt = C runtime, C程序的运行时环境(的一部分)

可以通过objdump确认

问题: printf()的代码在哪里呢?

执行

./a.out
# 通过一些配置工作, RISC-V的可执行文件也可以在本地执行
# apt-get install qemu-user qemu-user-binfmt
# mkdir -p /etc/qemu-binfmt
# ln -s /usr/riscv64-linux-gnu/ /etc/qemu-binfmt/riscv64
file a.out
a.out: ELF 64-bit LSB pie executable, UCB RISC-V, version 1 (SYSV)...
./a.out # 实际上是在QEMU模拟器中执行

把可执行文件加载到内存, 跳转到程序, 执行编译出的指令序列

Q: 谁来加载?

A: 运行时环境(宿主操作系统/QEMU)

实现定义行为和ABI

正确做法: 通过日志观察工具的行为

• 程序相同, 但编译选项可能影响程序的解释 -> 看AST!

clang -fno-color-diagnostics -fsyntax-only -Xclang -ast-dump -w -std=c90 -m32 a.c

RTFM: ABI中定义的基本数据类型

• System V ABI for i386 - 32位x86 Linux遵循的ABI：https://math-atlas.sourceforge.net/devel/assembly/abi386-4.pdf
• ABI for RISC-V：https://github.com/riscv-non-isa/riscv-elf-psabi-doc/blob/master/riscv-cc.adoc

ABI，全称为Application Binary Interface，即应用程序二进制接口。它定义了应用程序与操作系统之间进行交互的方式和规范，确保不同的软件组件能够正确地协同工作。ABI包括了函数调用约定、寄存器的使用、参数传递方式、系统调用接口等内容，为软件开发者提供了一个稳定和一致的编程接口。

为什么还要学习C语言?

“使用语言”和 “学习计算机”的目的不完全相同

• 使用语言的目标是提高效率

• 开发者友好的语言特性, 更抽象也更安全的功能, 各种开箱即用的库

• 例 - 数组越界不再是UB, 而是由运行环境马上报错
• 这些功能需要更复杂的翻译环境和运行环境来支撑

作为计算机的使用者, 我们应该掌握1~2门现代语言提升工作效率

python, bash, go, rust, …

• 学习计算机的目标是理解程序如何在计算机上运行

• 语言越接近底层硬件, 越有利于我们学习其中的细节

• 例 - ISA状态机没有数组越界的概念

• 作为计算机的设计者, 我们应该掌握C语言, 理解计算机的基本原理

总结—从C代码到指令序列

• 预处理 -> 编译 -> 汇编 -> 链接 -> 执行
  
• 编译 = 词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成 -> 优化 -> 目标代码生成
  
• 学会使用工具和日志理解其中的细节
  
• C语言标准中除了确切的行为, 还包含

• Unspecified Behavior
• Implementation-defined Behavior
• Undefined Behavior

• 通过ABI手册了解Implementation-defined Behavior的选择

• 同时认识C语言标准, 编译器, 操作系统, 运行库, 处理器之间的协助
• 程序的运行结果与源代码和上述因素都有关系

内容来自：一生一芯_余子濠_从C语言到二进制程序