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

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

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

预处理

预处理 = 文本粘贴

#include <stdio.h>
#define MSG "Hello 
World!
"
int main() {
  printf(MSG /* "hi!
" */);
#ifdef __riscv
  printf("Hello RISC-V!
");
#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
", 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
", 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 ' ' '
' | 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语言到二进制程序