运行时环境管理
　　
　　
　　
6.1  引言
　　运行时环境主要涉及到程序执行期间的情况。程序通常包括以下3部分：
● 程序的代码
● 静态和全局变量
● 本地变量和参数
　　以上3部分都需要适当的内层分配来保存其值。因此，以下介绍了运行时需要管理的3种实体：
　　(1) 生成的代码。对于构成文本或代码段的不同过程和程序，该段的大小在编译时才能知道。因此，在运行开始前可以静态地分配空间。
　　(2) 数据对象。可以为以下不同的类型：
● 全局变量/常量：全局变量或常量所需的空间大小在编译时可以确定。
● 局部变量：局部变量的大小同样也只在编译时确定。
● 动态创建的变量：在程序执行期间，该变量为请求内层分配所创建的空间。既然取决于程序的执行序列，因此所需的空间在编译时是未知的。动态分配的过程是在堆中进行的。
　　(3) 堆栈：跟踪过程的活动。
　　图6-1显示了程序的逻辑地址空间，代码位于最底层。静态部分分配了全局变量。在剩余的地址空间中，堆和栈从相对的两侧分配空间，具有最大的灵活性。而程序不会使用过多的动态空间，因此堆使用得较少。但是由于存在大量的嵌套程序调用，会使用大量的栈空间。对于其他程序情况也可能相反。因此也证明了堆和栈从相对的两侧进行分配。
代码
静态部分
堆
→ 空闲空间 ←
栈
低



高
图6-1  程序的逻辑地址空间
6.2  活动记录
　　在活动的程序中，变量需要存放在某些存储空间中。该存储空间又称为活动记录或帧。典型的活动记录如下：
● 传递给过程的参数。
● 簿记(bookkeeping)信息，包括返回地址。
● 局部变量的空间。
● 局部临时变量的空间，由编译器生成，用于存放子表达式的值。
　　图6-2显示了该结构。所有过程都是同样固定了标记消息的大小。编译器可以决定其他程序段的大小。
参数的空间(参数)
簿记信息的空间，包括返回地址
局部变量的空间
局部临时变量的空间
图6-2  典型的活动记录
　　根据语言，可以在静态、栈或堆区域中创建活动记录。在早期的语言如Fortran中，活动记录在静态区域中创建。因此在不同过程中，参数使用的地址以及定义的变量会在编译时预先设置。编译器使用这些静态位置生成代码。要传递这些参数，在调用过程时会将这些值复制到静态位置中，而在返回时再从静态位置中复制回来。该分配的主要难点在于过程调用时使用相同空间。因此在任何时刻，只能有一个活动的过程，不可能实现递归过程。创建活动记录的另一个选择是在栈中，常用于C、Pascal和Java语言等。当调用过程时，会将相应的活动记录压入堆栈中。在返回时，会弹出该记录项。这适用于当超过过程体时局部变量不再需要的情况。而对于像LISP这样的语言，允许返回整个函数，则该活动记录的分配是在堆中完成的。
　　应当注意，处理器的寄存器也作为运行时环境的一部分。它们用于存储临时变量、局部变量、全局变量以及其他特定的信息。例如，当堆栈指针指向栈顶时，程序计数器则指向下一条要执行的语句。而一些寄存器则用于追踪过程的活动。
● 帧指针(fp)：指向当前活动的记录。
● 参数指针(ap)：指向保存参数的活动记录的区域。
　　活动记录的结构即其包含的字段，根据语言的不同而不同。如果语言支持过程的嵌套定义，则可以通过一些作用域规则定义可以访问的变量。
　　现在将介绍两类不同的运行时环境以及它们相关联的活动记录结构。
　　(1) 不含有局部过程，基于栈的环境。
　　(2) 含有本地过程，基于栈的环境。
　　第一种类型常用于C语言，而第二种类型常用于如Pascal这样的代码块结构的语言。
6.2.1  不含局部过程的环境
　　如果语言中所有的过程都是全局的，那么基于栈的环境需要关于活动记录的两个条件：
　　(1) 维持当前活动记录的指针，运行其访问局部变量和参数，这通常称为帧指针(fp)。
　　(2) 之前活动记录的位置记录，以便当前调用结束时可以重新检索。通常依靠指向之前活动记录的指针来在当前活动记录中保存该信息。该指针又称为控制链或动态链。
　　示例6.1  考虑以下C代码，该程序除了main函数外，还包括两个相互递归的函数f和g。
　　　　
　　main函数调用函数g，而g有条件地调用函数f。然后函数f再调用g。f中静态的整型变量x作为全局变量，因此即使在f外执行，x值仍然会保留。图6-3显示了程序的执行图。图中，main函数调用g，g调用f，然后f再调用g，这次执行为g的第二次调用。

图6-3  示例图
　　1. 访问变量
　　通过当前帧指针的偏移量可以找到参数和局部变量。编译器能静态地计算偏移量，如以下示例所示。
　　示例6.2  思考含有参数m和局部变量y的过程g，过程g的每次调用都具有相同结构的活动记录。参数和局部变量的位置相对于帧指针具有固定的偏移量。图6-4显示了该结构。进一步来看，假设控制链接和返回地址的字段都为4个字节。m距帧指针的偏移量为：
　　mOffset = 控制链接的大小 = +4字节
　　类似地，y到帧指针的偏移量为
　　yOffset = –(y的大小 + 返回地址的大小) = –6
　　因此，分别通过偏移量4(fp)和–6(fp)可以访问m和y。

图6-4  计算变量的偏移量
　　2. 创建活动记录
　　当调用过程时，即创建了活动记录。因为活动记录的组成部分包括了传递参数和局部变量，因此其不能完全由调用程序和被调用程序创建。调用程序和被调用程序在调用时都有其特定的任务，称为调用序列。当返回时称为返回序列。表6-1演示了该调用操作。
表6-1  创建活动记录
调  用  时
调 用 程 序
被调用程序
1. 分配基本帧
2. 存储参数
3. 存储返回地址
4. 存储调用程序的存储寄存器
5. 存储自身的帧指针
6. 为子程序设置帧指针
7. 跳至子程序
1. 存储被调用程序的存储寄存器和状态
2. 扩展帧(用于局部过程)
3. 初始化局部过程
4. fall through(落空)代码
返  回  时
调 用 程 序
被调用程序
1. 复制返回值
2. 释放基本帧
3. 还原调用程序的存储寄存器
1. 存储返回值
2. 恢复被调用程序的存储寄存器和状态
3. 未扩展的帧
4. 恢复父过程的帧指针
5. 跳转至返回地址
　　
6.2.2  含有局部过程的环境
　　前面章节介绍的运行的支持还不足以支持局部过程的环境。这是因为现在定义的变量具有不同的作用域。要判断引用变量所使用的定义，需要访问非局部、非全局的变量。这些定义相对于嵌套当前定义的过程是局部的。因此，需要查看嵌套过程的活动记录来决定位置。
　　解决方法是添加额外的标记信息，称为访问链。访问链指向了定义程序环境的活动记录。
　　示例6.3  考虑如下程序段：
　　　　
　　　　
　　图6-5显示了相应的活动记录。当前过程为r。要确定x的位置，需要使用访问链遍历活动记录。最终，当需要到达包含x定义的过程时，通过相应帧指针的偏移量来访问。

图6-5  访问链
　　编译器的任务是生成合适的代码，并访问正确的定义，这包含如下操作：
　　(1) 找出声明名称的词法嵌套层和引用过程的词法嵌套层之间的差异d。
　　(2) 生成沿d的访问链到达正确的活动记录的代码。
　　(3) 生成通过偏移量机制访问变量的代码。
　　示例6.4  考虑如下程序，该程序含有一组嵌套的过程。
　　　　
　　图6-6显示了含有词法层的过程嵌套图。图6-7显示了一些程序的活动记录图。标注为实线的链接为控制链，而标注为点的链接为访问链。图6-7 (a)显示了M调用P、P调用Q、而Q调用R的情况。图6-7 (b)显示了R递归调用P后的情况。这里，P的控制链接指向R，而访问链指向M，M为次高的词法嵌套层。图6-7显示了P另外调用Q后的情况。这里，控制和访问链都指向P的第二次调用，因为P为Q第二次调用的词法和逻辑上的前身。

图6-6  嵌套的过程

图6-7  活动记录
6.3  display
　　访问非局部定义所面临的主要难点在于按照访问链搜索。由于是虚拟的页面环境，含有活动记录的堆栈中可能存在部分的页面交换。因此，访问可能非常慢。为了解决该问题并且不需要搜索就能访问变量，则需要用到display。
　　display d是活动记录的全局指针数组，其索引取决于词法嵌套的深度。display中元素的数量在编译时根据最大的嵌套深度来计算。数组元素d[i]指向嵌套深度i的代码块中最近的活动。而非局部变量X可以按以下方式找到：
　　(1) 使用数组访问可以找到包含X的活动记录。如果最靠近X嵌套声明的深度为i，则d[i]指向包含X位置的活动记录。
　　(2) 使用活动记录中的相对地址访问X。
　　示例6.5  对于示例6.4的程序代码，图6-8显示了活动记录和display的图。因为最大的嵌套深度是4，则display中只有4项。图6-8 (a)显示了程序M调用过程P、P调用Q、Q再调用R的情况。编译器知道在词法层2中，过程P的定义x是可用的，因此将生成代码访问display中的第二项，并直接到达P的活动记录。现在假设R调用P，将创建另一个活动记录并将其压入堆栈中。但是，P中引用的变量应当是P中的局部变量或者在M中可用。因此，display中仅有的两项分别为到M的值–1和到P的值2，如图6-8 (b)所示。

图6-8  使用display表示活动记录
　　当调用嵌套深度i的过程P时，会执行以下动作：
　　(1) 保存P的活动记录中d[i]的值。
　　(2) 设置d[i]指向新的活动记录。
　　类似地，当过程P结束后，将重新设置d[i]来存储P的活动记录中存储的值。这将确保在过程调用和返回时，能正确地设置和恢复display中的项。
6.4  小结
　　本章介绍了在程序执行期间有效管理存储的策略，同时引入了一种称为活动记录的特殊的数据结构，活动记录包含了控制程序执行的必要信息。编译器编写者必须要生成适当的代码维护这些活动记录，并确保在程序执行期间通过这些活动记录正确地访问变量。一种称为display的小型数组有助于以上过程的实现。但是，对display的管理成了编译器任务的一部分。
练习
　　6.1 如何理解运行时内存的分配？并解释静态和动态分配的差异。
　　6.2 解释静态分配的语言不支持递归的原因。
　　6.3 说出活动记录的定义，并详细解释活动记录的组成部分。
　　6.4 解释对于在堆栈中创建活动记录的语言，不推荐将大规模的数组作为局部变量和参数的原因。
　　6.5 C语言使用的是按值返回的参数传递，即在函数调用时，将形参复制到实参中。这意味着在实参中的修改不会影响实际的程序。但是，这不适用于数组。解释当进行分配时出现这一情况的原因，以及对该模式的看法。
　　6.6 在以下程序中第6、11、14、17行语句执行时，画出活动记录堆栈的图。
     (1)  Program X
     (2)  var x,y,z;
     (3)  Procedure P
     (4)    var a;
     (5)  begin (of P)
     (6)    a = Q
     (7)  end (of P)
     (8)  Procedure Q
     (9)    Procedure R
     (10)   begin (of R)
     (11)     P
     (12)  end (of R)
     (13)  begin (of Q)
     (14)     R
     (15)  end (of Q)
     (16)  begin (of X)
     (17)     P
     (18)     Q
     (19)  end (of X)
　　6.7 简述display的定义及其有助于加速程序执行的方式。
　　6.8 对于问题6.6，画出其相应的display。
　　
　　
　　
　　
　　
　　
　　
　　
??
　　
　　??
　　
　　??
　　
　　??
　　
编译器设计
　　
第6章  运行时环境管理
　　
108
　　
　　
107