运行时刻环境 (Runtime Environment)

在讨论代码生成之前，我们先介绍一些关于如何组织可 执行代码（executable code）的常见做法 代码和数据在执行时是什么样子的？ 运行时刻环境： 代码和数据的存储分配 访问变量时使用的机制 过程之间的连接、参数传递的机制 和操作系统、目标机器的接口 重点讨论：过程调用的存储管理

从源代码到执行 a loader is a part of an OS

存储组织

存储组织 对目标程序运行时的逻辑地址空间的组织和管理 常见的编译器对于目标程序运行时刻的空间划分 包含代码区和数据区 以连续字节块存储 字节是内存最小的编址单位 一个字节是8个二进制位 4个字节构成一个机器字 ……

存储组织 代码区：放置可执行目标代码，在编 译时刻该区域的大小就可以确定。这 个区通常在存储的低地址端 静态区：程序的某些数据对象，如全 局变量和编译器产生的某些数据，它 们的大小可以在编译时刻知道 动态区域 为了将运行时刻空间利用率最大化，堆区 和栈区被放在剩余地址空间的两端。它们 的大小随着程序运行会发生改变 栈：存放活动记录（过程调用时有关机器 状态的信息）。通常向低地址方向增长 堆：malloc的数据对象。通常向高地址方 向增长

int x = 10; void func() { int a = 0; int int x = 10; void func() { int a = 0; int *p = &x; //p is pointing to the memory in data segment int *q = &a: //q is pointing to the memory in stack char *r = malloc(10); //r is pointing to memory in heap … }

空间的栈式分配 与过程调用相关的数据在栈中进行存储和管理 过程调用（过程的活动） 在时间上总是嵌套的 当一个过程被调用时，用于存放该过程的局部变量和 相关机器状态的空间（活动记录）被压入栈 当这个过程结束时，该空间从栈中弹出 过程调用（过程的活动） 在时间上总是嵌套的 后调用的先返回 因此用栈来分配过程活动所需内存空间

过程调用示例 使用递归的快速排序算法

活动树（activation tree） 程序运行期间的所有过程活动可以用树表示 每个结点对应于一个过程活动 根结点对应于main过程的活动 过程p的某次活动对应的结点的所有子结点 表示此次活动所调用的各个过程活动 从左向右，表示调用的先后顺序 一个子节点必须在其右兄弟节点的活动开始之前结束

活动树示例 过程调用序列和活动树的前序遍历相对应 过程返回序列和活动树的后序遍历相对应 假定控制流在某个过程的某次活动中，对应 于树上节点N。N及其祖先节点是当前活跃的 （未结束的）活动。这些活动被调用的顺序 是它们从根节点到N的路径上出现的顺序。 这些活动将按照该顺序的反向顺序返回。

活动记录（activation record） 对于每个过程活动，压入栈的数据和信息 也被称作stack frame 这个栈被称作call stack / control stack / runtime stack / stack 每个活跃的活动有一个位于栈中的活动记录 活动树的根位于栈底 当前程序控制所在活动的活动记录位于栈顶 栈中全部活动记录的序列对应于在活动树中从根节点 到达当前活跃的活动节点的路径 -- 所有的尚未返回 的过程调用

活动记录存储示例 x86 栈底 m 高地址 q(1, 9) q(1, 3) 栈顶 q(2, 3) 低地址

活动记录的内容 内容与所实现的语言相关 微处理器制造者会约定活动记录内容的某种布局 一般包括：函数实参、局部变量、返回地址等 称作calling conventions 如果所有编译器都使用同样的calling conventions，那 么一个编译器编译出的函数就可以调用另一个编译器 编译出的函数

本书中活动记录的内容： 临时变量：某些临时中间结果 局部数据：该函数的局部变量 靠近栈底/高地址 临时变量：某些临时中间结果 局部数据：该函数的局部变量 机器状态信息：在对此函数的此次调用之 前的机器状态信息（包括返回地址、寄存 器内容），函数返回时需要恢复这些信息 访问链：在其它活动记录中存放的数据， 访问时需要访问链进行定位（后面介绍） 控制链：指向调用者的活动记录 返回值：存放被调用函数返回给调用函数 的值 实参：存放调用函数提供的实在参数（尽 可能放在寄存器中） 靠近栈顶/低地址

例

调用代码序列、返回代码序列 调用代码序列（calling sequence）：实现函数调 用的代码段 为一个活动记录在栈中分配空间，并在此记录的字段 中填写信息 返回代码序列（return sequence）： 恢复机器状态，使得调用函数能够在调用结束后继续 执行的代码 一个调用代码序列通常被分割到调用者caller和 被调用者callee的代码中

调用代码序列如何分割？ 本书期望把调用代码序列中尽可能多的部分放在被调用者中。当然，被调用者不可能知道所有的事。 生成的代码 int f(int x, int y) { … } main() { a = f(1, 2); b = f(a, a); c = f(a, b); 调用代码序列中被调用者部分； 函数体 … 对f的第1次调用的调用代码序列中调用者部分； 对f的第2次调用的调用代码序列中调用者部分； 对f的第3次调用的调用代码序列中调用者部分； 本书期望把调用代码序列中尽可能多的部分放在被调用者中。当然，被调用者不可能知道所有的事。

调用代码序列的设计 要与活动记录布局的设计相呼应 可以遵循下列原则： 调用者和被调用者之间传递的值（实参、返回值）， 一般被放在被调用者活动记录的开始位置，因此它们 尽可能地靠近调用者的活动记录 好处： 调用者能够计算该次调用的实参的值并放在自身活动记录的 顶部，而不用创建整个被调用者的活动记录 调用者和被调用者都知道将来被调用者的返回值放在哪里

调用代码序列的设计 要与活动记录布局的设计相呼应 可以遵循下列原则： 调用者和被调用者之间传递的值（实参、返回值）， 一般被放在被调用者活动记录的开始位置，因此它们 尽可能地靠近调用者的活动记录 固定长度的项（包括控制链、访问链和机器状态字段） 放在记录的中间位置 开始不知道大小的项（例如临时变量）被放置在活动 记录的尾部 “栈顶”指针top_sp所指的位置：活动记录中固定长 度字段的末端 那么固定长度的数据就可以通过固定的相对于top_sp的偏移 量来访问

调用者和被调用者合作管理栈示例 调用代码序列 调用者计算实参的值 调用者将返回地址和 当前top_sp的值放在 被调用者的活动记录 中，然后增加top_sp 的值 被调用者保存寄存器 值和其它状态信息 被调用者初始化其局 部数据并开始执行 调用者也可以做！

调用者和被调用者合作管理栈示例 返回代码序列 被调用者将返回值放 在与参数相邻的位置 被调用者恢复top_sp 和其它寄存器，然后 跳转到由调用者放在 机器状态字段中的返 回地址 尽管top_sp已经被减 小，但调用者仍然可 以根据当前top_sp的 位置找到返回值

栈中非局部数据的访问 讨论过程如何访问数据 特别是，如何找到在过程p中使用但又不属于p 的数据

没有嵌套函数的数据访问 C语言的变量要么在某个函数内定义，要么在所 有函数之外定义 全局变量被分配在静态区，在编译时刻即确定它们的 位置 其他变量一定是栈顶活动记录里的局部变量，且偏移 量已知，可以通过top_sp指针加上偏移量来访问这些 变量

带嵌套函数的数据访问

带嵌套函数的数据访问

嵌套深度

访问链（access link） 在活动记录中增 加一个访问链指 针 若函数p直接嵌套 在函数q中，那么 p的任何活动记录 中的访问链都指 向最近的q的活动 记录 嵌套深度沿着访 问链路逐一递减

访问链 假定函数p的嵌套深度为np，它引用嵌套深度为nq的函数q声明的变量x，nq ≤ np。如何访问x的存储单元？ 从栈顶的活动记录开始，追踪访问链np - nq次，到达x的声明所在函数q的活动记录 x的地址由下面的二元组表示（在编译时刻已知）：(np – nq, x在活动记录中的偏移)

访问链的维护 当过程q调用过程p时 p的深度大于q：根据作用域规则，p必然在q中直接 定义；那么p的访问链指向当前活动记录(即q) 例如：sort调用quicksort(1, 9)

访问链的维护 当过程q调用过程p时 递归调用p= q：新活动记录的访问链等于当前访问链 (即和前一个活动记录q指向同一目标) 例如：quicksort(1, 9)调用quicksort(1, 3)

访问链的维护 当过程q调用过程p时 p的深度小于等于q的深度：必然有过程r，p直接在r中 定义，而q嵌套在r中；p的访问链指向栈中r的活动记录 例如：partition调用exchange 找到r：从q的活动记录开始，沿着访问链经过nq – np +1步就可以找到r

访问链

显示表 如果嵌套深度太大，可能需要沿着一段很长的访 问链路才能找到需要的数据 显示表是一个更高效的数据访问实现方法 设定一个数组d，它为每个嵌套深度保存一个指 针，指针d[i]指向栈中最高的对应于某个嵌套深 度为i的函数的活动记录 如果函数p正在运行，且它需要访问属于某个嵌 套深度为i的某个函数q的变量x，那么只要查看 d[i]就可以找到q的活动记录，进而访问到x 注意 i = nq ≤ np

显示表的维护 需要在新的活动 记录p中保存显 示表条目的原来 的值。从而在p 返回时可以恢复 到调用前的值。

本章总结 运行时刻存储组织 栈、活动记录、栈中非局部数据访问