做个编译器——运行时组织

参数传递 #

值得说的传递方式有传结果、传名字。

此外比较熟悉的有传地址（引用）、传值。

对于一段程序，可能采用上述四种不同的参数传递方式，能分别得出完全不同的执行结果。

传结果 #

对于每个形式参数，其用2个逻辑单元来代表。第一个单元保存其地址，第二个单元保存其值。在过程体中，对这些参数的操作是对保存其值的单元的操作。

当过程执行结束返回时候，才会遍历参数表，把每个参数的值单元的内容写回其地址。

传名字 #

相当于把被调用的过程体整个抄到调用语句处，替换掉该调用语句。在其中出现的形式参数都被原地替换成实际参数。

如果实际参数与过程体内的局部变量重名，则在抄写的时候修改那些局部变量的名字，而不是实际参数的。

替换完成后，执行替换后的程序。

过程的活动 #

过程及其活动生存期 #

一个过程的活动指该过程的一次执行。活动的生存期即该过程的第一步操作到最后一步操作之间经历的时间。如果在执行该过程的过程中还调用了其他过程，则也包含在内。

过程的活动记录 #

在活动生存期内，该过程所需的存储单元必须是已经分配到位的。该工作由编译器完成。

过程所需要的这段存储空间是这段过程独享的，标志了过程活动的存在性。这段空间称为活动记录。

过程的活动记录一般采取栈式分配，存放在栈区中。每次进入新的过程，它的活动记录就被压入栈区。相应的，当过程执行完毕，其活动记录被弹出。显然，用栈式分配来管理活动记录能很好地体现过程调用的层次性。

运行时存储器的划分 #

运行时所需的存储空间主要包括代码空间、数据空间、控制连接数据空间。

需要考虑的问题 #

是否允许递归？——决定是动态分配还是静态分配

过程结束，是否释放局部变量的空间，使之不再可被访问？

内层能否访问外层变量？

如何传递参数？

是否支持动态存储分配？是否需要显式释放动态分配的空间？

空间动态分配策略 #

什么是动态分配 #

如果一个程序在编译阶段就可以确定要占用的空间大小，那么可以采用静态分配策略，在编译时即直接确定各个单元的内容。

如果程序需要new，delete等概念，完成对内存的动态申请与释放，就必须采用动态分配策略。

如果程序需要支持递归，那么同一个过程会被多次进入，导致内存中同时有多个该过程的活动记录，且其数量取决于递归深度，在编译时不可能确定。这只有动态空间分配能做到。

动态分配主要包括栈式分配和堆式分配两种策略。

栈区采用栈式分配策略。对于过程调用的应用场景，其遵循先进后出的栈式顺序，很适合栈式分配策略。

堆区采用堆式分配策略。考虑如下场景，如果在过程中使用了动态内存申请，例如用了new，那么其空间的释放就与过程的进入与退出没有关系了，所以对于这些动态变量，我们采取堆式分配。这些动态变量是不受过程调用的栈式分配管理的，而是单独在堆区进行管理。

嵌套过程语言的变量访问问题 #

对于C语言中的过程嵌套调用，亦或是Pascal中的begin end中套begin end，都允许在一个过程中进入另一个过程，且内部过程中能访问外层变量。

例如如图，B2过程可以访问到变量Y。可是B1和B2的活动记录是分开存放的，如何保证B2可以访问到B1的局部变量呢？

层次和偏移量定址法 #

首先规定几个概念。

• 层次：当前过程所处的嵌套层次。约定主程序的层次是0。
• 偏移量：在当前过程中的局部变量相对于活动记录起点的偏移量。

于是，可以利用层次和偏移量去确定某过程中的某符号的地址。

动态链（控制链） #

动态链实际上是老SP，也就是调用者的活动记录的起始地址（SP）。每次进入一个过程，都会先把SP的值保存到栈里，作为新栈帧的栈底。这个保存的老SP又称动态链（改个名来唬人）。

静态链（存取链） #

静态链指向该过程的直接外层过程的活动记录起始地址（SP）。

调用者和直接外层不一定是同一个。例如上面那个图，B2如果递归，则递归过程中的B2的调用者是B2，但是直接外层是B1.

为什么静态链是个SP备份值，却被称为链？因为如果递归地找下去，就可以从内层活动逐步向外层找出去，进而可以实现内层过程对外面任意层中的局部变量的访问了。

已知要访问的变量所在的层次和相对偏移量，就可以利用静态链去访问他了。我们只需要沿着静态链递归地走两者的层次差的步数，然后取相对找到的栈帧的偏移量处的单元即可。

静态链的确定 #

第N层调用N+1层，被调者的静态链就是调用者的SP

第N层调第N层，被调者的静态链就是调用者的静态链

第N层调第N-x层，被调者的静态链就是调用者沿着其静态链走x步的活动记录的静态链的值

• 因为这是内层调用外层，所以如果要通过这个内层拿到这个外层的活动记录的直接外层，需要通过这个内层先走到这个外层层次上的某个活动记录，取该活动记录的静态链的值就是被调者静态链的活动记录的值了。因为走了x步到达的活动记录和被调者活动记录处于同层。

栈帧格局 #

• 在这个图中，栈是向上增长的。这请与全局的那个图区分开，因为那个图里面栈是向下增长的。
• SP永远指向当前栈帧底，TOP永远指向栈帧顶。（区分：在x86汇编里面，SP是栈顶，BP是栈底）
• 当进入一个过程，第一件事就是保存原来的SP（作为动态链），然后把SP移动到SP保存处，一个新的栈帧产生了。
• 返回地址夹在动态链和静态链之间。
• 静态链入栈后，依次入栈参数个数、各形参、各局部变量。

从格局上可以看出，变量的相对偏移肯定要>=4的。因为下面三个偏移位置（0,1,2,3）存放的是别的信息，不是变量。