运行时命名支持
为了实现过程调用和词法作用域名称空间的双重抽象，编译器和运行时系统必须建立一组运行时数据结构。涉及控制和命名的关键结构是激活记录（AR），即与单个过程激活相关联的一块私有内存。每次过程调用都会产生一个新的激活记录或者称为调用记录。
- 编译器必须生成代码，使得调用者将返回地址存储在被调用者的激活记录（AR）中。
- 编译器需要将在调用处的实际参数映射到被调用者中可访问的形式参数。此参数信息会放入被调用者的AR中。
- 编译器必须为在被调用者中声明的局部变量创建存储空间。对于那些生命周期与过程调用相匹配的值，其存储空间会被放入被调用者的AR中。
- 编译器还必须提供其他信息给被调用者，以便其能够连接到调用上下文并允许它与其他过程进行交互。这些数据也会放入被调用者的AR中。
- 参数区存放了来自调用点的实际参数，其顺序由它们在调用点出现的顺序决定。
- 寄存器保存区包含足够的空间来保存过程中跨过程调用必须保留的寄存器值。返回值槽提供了在需要时从被调用者回传数据到调用者的空间。
- 返回地址槽存放了当被调用者终止时控制权应返回的运行时地址。
- 可寻址性槽存放了让被调用者能够访问周围词法作用域内局部变量的信息。
- 在被调用者的ARP处的槽位保存了调用者的ARP，以便被调用者在返回时可以恢复调用者的环境。
- 局部数据区存放了在被调用者的局部作用域中声明的、被调用者无法保持在寄存器中的变量，以及编译器需要存储的其他值。
为了提高效率，图中ARs所示的部分信息可能会保存在专用寄存器中。
如果源语言允许程序员为变量指定初始值，编译器必须确保这些初始化操作得以执行。对于静态分配的变量，数据可以直接插入到静态数据区中的适当位置。
存储在AR（活动记录）中的变量必须在运行时进行初始化。因为一个过程可能会被多次调用，编译器必须发出指令来在每次调用时执行初始化。实际上，这些初始化就是赋值操作，在每次调用过程前，即过程的第一个语句之前执行。
当p调用q时，其中一个必须保存p在调用之后需要的寄存器值。可能需要保存所有寄存器的值；另一方面，保存一部分也可能就足够了。在返回到p时，这些保存的值必须被恢复。这些保存寄存器值的生命周期与被调函数的生命周期相匹配。因此，编译器可以在被调方的AR或调用方的AR中保存它们。如果调用方在跳转到被调方之前保存了一个寄存器，它会将值保存到自己的AR中。同样，如果被调方在开始执行之前保存了一个寄存器，它也会将其值保存到自己的AR中。因此，AR需要有足够的容量来存储一套完整的调用方保存和被调方保存的寄存器。由于调用方在调用前保存并在调用后恢复寄存器值，它可以在每次调用时重复使用相同的调用方保存寄存器的空间。
提示
调用方保存寄存器
如果调用方有责任在一次调用前后保持寄存器r的值不变，我们称r为调用方保存寄存器（caller-saves register）。这意味着在调用其他函数之前，调用方需要将寄存器r中的重要值保存到自己的活动记录(AR)中，并在被调函数执行完毕后恢复这些值。
被调方保存寄存器
如果被调方有责任在其自身执行期间保持寄存器r的值不变，我们称r为被调方保存寄存器（callee-saves register）。这意味着若被调函数使用了寄存器r，且其值在函数执行前后的状态需要保持一致，那么被调函数必须负责在函数开始时保存r的值，在函数结束前恢复r的原始值。这种机制确保了调用者无需关心被调函数内部对寄存器的使用情况，只要被调函数遵循这一约定即可。
当过程p调用过程q时，调用的代码必须为q分配并初始化一个活动记录(AR)。因为过程调用是频繁发生的，编译器编写者应该尽量保持这种分配的成本尽可能低。一般来说，编译器编写者在AR分配上有三种选择：栈分配、堆分配和静态分配。
- 栈分配（Stack Allocation）: 利用运行时栈来分配新的活动记录。这种方式非常高效，因为分配和释放仅涉及调整栈指针的位置。
- 堆分配（Heap Allocation）: 在堆内存中动态分配活动记录。虽然这种方法提供了更大的灵活性，但其分配和回收成本较高，并且需要垃圾回收机制来管理不再使用的内存。
- 静态分配（Static Allocation）: 在编译期为每个过程分配固定的内存空间。这种方法简单且效率高，但是缺乏灵活性，因为它无法支持递归调用或是在编译期无法确定数量的过程调用。
面向对象语言（OOL）需要特定的运行时结构来支持其词法层次结构和类层次结构。与算法语言类似，方法控制信息和局部名称存储使用激活记录（ARs）。然而，由于对象的生命周期独立于方法调用，每个对象需要自己的对象记录（OR）来保存状态。OR包含指向类和方法向量的指针，以及类特定数据成员。在单继承情况下，子类对象记录按照前缀布局方案组织，继承的数据成员与父类保持相同偏移量，新增成员位于其后。这种结构支持高效的方法查找和继承机制，是面向对象语言运行时支持的核心组成部分。
为了支持开放的类层次结构，编译器需要为每个方法名生成搜索键，并维护(类，键)到实现的映射。运行时系统通过方法缓存优化查找过程，缓存包含键、类和代码指针。动态调度首先检查缓存，未命中时沿类层次结构向上搜索。为了提高性能，系统可以使用内联方法缓存，在每个调用点存储最近使用的类和代码指针。当类层次结构发生变化时，需要使相关缓存条目失效，可以通过清除缓存或生成新标签来实现。这些机制共同构成了面向对象语言高效方法调度的基础。
图(a)和(b)重复了第5章的例子。图(c)显示了同时实例化一个Point和一个ColorPoint后可能出现的运行时结构。所有的Point、ColorPoint、aPoint和aColorPoint都有它们自己的OR。类的OR不在本页范围内。
aPoint的OR很简单。它包含一个指向aPoint类的指针，一个指向aPoint方法向量的指针（来自Point类），以及用于Point数据成员的空间。
aColorPoint的OR同样简单。它包含一个指向aColorPoint类的指针，一个指向其方法向量的指针（来自ColorPoint类），以及用于ColorPoint数据成员的空间。根据第255页第5.6.3节讨论的单继承布局方案，数据成员按照前缀布局方案排序。因此，继承的数据成员x, y和z位于与Point实例相同的偏移位置，而ColorPoint中声明的数据成员则位于它们下方。
类的OR具有类似的结构。每个类的OR包含一个类指针。它们的代码指针（未显示）会指向类中的方法向量。类的OR展示了方法向量和超类指针。毫无疑问，类的OR会包含额外的类特定成员。
当创建对象时会明确地分配OR（对象记录），并在对象不再可达时释放。大多数OR都是在堆上分配的，因为对象的生命周期通常不与某个方法的一次激活相关联。如果一个对象的生命周期受限于某个方法的激活，那么其OR可以存储在为该方法创建的AR（活动记录）内部。分析可以揭示出原本需要在堆上分配的OR，在某些情况下可以改为存放在某个方法的AR中。这一转换可以降低分配的开销以及堆管理的成本。
aColorPoint的对象记录中包含的代码指针指向的是ColorPoint而非Point提供的方法向量。因此，相对于aColorPoint调用draw实际上是调用了ColorPoint.draw；而相对于aPoint调用draw则是调用了Point.draw。最后，如果将aColorPoint转换为Point，则应当使用Point的方法向量并调用Point.draw。
图中的例子展示了每个类都有一个完整的方法向量。因此，ColorPoint的方法向量包括了指向ColorPoint.draw、Point.move以及colorPoint.setc的指针。这个向量反映了通过继承层次解决这些名称的结果。这种方法达到了预期的效果——即x类的对象调用了从x类内部可见的方法的实现。
作为替代方案，编译器可以在其类方法向量中仅表示colorPoint的本地方法。方法名称会被解析为一个坐标，这个坐标告诉编译器沿着超类链向上查找多少步才能找到代码指针。编译器会生成代码来沿超类链向上追踪到正确的层级，然后检索代码指针。完整的方法向量虽然会稍微增加一些运行时的空间需求，但却可以节省运行时间。
到目前为止的讨论表明，每个方法调用都需要通过接收者的对象结构（Object Representation, OR）查找以定位方法的实现。在具有封闭类结构的语言中，编译器可以在编译时将方法名解析为特定的实现，并生成直接调用。例如，在C++中，除非方法被声明为虚方法，否则编译器可以在编译时将任何方法解析为其具体的实现——这里所谓的虚方法，基本上意味着程序员希望根据接收者的类来定位实现。
对于虚方法，调度使用适当的方法向量来定位实现。编译器会发出代码以跟随从对象结构到类方法向量再到代码指针的路径，这个过程常被称为动态调度。然而，如果C++编译器能够证明某个虚方法调用有一个已知不变的接收者类，它可以生成一个直接调用，这有时被称为静态调度。
为了支持开放的类层次结构，编译器为每个方法生成搜索键，并维护（类，键）到实现的映射。动态调度首先在方法缓存中查找（类，键）对，若命中则直接使用对应的代码指针；未命中时，则沿类的继承链向上搜索，并将找到的结果缓存。缓存策略如最近最少使用来管理缓存条目的替换。此外，内联方法缓存针对单个调用点优化，存储上次调用的类和代码指针，匹配时直接使用。类层次结构变化时，需使相关缓存条目失效并更新缓存。
类似于Algol的语言通常使用词法作用域，其中命名空间被正确嵌套，新实例的名称会遮蔽旧的实例。每次调用都会为被调用者创建一个活动记录，其中包括被调用者的本地数据区。面向对象语言则在命名空间中添加了一个基于继承的层次结构，这个结构依赖于类定义。这种双重层次结构的命名空间导致了名称之间更复杂的交互和更为复杂的实现。
两种命名风格都需要运行时结构来反映和实现命名层次。在类似Algol的语言(ALL)中，活动记录捕捉了命名空间的结构，为大多数值提供了必要的存储，并保留了正确执行所需的状态。在面向对象语言(OOL)中，方法的活动记录仍然捕捉命名空间的词法作用域部分和执行状态。然而，其实现还需要一个对象记录的层次结构来捕捉基于继承的命名空间。
更新日志
a7ee6-于