运行时刻环境 (Runtime Environment)

Presentation on theme: "运行时刻环境 (Runtime Environment)"— Presentation transcript:

1 运行时刻环境 (Runtime Environment)

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

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

4 存储组织

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

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

7 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 … }

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

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

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

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

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

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

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

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

16 例

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

18 调用代码序列如何分割？ 本书期望把调用代码序列中尽可能多的部分放在被调用者中。当然，被调用者不可能知道所有的事。
生成的代码 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次调用的调用代码序列中调用者部分； 本书期望把调用代码序列中尽可能多的部分放在被调用者中。当然，被调用者不可能知道所有的事。

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

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

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

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

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

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

25 带嵌套函数的数据访问

26 带嵌套函数的数据访问

27 嵌套深度

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

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

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

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

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

33 访问链

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

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

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