《自制编译器》读书笔记Part2

作者: kolibreath | 来源:发表于2020-09-05 16:26 被阅读0次

前言

这个部分主要就讲讲最后一个部分，也是最复杂的一个部分--- 代码生成。代码生成需要涉及到一下几个方面，分别是汇编代码生成、链接和加载。不过在讲代码生成之前先要讲一下和代码优化，毕竟这个部分单独先拿出来讲不会影响内容的连贯性。

代码优化

优化的目的一般是为了提升代码运行的速度，不过也有以减少代码量为目的的优化。下面我简要通过一张表来解释常见的优化案例：

优化方法	例子	处理
常量折叠	int max = 2*1024;	直接在编译过程中算出结果
代数简化	int x = y * 1;	利用数学表达式的性质代替计算的公式
降低运算强度	int y = x * 2;	乘法变成位移，次数较少的乘法运算变成加法
削除共同子表达式	int x = a * b + c ； int y = a * b+1;	其中共同的计算部分只需要计算一次就行
消除无效语句	if(false) func(x);	这个指令在逻辑上基本是运行不到的，可以直接删除
函数内联		这个和c++里面的inline差不多，就是把短的语句插入到其他地方，避免没有必要的压栈还有清理过程

在Cflat编译器中，作者使用的是一种“窥孔优化”，即对于一部分机器码进行匹配，然后做优化，这里就不展开了。

代码生成

汇编代码语法

汇编代码具体的语法可以看到一下《自制编译器》的第三部分，我认为这个部分写的非常详细，可以作为很好的参考手册。

汇编代码举例

 import stdio;

int a = 10;

int func(int b) { return b + 1; }

int main(int argc, char ** argv) {
 printf("%s\n", "hello,world!");
}

这个例子中声明了一个全局变量和一个函数，以及在main()函数中输出了hello,world，可以说是一个非常常规的例子了，他的对应的由Cflat编译器输出的汇编代码如下:

# 说明汇编代码对应的文件的名称
 .file  "test.cb"
    .data
# 声明全局变量 对齐方式 类型（@object 表示变量）
.globl a
    .align  4
    .type   a,@object
    .size   a,4
a:
# 说明a这个变量是4个字节 初始值为10
.long   10
# 声明字符串这样的只读量会放在read only data节（rodata）
    .section    .rodata
.LC0:
    .string "%s\n"
.LC1:
    .string "hello,world!"
#改变节 将下面的函数的代码写在机器码对应的 .text节
    .text
.globl func
    .type   func,@function
# 对应的函数代码
func:
# 函数序言
    pushl   %ebp
    movl    %esp, %ebp
#将参数的值通过间接内存访问放入eax寄存器
    movl    8(%ebp), %eax
#加1并且返回 返回值一般都会通过eax返回
    addl    $1, %eax
    jmp .L0
.L0:
# 函数尾声
    movl    %ebp, %esp
    popl    %ebp
    ret
# 计算出函数func的大小 “.”符号说明的是函数末尾的地址-main函数的开头的地址得到函数的大小
    .size   func,.-func
.globl main
    .type   main,@function
# 这个标签其实就是main函数的地址，方便其他函数调用
main:
# 函数序言
    pushl   %ebp
    movl    %esp, %ebp
# 把标签对应的字符串放到eax寄存器
    movl    $.LC1, %eax
# 参数压栈 两个参数 一个格式化参数 一个输出参数，从右向左压栈
    pushl   %eax
    movl    $.LC0, %eax
    pushl   %eax
# 表示调用printf（去printf的地址调用printf 但是printf在哪里呢？）
    call    printf
    addl    $8, %esp
.L1:
# 函数尾声
    movl    %ebp, %esp
    popl    %ebp
    ret
    .size   main,.-main

如果对于汇编语言理解上有问题的话问题不大，因为注释已经写的比较明白了，下面几节将会阐述这段汇编代码的几个问题

函数相关的机器栈帧分配问题（调用者被调用者参数压栈等等）
函数序言和函数尾声
对于没有声明在main()函数中printf()的地址在哪里？
对于变量分配，全局变量的分配就是使用汇编代码的范畴，这里不详细解释了。

Stop here！

在生成中间代码ir树到汇编代码的步子是不是迈的有点大？事实上从中间代码到汇编代码的生成的阶段需要完成理解我下面讲解的内容才能更好地理解代码生成的过程。其实汇编代码的生成过程也是类似上面的从代码到抽象语法树这样的一个翻译的过程（但是整体的逻辑更复杂一些），这些汇编代码最后交给了Linux系统的GNU as汇编器生成了目标文件.out 文件（ELF格式）,比如

as -o hello.o hello.s

之后再将这个文件和标准库链接才能输出可执行文件

gcc hello.o -o hello

ir树到汇编代码的具体流程先按下不表，后面再详细说明。

函数调用约定 calling convention

程序的调用约定是指：

根据 CPU和OS决定函数函数调用的具体实现方法的约定。

所以说到了编译的第四个部分这里因为不同的CPU的指令集上有差异，而且OS提供的一些工具包也不同，在代码生成的阶段是一个对CPU和OS强依赖的阶段(Cflat编译器就是在x86架构的CPU，Linux系统上实现的)。

函数调用约定1

函数调用约定2

标准栈帧结构

结合具体的例子分析调用过程

首先要明确一点，机器栈其实上是内存的一块区域，并不是通过一种编程语言创建的一种栈的数据结构，只是汇编语言通过了类似于先入后出（First in last out）的机制来操作这片内存。

int f(int x, int j){
 int i, j;
 i = x;
 j = i * y;
 return j;
}

int main(int argc, char ** argv) {
 int i = 77;
 i = f(i, 8);
 i %= 5;
 return i;
}

对于这个代码，对应的汇编代码以及内容我通过下图表示出来了

说明图

下面简单的做一下说明：
下到汇编语言这个层级有几点需要明确：

寄存器的数量非常少
寄存器是CPU中非常关键的资源，他非常少，但是由不得不用，试想一下只有很少的寄存器（相当于是编程语言的全局变量）就要完成编程语言到机器语言的转化，难度是很大的。但是还是可以通过压入（push）和弹出（pop）机器栈的方式保存的。
函数对参数的访问、序言、尾声
在函数调用的过程中，函数是通过栈底指针寄存器ebp+偏移量（n(%ebp)）的方式来访问实际参数的，但是函数之间存在着调用和被调用的关系，被调用函数就需要保存调用者的栈底指针寄存器ebp的值。同时调用函数还需要负责给被调用函数开辟出一块内存空间（这就是函数的序言部分），被调用函数还需要执行在调用完成之后的还原工作，毕竟得把别人栈顶（esp）和栈底（ebp）还原回去，这部分就是函数的尾声。

虽然书上没有写，但是我们也不妨看看f函数的的汇编代码:

f:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $8, %esp
# 从这里开始就是省略的部分
# 访问函数的实际参数 
    movl    8(%ebp), %eax
    movl    %eax, -4(%ebp)
    movl    -4(%ebp), %eax
    movl    12(%ebp), %ecx
# 在ecx 和eax进行运算操作
    imull   %ecx, %eax
    movl    %eax, -8(%ebp)
    movl    -8(%ebp), %eax
    jmp .L0
# 函数尾声
.L0:
    movl    %ebp, %esp
    popl    %ebp
    ret
    .size   f,.-f

上面的代码中，之所以是ebp 的地址+8 是因为call调用返回地址压栈之后，返回地址上面的就是被调用函数f的栈底地址，而且main函数在调用f之前就给他的两个参数压栈了，所以很容易就寻找到了实际参数的地址。

callee-save和caller-save寄存器

为了减少函数在调用和被调用的过程中对于通用寄存器反复压栈出栈的过程，寄存器一般被划分为callee-save（被调用者保存寄存器）caller-save（调用者保存寄存器）

举个例子ebp是一个callee-save寄存器，因为被调用的函数（callee）会将调用函数的esp作为自己的ebp，所以被调用的函数（callee）在写入ebp寄存器之前需要保存调用者（caller）的ebp，然后再向esp中写入内容，因此调用者需要保存自己的esp（caller-save），如果仔细分析一下上面函数调用的流程就可以理解了。

函数的编译过程

在程序调用约定中还有一条非常重要的要求就是对于函数的栈帧的结构的约定

标准栈帧结构

其中可以看到如果函数被调用的时候局部变量需要放在callee-save寄存器的地址上面然后再是临时变量。

CodeGenerator#compileFunctionBody

private void compileFunctionBody(AssemblyCode file, DefinedFunction func) {
        StackFrameInfo frame = new StackFrameInfo();
        // 确定参数的地址 实际参数的位置在调用者函数的栈中（caller ）通过ebp寄存器往下找
        locateParameters(func.parameters());
       // 确定局部变量的地址
        frame.lvarSize = locateLocalVariables(func.lvarScope());

       //函数体的编译过程现编译完函数体 然后再找出偏移量 
        AssemblyCode body = optimize(compileStmts(func));
        frame.saveRegs = usedCalleeSaveRegisters(body);
        frame.tempSize = body.virtualStack.maxSize();

        //根据编译函数中确定的寄存器（callee-save）来确定局部变量的偏移量
        fixLocalVariableOffsets(func.lvarScope(), frame.lvarOffset());
        fixTempVariableOffsets(body, frame.tempOffset());

        if (options.isVerboseAsm()) 
            printStackFrameLayout(file, frame, func.localVariables()); 

        generateFunctionBody(file, body, frame);
    }

这个里面存在一个很大的问题，因为如果不先编译函数的话就没有办法确定这个函数在使用过程中使用的callee-save寄存器器个数，因此也就无法确定临近的局部变量的内存位置。因为Cflat编译器采取的策略是先进行函数体的编译，局部变量的位置在加上callee-save寄存器的偏移量。

总结1

中间代码编译成汇编代码的过程比较复杂，这个地方其实只是挑选出来比较重点的部分说了一下，大体的思路比较好把握，就是需要按照对应的指令集和调用约定构造出符合CPU和OS要求的汇编代码，然后就可以通过GNU as工具生成目标文件。

生成目标文件

最开始的时候就讲过生成了目标代码之后需要链接和加载才可以生成可执行文件，在Linux中常见的用于描述目标文件、可执行文件以及共享库的所有信息，并且把机器代码机器对应的元数据以一种放标连接器加载器处理的形式保存的起来的格式被称作ELF文件。

ELF文件的格式

ELF文件中有部分是给汇编器处理的有部分是链接器生成的，Cflat中汇编器处理的只有四个节。所谓节分别是

名称	作用
.text	配置机器码
.data	拥有初始值的全局变量
.rodata	字符串字面量不能更新的数据（只读）
.bss	没有初始值的全局变量，在ELF文件中没有大小信息

ELF的结构

这些节以及指定他们的相关语法还是属于汇编语言的范畴的，因此还是需要CodeGenerator中生成这个节进行内存的分配等等操作。
CodeGenerator#generate

 public AssemblyCode generate(IR ir) {
        //确定全局变量 函数 字符串常量在内存空间中的位置
        locateSymbols(ir);
        return generateAssemblyCode(ir);
    }

   private AssemblyCode generateAssemblyCode(IR ir) {
        AssemblyCode file = newAssemblyCode();
        file._file(ir.fileName());
        if (ir.isGlobalVariableDefined()) {
            generateDataSection(file, ir.definedGlobalVariables());
        }
        if (ir.isStringLiteralDefined()) {
            generateReadOnlyDataSection(file, ir.constantTable());
        }
        if (ir.isFunctionDefined()) {
            generateTextSection(file, ir.definedFunctions());
        }
        // #@@range/generateAssemblyCode_last{
        if (ir.isCommonSymbolDefined()) {
            generateCommonSymbols(file, ir.definedCommonSymbols());
        }
        if (options.isPositionIndependent()) {
            PICThunk(file, GOTBaseReg());
        }
        return file;
    }

链接

对于两个C语言文件main.c和f.c
main.c:

#include <stdio.h>

extern  int f(int a, int b);

int  main(int argc, char ** argv){
  printf("%the answer is d\n", f(1,2));
}

f.c:

int f int f(int a, int b) {return a + b;}

对这两个文件进行分别编译输出目标文件,

gcc -c main.c
gcc -c f.c

因为main中的f函数没有定义，所以需要将两个目标文件链接起来

gcc main.o f.o -o prog

最终输出了prog这个可执行文件。在Linux中负责链接的程序是/usr/bin/ld。链接器对于OS是强依赖的，所以链接器一般都会和OS由OS提供商提供。

链接器处理操作和能够处理的文件格式

链接器在连接时会进行三个处理

合并节
将相同种类的节进行合并

合并节
重定位
重定位是指根据程序实际加载到内存时的地址，对目标文件中的代码和数据进行调整。因为各个文件的编译和汇编的过程是独立的，并不知道其他的文件的函数的地址，这样可能会出现在链接的时候同一个地址有多个函数的情况发生，因此需要进行偏移量的调整。

重定位过程
符号消解
对于未定义的符号进行消解的过程，比如printf函数需要在lib.c中找。

链接器处理的文件格式

可重定位文件
可执行文件
共享库
静态库

共享库和静态库后面会详细讲到。

动态链接和静态链接

动态链接和静态链接的区别就在于：静态链接会在build的时候进行目标文件的链接，而动态链接只是在build的时候检查共享库（动态链接库）和符号是否存在，在运行时进行链接。

动态链接的优缺点

可以通过理解动态链接的优缺点来了解静态连接的优缺点

优点	原因
容易更新	对于库的更新只需要安装新的库，对于静态库却需要重新进行链接
节省磁盘空间	因为静态库需要在链接了静态库文件中保留一份静态库的副本，比较浪费磁盘空间
节省内存	.text段只读，mmap映射到内存之后多个进程可以共享这个内存段

缺点	原因
性能稍差	运行时进行连接操作需要花费一定的时间
连接具有不确定性	可能用户在链接时替换为自己的库

位置无关代码

动态链接需要加载共享库，上面简单的介绍了一下共享库。共享库是通过mmap系统调用直接加载到内存空间中，然后再虚拟地址空间内进程就可以共用这个内存页。在上面的main.c的例子中使用了f.c中定义的f函数和在libc中定义的printf函数，在汇编代码中，会使用call <f>和call <printf>类似的代码来表示调用这两个函数。

在链接时，因为f定义在f.c中，通过重定位可以找到f函数；在链接时会加载libc库也可以确定printf的地址了。
直观地思路是修改call后面的地址，保证call能够调用真正的地址。

但是这样的方式是不行的，因为现代操作系统不允许这样的行为，代码节是只读的只能修改数据节。而且重定位一旦发生就会向内存中写入数据，共享库的共享也根本无从谈起了。

因此就选择了一种比较折中的方式，就是重定位到数据段，修改数据段的内容总是可行的。因此对于外部定义的函数的访问过程就可以通过GOT（全局偏移量表，定义在数据段），来保存函数地址，然后链接器也生成了用于获取外部函数地址的一小段代码，也就是PLT（Procedure Link Table）。

《自制编译器》中对这个部分我觉得描述比较模糊，我根本看不懂他的逻辑，于是就选取了《深入理解计算机系统》的一张图来说明这个过程。

延迟绑定 lazy binding

第一次调用

假设现在要获取共享库中定义的函数addvec，也就是序号1表示的部分，这是就会访问过程连接表PLT中的PLT[2]对应的这一小段代码。这段代码需要跳转到GOT[4]对应的地址，其实也就是访问地址在4005c6
然后执行相应的操作。继续执行PLT[2]中的代码，带了4005cb ，这里跳转到了4005a0也就是PLT[0]对应的程序，他的目的是调用动态链接器，执行PLT[0]中的两部操作就给动态链接器传递了所需的参数，于是也就确定了addvec的位置。

后续调用

上面这样的操作有一个显而易见的好处，类似于libc.so 这样有很多很多的函数的库，调用方只会使用需要链接的库进行链接，就可以避免很多没有必要的重定位，
在上面的图中，如果如果是第二次或者后续在调用addvec的时候会直接跳转到GOT[4]的地址，此时因为addvec的地址已经确定，所以可以直接使用addvec

总结

编译的四个过程就全部都讲完了，我们再来梳理一下这个过程

对于任意的cflat代码，会按照图中的代码的调用顺序进行调用。在compile()中进行语法分析，语义分析并且声称中间代码，然后就会进行汇编代码生成，最后Cflat编译器会调用Linux中的一些必要的函数和工具进行链接，

对于Part1中的图也可以在最后进行补充了：