You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

308 lines
22 KiB
Markdown

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

# 17生成本地代码第2关变量存储、函数调用和栈帧维护
你好,我是宫文学。
在上一节课里,我们已经初步生成了汇编代码和可执行文件。不过,很多技术细节我还没有来得及给你介绍,而且我们支持的语言特性也比较简单。
那么,这一节课,我就来给你补上这些技术细节。比如,我们要如何把逻辑寄存器映射到物理寄存器或内存地址、如何管理栈桢,以及如何让程序符合调用约定等等。
好了,我们开始吧。先让我们解决逻辑寄存器的映射问题,这其中涉及一个简单的寄存器分配算法。
## 给变量分配物理寄存器或内存
在上一节课,我们在生成汇编代码的时候,给参数、本地变量和临时变量使用的都是逻辑寄存器,也就是只保存了变量的下标。那么我们要怎么把这些逻辑寄存器对应到物理的存储方式上来呢?
我们还是先来梳理一下实现思路吧。
其实我们接下来要实现的寄存器分配算法是一个比较初级的算法。你如果用clang或gcc把一个C语言的文件编译成汇编代码并且不带-O1、-O2这样的优化选项生成出来的汇编代码就是采用了类似的寄存器分配算法。现在我们就来看看这种汇编代码在实际存储变量上的特点。
首先,程序的参数都被保存到了内存里。具体是怎么来保存的呢?你可以先看看示例程序[param.c](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.c)
```plain
void println(int a);
int foo(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8){
int x1 = p1*p2;
int x2 = p3*p4;
return x1 + x2 + p5*p6 + p7*p8;
}
int main(){
int a = 10;
int b = 12;
int c = a*b + foo(a,b,1,2,3,4,5,6) + foo(b,a,7,8,9,10,11,12);
println(c);
return 0;
}
```
这个示例程序所对应的汇编代码是[param.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.s),我摘取了其中的一部分,这段代码展示了参数是如何被保存到内存的:
```plain
## 把参数值保存到内存
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
movl %ecx, -16(%rbp)
movl %r8d, -20(%rbp)
movl %r9d, -24(%rbp)
```
在这个示例程序中foo函数有8个参数。根据[System V AMD64的ABI](https://gitee.com/richard-gong/craft-a-language/blob/master/13/System%20V%20Application%20Binary%20Interface%20AMD64%20Architecture%20Processor%20Supplement%20Draft%20Version%200.99.6.pdf)和C语言的调用约定其中前6个参数是通过寄存器传递的其他两个参数是通过栈桢传递的。
在汇编代码中我们会发现这6个通过寄存器传递的参数都先被保存到了栈桢中。这6个寄存器和参数的对应关系是这样的
![图片](https://static001.geekbang.org/resource/image/22/33/22ff0091312f4df5fb6313bdf3045333.jpg?wh=1920x570)
我也把它们保存在栈桢里的位置画成了一张图,你可以看一下:
![图片](https://static001.geekbang.org/resource/image/21/e1/213c71d3e770fdc7972b622c77b8d6e1.jpg?wh=1920x1080)
你可以看到这里面的前6个参数的位置都是从rbp的位置依次向下4个字节也就是一个整数的位置。参数1是-4(%rbp)参数2是-8(%rbp),依此类推。
而大于6个的参数是保存在调用者的栈桢里的。其中参数7的地址是16(%rbp)也就是rbp指针往上16个字节。这里为什么要加上16个字节呢这是因为这16个字节中有8个字节是返回地址是由callq \_foo指令压到栈里的还有8个字节是rbp之前的值是由pushq rbp压到栈里的。
好,到目前为止,我们就知道如何在汇编代码里访问每个参数了。你可以查看代码库里的[lowerVars](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L1178)代码它把每个参数转变成了一个内存地址类型的Oprand。
```plain
//处理参数
for (let varIndex:number = 0; varIndex<this.numTotalVars; varIndex++){
let newOprand:Oprand;
if (varIndex < this.numParams){
if (varIndex < 6){
//从自己的栈桢里访问。在程序的序曲里,就把这些变量拷贝到栈里了。
let offset = -(varIndex + 1) *4;
newOprand = new MemAddress(Register.rbp,offset);
}
else{
//从Caller的栈里访问参数
//+16是因为有一个callq压入的返回地址一个pushq rbp又加了8位
let offset = (varIndex - 6)*8 + 16;
newOprand = new MemAddress(Register.rbp,offset);
}
}
...
}
```
接下来,我们再看看本地变量。在示例程序[param.c](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.c)中有x1和x2两个本地变量你可以阅读[param.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.s),看看它们都是存在哪的。
我相信经过这么多节课的训练现在你阅读汇编代码应该越来越熟练了。在这个代码里你可以看到x1实际上是存在-28(%rbp)的而x2是存在-32(%rbp)的。也就是说,在栈桢里,它们是紧挨着参数的区域继续往下延伸的,你可以看看下面这张图。
![图片](https://static001.geekbang.org/resource/image/9b/45/9b4b437edbe28b3e69f77990e17dd345.jpg?wh=1920x1080)
好了,**现在对于参数和本地变量的保存,我们都搞清楚了,它们都是保存在内存的栈桢里的**。那么临时变量呢?临时变量也保存在内存里吗?
这是不行的。为什么呢这是因为X86指令集中加减乘除等指令和mov指令对内存地址的使用是有限制的。
怎么理解呢我们分析一下x1=p1\*p2这条语句来看看。在上节课中我们已经知道这条语句在生成汇编代码时需要用到一个临时变量t1所以整条语句在逻辑上相当于下面这三条汇编代码
```plain
movl p1, t1 #把p1拷贝到t1
imull p2, t1 #把p2乘到t1上
movl t1, x1 #把t1赋给x1
```
在这里p1和p2都是内存地址。如果t1也是内存地址我们假设它是-36(%rbp),那么这三条汇编代码就会变成:
```plain
movl -4(%rbp), -36(%rbp) #把p1拷贝到t1
imull -8(%rbp), -36(%rbp) #把p2乘到t1上
movl -36(%rbp), -4(%rbp) #把t1赋给x1
```
但是如果你用汇编器编译这三条代码,汇编器会报错。
这是为什么呢因为x86中汇编代码的规则虽然比较宽松在加减乘除等很多运算性指令里都支持使用内存地址作为操作数但它只允许源操作数是内存地址不允许目标操作数是内存地址。而mov指令支持目标操作数是内存地址但这个时候源操作数必须是立即数或寄存器不支持把数据从一个内存地址拷贝到另一个内存地址。
那么我们要怎么来修改这三条代码让它变成合法的X86汇编代码呢
很简单我们只要给临时变量t1分配一个物理寄存器就可以了。你可以参考[param.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.s)的代码它给t1分配了一个%ecx寄存器完美地解决了这个问题
```plain
movl -4(%rbp), %ecx #把p1拷贝到t1
mull -8(%rbp), %ecx #把p2乘到t1上
movl %ecx, -28(%rbp) #把t1赋给x1
```
所以,现在我们就清楚了:**对于临时变量,我们都统一给它们分配寄存器就行了**。
那进一步的问题又来了我们给这些临时变量分配哪些寄存器呢是先分配那些由Caller保护的寄存器还是Callee保护的寄存器用哪类寄存器的代价更低呢这几个问题你可以先记着自己想一会后面你看看示例代码是如何实现的。
好了现在我们已经给参数、本地变量和临时变量都分配了物理的存储方式。这个过程我们叫做把变量做Lower处理的过程你可以看一下[lowerVars](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L1178)方法。
并且,基于我们上面这个分配方法,所有的二元计算都能生成正确的汇编代码。你可以在[example.ts](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/example.ts)中写一些表达式计算的代码然后再用make example命令做构建。这会生成汇编代码文件example.s和可执行文件example你再看看它们能否正确地运行。
接下来,我们再研究一下如何实现函数的调用。
## 实现函数调用
我们仍然用示例代码[param.c](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.c)来做研究。在示例代码中我们用main函数调用了foo函数。由于foo函数的参数比较多所以我建议你好好看一下[param.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.s)中传参的具体过程。
```plain
movl -8(%rbp), %edi ##参数1变量a
movl -12(%rbp), %esi ##参数2变量b
movl $1, %edx ##参数3
movl $2, %ecx ##参数4
movl $3, %r8d ##参数5
movl $4, %r9d ##参数6
movl $5, (%rsp) ##参数7
movl $6, 8(%rsp) ##参数8
...
callq _foo
```
根据我们目前掌握的参数传递的知识这里的前6个参数赋给了6个寄存器而第7和第8个参数则是基于rsp赋给(%rsp)和8(%rsp)这两个内存地址。而在被调用者中访问这两个参数则是使用16(%rbp)和24(%rbp)。
我也画了一张图给你展示了如何在Caller和Callee的栈桢中访问参数7和参数8
![图片](https://static001.geekbang.org/resource/image/8e/fd/8e15e972dd84d7a9352dff7227c253fd.jpg?wh=1920x1080)
你要注意这里每个参数都占用了8个字节而不是像前面在Caller的栈桢里保存参数和本地变量那样占用4个字节。你能不能想一想这是什么原因呢
我估计你已经猜到了。这是因为在制定ABI的时候要兼容尽量多的场景。这个规定使得我们能够用同样的方式传递整型和长整型的参数而长整型就需要占据8个字节。
你可以看看[param\_long.c](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param_long.c)及其对应的[param\_long.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param_long.s)汇编代码文件。你会发现在这个示例文件中我们把整型的参数改成了长整型但是传递第7个和第8个参数的方法方式没有任何改变。在代码里访问这两个参数值的内存地址的表达方式也是一样的。
好了,我们已经了解了函数调用中传参的过程了,具体实现你可以参见代码库中的[lowerFunctionCall](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L1419)方法。那么现在我们是不是就可以调用callq指令来做函数调用了呢还不行。为什么呢因为我们还有一项重要的工作要做就是**保护好某些寄存器的值。**
还记得吗在函数调用的过程中有些寄存器的值是由Caller负责保护的而另一些寄存器的值是由Callee负责保护的这是为了避免可能由于多方使用同一个寄存器导致寄存器的值被破坏从而导致计算错误的问题。
我们还是通过示例代码来分析一下寄存器的使用可能产生的冲突。你会看到,在[param.c](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.c)中有下面的一行代码:
```plain
int c = a*b + foo(a,b,1,2,3,4,5,6) + foo(b,a,7,8,9,10,11,12);
```
这行代码是我故意设计的目的就是制造出寄存器使用上的冲突。整个计算过程大致可以分成下面这几步其中涉及到t1、t2和t3三个临时变量。
```plain
t1 = a*b
t2 = foo(a,b,1,2,3,4,5,6)
t1 = t1 + t2
t3 = foo(b,a,7,8,9,10,11,12)
t1 = t1 + t3
c = t1
```
首先我们需要计算表达式a\*b这个结果我们用t1表示并把它映射到寄存器。在[param.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.s)里这个寄存器是eax。
接着我们需要调用foo()函数假设返回值保存在t2中。这里要注意根据ABIfoo()函数的返回是要保存到eax中的所以t2和t1都要使用eax寄存器。为了防止t1的值被破坏我们就必须先把它写到栈里去。
```plain
movl %eax, -20(%rbp) ## 4-byte Spill
callq _foo
movl -20(%rbp), %ecx ## 4-byte Reload
addl %eax, %ecx ## t1 = t1 + t2把t2的值加到t1上
```
接下来在调用foo函数以后我们要把t1和t2相加。在此之前我们又需要把t1从内存中恢复到寄存器里来。但这个寄存器不再是eax因为现在t2已经占用了eax。所以t1被装载到了ecx寄存器中。
再接着我们还要再一次调用foo函数。在这次调用中寄存器的使用再次产生了冲突因为这次我们要用ecx来传递foo函数的第四个参数。那这又要怎么办呢我们还是要把t1的值从ecx寄存器里保存到内存中在调用完foo之后再从内存恢复到寄存器。
```plain
movl %ecx, -24(%rbp) ## 4-byte Spill
...
callq _foo
movl -24(%rbp), %ecx ## 4-byte Reload
addl %eax, %ecx ## t1 = t1 + t3, 把t3的值再加到t1上。
movl %ecx, -16(%rbp) ## c = t1
```
好了,通过上面这个例子的分析,我相信你已经对寄存器的冲突有了比较直观的了解。这里,我再带你总结一下可能发生冲突的场景:
* 场景1某个临时变量使用了eax但接下来的函数返回值也要使用eax也就是这个eax 在Callee中去做了设置
* 场景2某个临时变量使用了edi、esi、edx、ecx、r8d和r9d这6个寄存器其中的一个接下来的函数调用还要这个寄存器来传递参数
* 场景3在Caller中使用了不由Callee保护的寄存器比如r10d、r11d等等。在ABI中规定只有ebx、r12d~r15d这几个寄存器是由Callee保护的所以其他的寄存器都需要由Caller保护避免被Callee破坏。
那我们要如何保护这些寄存器呢?我们需要把它们的值写到栈桢里,之后再从栈桢里恢复。
注意把一个临时变量t保存到内存的过程叫做Spill也叫做溢出我们在后面专门学习寄存器分配算法的时候会再次见到这个词汇。把t从内存再重新装载到寄存器的过程叫做Reload。不过这里你也要注意虽然新的寄存器不一定是原来那个寄存器但编译器会知道这还是原来那个临时变量t。
Spill和Reload的实现你仍然可以参见[lowerFunctionCall](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L1419)方法。
那么到目前为止我们已经往栈桢里放了很多数据包括返回值地址、rbp的原值、参数还有本地变量。而且把临时变量溢出Spill到内存里也需要预留一些空间调用函数时给函数传参也需要使用栈的空间。
那我们现在就再进一步,梳理一下栈桢里的内容,也来分析一下我们要怎么做好栈桢的维护。
## 栈桢的维护
你可以先看一下,采用我们目前的算法形成的栈桢结构是这样的:
![图片](https://static001.geekbang.org/resource/image/f5/a3/f5ab10b57d420d11265434ec74ec52a3.jpg?wh=1920x1080)
一个栈桢从上到下依次是返回值、rbp原值、Callee保护的寄存器目前我们的示例程序中还没有用到这些寄存器、参数、本地变量、溢出到内存的临时变量。
然后你再从栈顶也就是栈桢的最底下往上看这里是我们在调用函数时为超过6个的参数所保存的空间。
然后你还会注意到,在栈桢中间可能还有一些多余的空间。为什么会这样呢?
第一个原因,是这个函数可能会调用多个函数,而被调用的多个函数所需的参数数量是不同的,因此我们需要为参数最多的那个函数预留出足够的用于保存参数的空间。
第二个原因是内存对齐。原来在ABI中规定如果这个函数要调用另一个函数那么参数区的尾部应该是16字节对齐的。所以说参数区的尾部也是两个栈桢之间的分界线。换句话说在控制转移到函数入口的那一刻(%rsp+8)的值是能够被16整除的。这里的8是因为callq指令把8位的一个返回地址压到了栈里。
我建议你看看[ABI文档](https://gitee.com/richard-gong/craft-a-language/blob/master/13/System%20V%20Application%20Binary%20Interface%20AMD64%20Architecture%20Processor%20Supplement%20Draft%20Version%200.99.6.pdf)中对栈桢的描述,我截取了一小段,你可以看看:
![图片](https://static001.geekbang.org/resource/image/97/0d/979a6b4f32d2d48f3ab02762dbd0970d.png?wh=1524x442 "来源System V Application Binary Interface AMD64 Architecture Processor Supplement Draft Version 0.99.6")
基于上面的原则我们在为一个函数建立栈桢的时候需要计算出rsp移动的量以便确定正确的栈桢尺寸。在[param.s](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/param.s)的\_main函数中序曲和尾声部分各有一行指令就是用来移动rsp指针的。
```plain
##序曲
pushq %rbp
movq %rsp, %rbp
subq $48, %rsp ##把栈桢扩展48个字节。整个栈桢的大小是48+16字节
##函数体
...
##尾声
addq $48, %rsp ##缩回栈桢
popq %rbp
retq
```
不过刚才我们看的是main函数的栈桢的情况。但对于foo函数来说它的栈桢会有所不同。
有什么区别呢区别就在于foo函数是叶子函数也就是说它没有调用其他函数。在这个情况下我们根本没有必要移动rsp指针来为栈桢申请内存。只要foo函数占用的内存不超过128个字节我们直接使用红区RedZone就行了。它的栈桢结构如下图所示这时rsp的值和rbp的值是相同的。
![图片](https://static001.geekbang.org/resource/image/94/54/942530836aecb652579f505a13a7ee54.jpg?wh=1920x1080)
关于红区的知识点,我仍然建议你阅读[ABI文档](https://gitee.com/richard-gong/craft-a-language/blob/master/13/System%20V%20Application%20Binary%20Interface%20AMD64%20Architecture%20Processor%20Supplement%20Draft%20Version%200.99.6.pdf),我在这里也贴了一小段,供你参考。
![图片](https://static001.geekbang.org/resource/image/9e/c7/9ec76b76c6da5d3b04469bac92876cc7.png?wh=1488x326 "来源System V Application Binary Interface AMD64 Architecture Processor Supplement Draft Version 0.99.6")
现在,栈桢维护的原理,我们已经讲清楚了,至于具体的计算栈桢大小、维护栈桢的代码,你可以在代码库中的[addPrologue](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L1262)和[addEpilogue](https://gitee.com/richard-gong/craft-a-language/blob/master/16-18/asm_x86-64.ts#L1312)两个函数中看到。在这里,你要特别关注一下其中计算栈桢大小的相关代码,以此为线索你就能搞清楚整个栈桢的内存布局了。我相信,在明白原理之后,你再阅读这些代码,可以保持一条比较清晰的思路。
## 课程小结
好了,今天的内容就是这些,到今天这节课为止,我们的语言已经能够为表达式计算和函数调用等功能生成汇编代码和可执行文件了。那么今天这节课,我希望你记住下面几个关键的知识点:
首先我们在采用简单的寄存器分配算法时通常是把参数、本地变量都保存到栈桢里但临时变量则要用使用寄存器在这个过程中我们加深了对x86指令的理解。像加减乘除等运算目标操作数应该是寄存器而对源操作数就没有这个要求了。另外mov指令虽然在源操作数和目标操作数中都可以使用内存地址但不能两个操作数都是内存地址。
第二我们再次熟悉了函数调用的约定也就是前6个参数用寄存器超过6个的参数使用Caller的栈桢。不过这次我们更细致地了解了从Caller和Callee中应该如何访问这些额外的参数。具体来说在Caller中我们要基于rsp寄存器来寻址但在Callee中则要基于rbp寄存器来寻址。
第三,在调用函数时,会发生寄存器使用冲突的情况,这个时候我们需要把保存在寄存器中的临时变量溢出到内存中,需要时再装载回来,而这两个操作使用的寄存器可能并不是同一个。
最后我们总结了栈桢的内存布局设计并指出了如何正确地移动栈顶指针rsp来申请内存。在这个过程中栈桢要保证16字节内存对齐。而对于叶子函数我们还可以直接使用RedZone不用移动栈顶指针rsp。不过这里要指出的是对于这个内存布局只有超过6个的额外参数的位置、返回地址的位置还有内存对齐等少量内容是由ABI规定的其他大部分栈桢空间都是语言的设计者自己决定如何使用的。
最后再补充一句,到目前为止,我在这节课提到的所有寄存器,都是与整数计算有关的寄存器。如果你要进行浮点数计算,使用的寄存器会是另外一组,我们在后面的课程里再详细介绍。
## 思考题
在这节课的示例代码中我们看到临时变量首先使用的是Caller保护的寄存变量比如eax而不是Callee保护的。这又是什么道理呢请你分析一下。
感谢你和我一起学习,也欢迎你把这节课分享给更多对生成本地代码感兴趣的朋友。我是宫文学,我们下节课见。
## 资源链接
[这节课的示例代码在这里!](https://gitee.com/richard-gong/craft-a-language/tree/master/16-18)