栈式分配

活动树

过程调用（过程活动）在时间上总是嵌套的，后调用的先返回，因此用栈来分配过程活动所需内存空间。

程序运行的所有过程都可以用树表示，每个节点对应于一个过程活动，根节点对应于main过程的活动，过程p的某次活动对应的节点的所有子节点表示此次活动所调用的各个过程活动，从左到右表示调用的先后顺序。

又称为调用树。

过程调用（返回）序列和活动树的前序（后序）遍历对应。假定当前活动对应节点N，那么尚未结束的活动对应于N及其祖先节点。

活动记录

过程调用和返回由控制栈进行管理，每个活跃的活动对应于栈中的一个活动记录。活动记录按照活动的开始时间，从栈底到栈顶排列。

向下增长的活动记录栈

a[11]为全局变量，位于控制栈的顶部。main无局部变量，r有局部变量i，位于r的下方；q有局部变量i和参数m、n，参数位于q的上方。

调用代码序列

调用代码序列（Calling sequence）为活动记录分配空间，填写记录中的信息。

返回代码序列（Return sequence）恢复调用者状态，使调用者继续运行。

调用代码序列会分割到调用者和被调用者中，根据源语言、目标语言和操作系统的限制，可以有不同的分割方案。但是要把代码尽可能放在被调用者中。

调用/返回代码序列的要求

数据方面：能够把参数正确地传递给被调用者；能够把返回值传递给调用者；

控制方面：能够正确转到被调用过程的代码开始位置；能够正确转回调用者的调用位置（的下一条指令）；

调用代码序列与活动记录的布局相关

活动记录的布局原则

• 调用者和被调用者之间传递的值放在被调用者活动记录的开始位置（实在参数和返回值）

• 固定长度的项（控制链、访问链和机器状态字段）放在中间位置

• 早期不知道大小的项在活动记录尾部

• 栈顶指针通常指向固定长度字段的末端

调用序列：

• 调用者计算实在参数的值

• 调用者将返回地址和原栈顶指针放到被调用者的活动记录中；调用者增加栈顶指针的值（越过了调用者的局部数据和临时变量、以及被调用者的参数和机器状态字段）

• 调用者保存寄存器值和其他状态字段

• 被调用者初始化局部数据并开始执行

返回序列：

• 被调用者将返回值放到与参数相邻的位置

• 恢复栈顶指针和寄存器，跳转到返回地址

栈中的变长数据

如果数据对象的生命期局限于过程活动的生命期，就可以分配在运行时刻栈中。变长数据也可以。

top指向实际栈顶、top_sp用于寻找顶层记录的定长字段。