China-pub.com 下载 第7章 运行时环境 本章要点 ·程序执行时的存储器组织 ·动态存储 ·完全静态运行时环境 ·参数传递机制 ·基于栈的运行时环境 ·TNY语言的运行时环境 在前几章中，我们已研究了实现源语言静态分析的编译程序各阶段。该内容包括了扫描 分析和静态语义分析。这个分析仅仅取决于源语言的特性，它与目标（汇编或机器）语言及目标 机器和它的操作系统的特性完全无关。 在本章及下一章中，我们将转向研究编译程序如何生成可执行代码的问题。这个研究包括 了附加分析，例如由优化程序实现的分析，其中的一些可以与机器无关。但是代码生成的许 多任务都依赖于具体的目标机器。然而同样地代码生成的一般特征在体系结构上仍保留了很 大的变化。运行时环境(runtime environment)尤为如此，运行时环境指的是目标计算机的寄存 器以及存储器的结构，用来管理存储器并保存指导执行过程所需的信息。实际上，几乎所有 的程序设计语言都使用运行时环境的3个类型中的某一个，它的主要结构并不依赖于目标机器 的特定细节。环境的这3个类型分别是：FORTRAN77的完全静态环境(fully static environment) 特征、像C、C++、Pascall以及Ada这些语言的基于栈的环境(stack-based environment),以及 像LISP这样的函数语言的完全动态环境(fully dynamic environment))。这3种类型的混合形式 也是可能的。 本章将按顺序逐个讨论这3种环境，还指出哪些环境是可行的语言特征以及它们必须具有 的特性。这包括了作用域及分配问题、过程调用的本质和不同的参数传递机制。这一章集中讨 论的是环境的一般结构，而第8章着重于维护环境需要生成的真实代码。在这一点上，大家应 记住编译程序只能间接地维护环境，在程序执行期间它必须生成代码进行必要的维护操作。相 反地由于解释程序可以在其自己的数据结构中直接维护环境，因而它的任务就很简单。 本章的第一节包括了对所有运行时环境的一般特征及其与目标机器的体系结构之间的关系 的论述：之后的两节探讨了静态环境和基于栈的环境，以及执行时的操作示例。由于基于栈的 环境是最常见的，所以我们对于基于栈系统的不同变型和结构又要着重讲述。在这之后是一些 动态存储问题，其中包括了完全动态环境和面向对象的环境。下面还会讲到有关环境操作的名 种参数传递技术。本章最后简要描述了实现TNY语言所需的简单环境。 7.1程序执行时的存储器组织 典型计算机的存储器可分为寄存器区域和较慢的直接编址的随机访问存储器(RAM)。 RAM区域还可再分为代码区和数据区。在绝大多数的语言中，执行时不可能改变代码区，且 在概念上可将代码和数据区看作是独立的。另外由于代码区在执行之前是固定，所以在编译时 所有代码的地址都是可计算的，代码区可如下所示：
下载 第7章 运行时环境 本章要点 • 程序执行时的存储器组织 • 动态存储 • 完全静态运行时环境 • 参数传递机制 • 基于栈的运行时环境 • TINY语言的运行时环境 在前几章中，我们已研究了实现源语言静态分析的编译程序各阶段。该内容包括了扫描、 分析和静态语义分析。这个分析仅仅取决于源语言的特性，它与目标 (汇编或机器)语言及目标 机器和它的操作系统的特性完全无关。 在本章及下一章中，我们将转向研究编译程序如何生成可执行代码的问题。这个研究包括 了附加分析，例如由优化程序实现的分析，其中的一些可以与机器无关。但是代码生成的许 多任务都依赖于具体的目标机器。然而同样地代码生成的一般特征在体系结构上仍保留了很 大的变化。运行时环境 (runtime environment)尤为如此，运行时环境指的是目标计算机的寄存 器以及存储器的结构，用来管理存储器并保存指导执行过程所需的信息。实际上，几乎所有 的程序设计语言都使用运行时环境的 3个类型中的某一个，它的主要结构并不依赖于目标机器 的特定细节。环境的这3个类型分别是：F O RT R A N 7 7的完全静态环境(fully static environment) 特征、像C、C + +、P a s c a l以及A d a这些语言的基于栈的环境 (stack-based environment)，以及 像L I S P这样的函数语言的完全动态环境 (fully dynamic environment)。这3种类型的混合形式 也是可能的。 本章将按顺序逐个讨论这 3种环境，还指出哪些环境是可行的语言特征以及它们必须具有 的特性。这包括了作用域及分配问题、过程调用的本质和不同的参数传递机制。这一章集中讨 论的是环境的一般结构，而第 8章着重于维护环境需要生成的真实代码。在这一点上，大家应 记住编译程序只能间接地维护环境，在程序执行期间它必须生成代码进行必要的维护操作。相 反地由于解释程序可以在其自己的数据结构中直接维护环境，因而它的任务就很简单。 本章的第一节包括了对所有运行时环境的一般特征及其与目标机器的体系结构之间的关系 的论述；之后的两节探讨了静态环境和基于栈的环境，以及执行时的操作示例。由于基于栈的 环境是最常见的，所以我们对于基于栈系统的不同变型和结构又要着重讲述。在这之后是一些 动态存储问题，其中包括了完全动态环境和面向对象的环境。下面还会讲到有关环境操作的各 种参数传递技术。本章最后简要描述了实现 T I N Y语言所需的简单环境。 7.1 程序执行时的存储器组织 典型计算机的存储器可分为寄存器区域和较慢的直接编址的随机访问存储器 ( R A M )。 R A M区域还可再分为代码区和数据区。在绝大多数的语言中，执行时不可能改变代码区，且 在概念上可将代码和数据区看作是独立的。另外由于代码区在执行之前是固定，所以在编译时 所有代码的地址都是可计算的，代码区可如下所示：
China-pub.com 第7章运行时环境 267 下载 过程1的入口点 过程的代码 过程2的入口点 过程2的代码 过程m的入口点 过程n的代码 代码存储器 特别地，在编译时还可以知道每个过程的入口点和函数⊙。对数据的分配不能这样说，它只有 小部分可在执行之前被分配到存储器中的固定位置。本章大部分内容都会谈论如何处理非固 定的或动态的数据分配。 在执行之前，可以将一类数据固定在存储器中，它还包括了程序的全局和/或静态数据 (FORTRAN77与绝大多数的语言不同，它所有的数据都属于这一类)。这些数据通常都在一个 固定区域内并以相似的风格单独分配给代码。在Pascal中，全局变量属于这一类，C的外部和 静态变量也是如此 在组织全局/静态区域中出现的一个问题是它涉及到编译时所知的常量。这其中包括了C和 Pascal的consti声明以及代码本身所用的文字值，例如串“Hel1。名d\i和在C语句 printf (Bello sd\n "12345 ) 中的整型值12345。诸如0和1这样较小的编译时常量通常由编译程序直接插入到代码中且不为 其分配任何数据空间。同样地，由于编译程序已掌握了全局函数或过程的入口点且可直接将其 插入到代码中，所以也不为它们分配全局数据区。然而我们却将大型的整型值、浮点值，特别 是串文字分配到全局静态区域中的存储器 在启动时仅保存一次，之后再由执行代码从这些 位置中得到（实际上，在C中串文字被看作是指针，因此它们必须按照这种方式来保存）。 用作动态数据分配的存储区可按多种方式组织。典型的组织是将这个存储器分为栈(stak) 区域和堆(heap)区域，栈区域用于其分配发生在后进先出LIFO(last--in,irst-out)风格中的数据 而堆区域则用于不符合LFO协议（例如在C中的指针分配）的动态分配©。目标机器的体系结构通 常包括处理器栈，利用了这个栈使得用处理器支持过程调用和返回（使用基于存储器分配的主要 机制)成为可能。有时，编译程序不得不将处理器栈的显式分配安排在存储器内的恰当位置中。 一种一般的运行时存储器组织如下所示，它具.有上术所有的程储娶分类： 代码区城 全程/静态区域 空间 日更为可能的情况是，代码由装载程序装载到存储器的一个在执行开始时分配的区域中，因此这是完全不可预 测的。但是之后的所有定际地址都由从固定的势载基地址的馆移自动计位组出，因出和固定地址的原理相同 有时，编译器的编写者必须留心生成可重定位代码(relocatable code,其中都相对于某个基址(base(通常是寄 存器)执行转移、调用以及引用。下一章将给出一些例子 读者应注意到堆通常是 个简单的线性存储器区域。将它称之为堆是一个历史原因，这与算法（如堆类排序） 中用到的堆数据结构无关
特别地，在编译时还可以知道每个过程的入口点和函数 。对数据的分配不能这样说，它只有 一小部分可在执行之前被分配到存储器中的固定位置。本章大部分内容都会谈论如何处理非固 定的或动态的数据分配。 在执行之前，可以将一类数据固定在存储器中，它还包括了程序的全局和 /或静态数据 ( F O RT R A N 7 7与绝大多数的语言不同，它所有的数据都属于这一类 )。这些数据通常都在一个 固定区域内并以相似的风格单独分配给代码。在 Pascal 中，全局变量属于这一类， C的外部和 静态变量也是如此。 在组织全局/静态区域中出现的一个问题是它涉及到编译时所知的常量。这其中包括了 C和 Pascal 的c o n s t声明以及代码本身所用的文字值，例如串“Hello %d\n”和在C语句 printf (" Hello %d\n ", 12345 ) ; 中的整型值1 2 3 4 5。诸如0和1这样较小的编译时常量通常由编译程序直接插入到代码中且不为 其分配任何数据空间。同样地，由于编译程序已掌握了全局函数或过程的入口点且可直接将其 插入到代码中，所以也不为它们分配全局数据区。然而我们却将大型的整型值、浮点值，特别 是串文字分配到全局 /静态区域中的存储器，在启动时仅保存一次，之后再由执行代码从这些 位置中得到(实际上，在C中串文字被看作是指针，因此它们必须按照这种方式来保存 )。 用作动态数据分配的存储区可按多种方式组织。典型的组织是将这个存储器分为栈 ( s t a c k ) 区域和堆( h e a p )区域，栈区域用于其分配发生在后进先出 LIFO(last-in, first-out)风格中的数据， 而堆区域则用于不符合L I F O协议(例如在C中的指针分配)的动态分配 。目标机器的体系结构通 常包括处理器栈，利用了这个栈使得用处理器支持过程调用和返回(使用基于存储器分配的主要 机制)成为可能。有时，编译程序不得不将处理器栈的显式分配安排在存储器内的恰当位置中。 一种一般的运行时存储器组织如下所示，它具有上述所有的存储器分类： 代码区域 全程 / 静态区域 栈 自由空间 堆 第 7章 运行时环境 2 6 7 下载 过程1的入口点 过程1的代码 过程2的代码 过程n的代码 代码存储器 过程2的入口点 过程n的入口点 更为可能的情况是，代码由装载程序装载到存储器的一个在执行开始时分配的区域中，因此这是完全不可预 测的。但是之后的所有实际地址都由从固定的装载基地址的偏移自动计算得出，因此和固定地址的原理相同。 有时，编译器的编写者必须留心生成可重定位代码 (relocatable code),其中都相对于某个基址( b a s e ) (通常是寄 存器)执行转移、调用以及引用。下一章将给出一些例子。 读者应注意到堆通常是一个简单的线性存储器区域。将它称之为堆是一个历史原因，这与算法 (如堆类排序) 中用到的堆数据结构无关。 ↓ ↑
268 翁译原理及实践 China-pub.com 下载 上图中的箭头表示栈和堆的生长方向。传统上是将栈画作在存储器中向下生长，这样它的 顶部实际就是在其所画区域的底部。堆也画得与栈相似，但它不是LFO结构且它的生长和缩 短比箭头所表示的还要复杂（参见7.4节）。在某些组织中，栈和堆被分配在不同的存储器部分， 而不是占据相同的区域。 存储器分配中的 一个重要单元是过程活动记录(procedure activation record),当调用或激活 过程或函数时，它包含了为其局部数据分配的存储器。活动记录至少应包括以下几个部分： 白变量《参数)空问 图鞋起合色的空它布T西 用作局部数据的空间 用作局部临时变量的空间 在这里应福调而日以后环要重复议个图示仅仅表示的是活动记最的一般组织。句括其所含影 据的顺序的特定细节则依赖于目标机器的体系结构、被编译的语言特性，甚至还有编译程序的 编写者的喜好。 所有过程活动记录的某些部分，例如用于簿记信息的空间，具有相同的大小。而其他部分 诸如用于自变量和局部数据的空间会对每一个过程保持固定，但是每个过程都各不相同。某些 活动记录还会由处理器自动分配到过程调用上（例如存储返回地址）。其他部分（如局部临时变量 空间)可能需要由编译程序生成的指令显式地分配。根据语言的不同，可能将活动记录分配在 静态区域(FORTRAN77)、栈区域(C、Pascal)、或堆区域(LISP)。当将活动记录保存在栈中时， 它们有时指的是栈框架(stack frame)。 处理器寄存器也是运行时环境的结构部分。寄存器可用来保存临时变量、局部变量甚至是 全局变量。当处理器具有多个寄存器时，正如在较新的RISC处理器中一样，整个静态区域和 整个活动记录都可完整地保存在寄存器中。处理器还具有特殊用途的寄存器以记录执行，如在 大多数的体系结构中的程序计数器(pc、栈指针(sp)(stack pointer)。可能还会为跟踪过程活动 而特别设计寄存器。这样的寄存器典型的有指向当前活动记录的框架指针（仰）((frame pointer), 以及指向保存自变量（参数值）的活动记录区域的自变量指针(argument pointer)e。 运行时环境的一个特别重要的部分是当调用过程或函数时，对必须发生的操作序列的判定 这样的操作可能还包括活动记录的存储器分配、计算和保存自变量以及为了使调用有效而进行 的必要的寄存器的保存和设置。这些操作通常指的是调用序列(calling sequence)。过程或函数 返回时需要的额外操作，如放置可由调用程序访问的返回值、寄存器的重新调整，以及活动记 录存储器的释放，也通常被认为是调用序列的一个部分。如果需要，可将调用时执行的调用序 列部分称作是调用序列(call sequence),而返回时执行的部分称为返回序列(return sequence)。 调用序列设计的重要方面有：1)如何在调用程序和被调用程序之间分开调用序列操作（也 就是有多少调用序列的代码放在调用点上，多少放在每个过程的代码开头)：2)在多大程度上 依赖处理器对调用支持而不是为调用序列的每一步生成显式代码。由于在调用点上比在被调用 ⊙这些名称都是从V八X体系结构中得到的，但是类似的名称还可出现在其他体系结构中
上图中的箭头表示栈和堆的生长方向。传统上是将栈画作在存储器中向下生长，这样它的 顶部实际就是在其所画区域的底部。堆也画得与栈相似，但它不是 L I F O结构且它的生长和缩 短比箭头所表示的还要复杂 (参见7 . 4节)。在某些组织中，栈和堆被分配在不同的存储器部分， 而不是占据相同的区域。 存储器分配中的一个重要单元是过程活动记录(procedure activation record)，当调用或激活 过程或函数时，它包含了为其局部数据分配的存储器。活动记录至少应包括以下几个部分： 在这里应强调(而且以后还要重复)这个图示仅仅表示的是活动记录的一般组织。包括其所含数 据的顺序的特定细节则依赖于目标机器的体系结构、被编译的语言特性，甚至还有编译程序的 编写者的喜好。 所有过程活动记录的某些部分，例如用于簿记信息的空间，具有相同的大小。而其他部分， 诸如用于自变量和局部数据的空间会对每一个过程保持固定，但是每个过程都各不相同。某些 活动记录还会由处理器自动分配到过程调用上 (例如存储返回地址)。其他部分(如局部临时变量 空间)可能需要由编译程序生成的指令显式地分配。根据语言的不同，可能将活动记录分配在 静态区域( F O RT R A N 7 7 )、栈区域( C、P a s c a l )、或堆区域( L I S P )。当将活动记录保存在栈中时， 它们有时指的是栈框架(stack frame)。 处理器寄存器也是运行时环境的结构部分。寄存器可用来保存临时变量、局部变量甚至是 全局变量。当处理器具有多个寄存器时，正如在较新的 R I S C处理器中一样，整个静态区域和 整个活动记录都可完整地保存在寄存器中。处理器还具有特殊用途的寄存器以记录执行，如在 大多数的体系结构中的程序计数器 ( p c )、栈指针(sp)(stack pointer)。可能还会为跟踪过程活动 而特别设计寄存器。这样的寄存器典型的有指向当前活动记录的框架指针 (fp)(frame pointer)， 以及指向保存自变量(参数值)的活动记录区域的自变量指针( a rgument pointer) 。 运行时环境的一个特别重要的部分是当调用过程或函数时，对必须发生的操作序列的判定。 这样的操作可能还包括活动记录的存储器分配、计算和保存自变量以及为了使调用有效而进行 的必要的寄存器的保存和设置。这些操作通常指的是调用序列 (calling sequence)。过程或函数 返回时需要的额外操作，如放置可由调用程序访问的返回值、寄存器的重新调整，以及活动记 录存储器的释放，也通常被认为是调用序列的一个部分。如果需要，可将调用时执行的调用序 列部分称作是调用序列(call sequence)，而返回时执行的部分称为返回序列(return sequence)。 调用序列设计的重要方面有： 1) 如何在调用程序和被调用程序之间分开调用序列操作 (也 就是有多少调用序列的代码放在调用点上，多少放在每个过程的代码开头 )；2 )在多大程度上 依赖处理器对调用支持而不是为调用序列的每一步生成显式代码。由于在调用点上比在被调用 2 6 8 编译原理及实践 下载 自变量（参数）空间 用作薄记信息的空间，它包括了返 回地址 用作局部数据的空间 用作局部临时变量的空间 这些名称都是从VA X体系结构中得到的，但是类似的名称还可出现在其他体系结构中
China-pub.Com 269 下载 第7章运行时环境 程序内更易生成调用序列代码，但是这样做会引起生成代码数量的生长，因为在每个调用点都 要复制相同的代码所以第1点是一个很棘手的问题，后面还要再更详细地讲到这些问题。 调用程序至少要负责计算自变量并将它们放在可由被调用程序找到的位置上（可能是直接 放在被调用程序的活动记录中)。此外，调用程序或被调用程序或两者必须保存调用点上的机 器状态，包括返回地址，可能还有正使用的寄存器。最后，在调用程序和被调用程序之间须用 某个可能的合作方式建立所有附加的簿记信息。 7.2完全静态运行时环境 最简单的运行时环境类型是所有数据都是静态的，且执行程序期间在存储器中保持固定。 这样的环境可用来实现没有指针或动态分配，且过程不可递归调用的语音。此类语言的标准倒 子是FORTRAN77。 在完全静态环境中，不仅全局变量，所有的变量都是静态分配。因此，每个过程只有一个 在执行之前被静态分配的活动记录。我们都可通过固定的地址直接访问所有的变量，而不论它 们是局部的还是全局的，则整个程序存储器如下所示： 主过程的代码 过程1的代码 代绿 过程n的代码 会品数摇风城 主过程的活动记录 过程1的活动记录 过程m的话动记录 在这样的环境中，保留每个活动记录的簿记信息开销相对较小，而且也不需要在活动记录中 保存有关环境的额外信息（而不是返回地址）。用于这样环境的调用序列也十分简单。当调用 一个过程时，就计算每个自变量，并将其保存到被调用过程的活动中恰当的参数位置。接着 保存调用程序代码中的返回地址，并转移到被调用的过程的代码开头。返回时，转移到返回 地址©。 例7.1作为这种环境的具体示例，考虑程序清单7-1中的FORTRAN77程序。这个程序有一个 主过程和一个附加的过程QUADMEAN。在主过程和QUADMEAN中有由COMMON MAXSIZE声明 当执行返回指令时，也自动地再装载这个地址 我们忽略库函数SQRT ,它由QUADMEANI调用而且在执行之前先被链接
程序内更易生成调用序列代码，但是这样做会引起生成代码数量的生长，因为在每个调用点都 要复制相同的代码所以第1点是一个很棘手的问题，后面还要再更详细地讲到这些问题。 调用程序至少要负责计算自变量并将它们放在可由被调用程序找到的位置上 (可能是直接 放在被调用程序的活动记录中 )。此外，调用程序或被调用程序或两者必须保存调用点上的机 器状态，包括返回地址，可能还有正使用的寄存器。最后，在调用程序和被调用程序之间须用 某个可能的合作方式建立所有附加的簿记信息。 7.2 完全静态运行时环境 最简单的运行时环境类型是所有数据都是静态的，且执行程序期间在存储器中保持固定。 这样的环境可用来实现没有指针或动态分配，且过程不可递归调用的语言。此类语言的标准例 子是F O RT R A N 7 7。 在完全静态环境中，不仅全局变量，所有的变量都是静态分配。因此，每个过程只有一个 在执行之前被静态分配的活动记录。我们都可通过固定的地址直接访问所有的变量，而不论它 们是局部的还是全局的，则整个程序存储器如下所示： 在这样的环境中，保留每个活动记录的簿记信息开销相对较小，而且也不需要在活动记录中 保存有关环境的额外信息 (而不是返回地址 )。用于这样环境的调用序列也十分简单。当调用 一个过程时，就计算每个自变量，并将其保存到被调用过程的活动中恰当的参数位置。接着 保存调用程序代码中的返回地址，并转移到被调用的过程的代码开头。返回时，转移到返回 地址 。 例7.1 作为这种环境的具体示例，考虑程序清单 7 - 1中的F O RT R A N 7 7程序。这个程序有一个 主过程和一个附加的过程Q U A D M E A N 。在主过程和Q U A D M E A N中有由COMMON MAXSIZE声明 第 7章 运行时环境 2 6 9 下载 在大多数的体系结构中，子例程转移自动地保存返回地址；当执行返回指令时，也自动地再装载这个地址。 我们忽略库函数S Q RT，它由Q U A D M E A N调用而且在执行之前先被链接。 代码 区域 主过程的代码 过程1的代码 过程n 的代码 全局数据区域 数据 区域 主过程的活动记录 过程n 的活动记录 过程1的活动记录
270 翁译原理及实践 China-pub.C 下载 给出的全局变量⊙。 程序清单7-1一个FORTRAN77示例程序 D日02BMp里gT COMMON MAXS:工ZE ).TEMP RRAD TABLE(1),TABLE(2),TABLE(3) (TABLE,3,TEMP) DHEAN (A,SIZE,QHEAN) REAL A(S江ZE),QE,TP IF ((SIZE.GT.MAXSIZE).OR.(SIZE.L.1))GOTO 99 D010K·1,8江z TEMP A(K)"A(K) 39() RETURN END 忽略存储器中整型值和浮点值间可能有的大 小区别，我们显示了图7-1中的这个程序的运 全局区 MAXSIZE 行时环境⑨。在该图中，我们用箭头表示从 TABLE 主过程中调用时，过程QUADMEAN的参数A (10) SIZE和OMEAN的值。在FORTRAN77中，参 数值是隐含的存储引用，所以调用(TAB工E、 TEMP 3和TEMP)的参数地址就被复制到 3 QUADMEAN的参数地址中。它有几个后果。 A 首先，需要一个额外的复引用来访问参数 812班 值。其次，数组参数无需再重新设置和复 OMEAN 制（因此，只给在QUADMEAN中的数组参数 A分配一个空间，在调用时指出TABLE的基 的活动记录 返国地址 地址)。再次，像在调用中的值3的常量参数 四P 必须被放在一个存储器地址中而日在调用 时要使用这个地址(7.5节将更完整地讨论参 数传递机制)。 图71中还有一个特性需要解释一下，这 图7-！程序清单7-1中程序的运行时环境 日实际上，FORTRAN77允许COMMON变量在不同的过程中具有不同的名称，而仍旧指的是相同存储器位置。 从这个示例开始，我们将默认忽略这种复杂性」 ©我们再次强调这个图示仅仅是示意性的。在操作中的实现实际与这里给出的有所差异
给出的全局变量 。 程序清单7-1 一个F O RT R A N 7 7示例程序 忽略存储器中整型值和浮点值间可能有的大 小区别，我们显示了图 7 - 1中的这个程序的运 行时环境 。在该图中，我们用箭头表示从 主过程中调用时，过程 Q U A D M E A N的参数A、 S I Z E和Q M E A N的值。在F O RT R A N 7 7中，参 数值是隐含的存储引用，所以调用 (T A B L E、 3 和 T E M P ) 的 参 数 地 址 就 被 复 制 到 Q U A D M E A N的参数地址中。它有几个后果。 首先，需要一个额外的复引用来访问参数 值。其次，数组参数无需再重新设置和复 制(因此，只给在 Q U A D M E A N中的数组参数 A分配一个空间，在调用时指出 T A B L E的基 地址)。再次，像在调用中的值 3的常量参数 必须被放在一个存储器地址中而且在调用 时要使用这个地址 ( 7 . 5节将更完整地讨论参 数传递机制 )。 图7 - 1中还有一个特性需要解释一下，这 2 7 0 编译原理及实践 下载 实际上，F O RT R A N 7 7允许C O M M O N变量在不同的过程中具有不同的名称，而仍旧指的是相同存储器位置。 从这个示例开始，我们将默认忽略这种复杂性。 我们再次强调这个图示仅仅是示意性的。在操作中的实现实际与这里给出的有所差异。 全局区 主过程的 活动记录 过程Q U A D M E A N 的活动记录 QMEAN 返回地址 图7-1 程序清单7 - 1中程序的运行时环境
China-pub.Com 第7章运行时环境 271 下载 就是QUADMEAN的活动记录结尾分配的未命名的地址。这个地址是一个在算术表达式计算中用 来储存临时变量值的“凑合的”地址。在QUADMEAN中可能需要两个运算。一个是循环中的 TEMP+A(K)A(K)的计算，另一个是当参数在调用SQRT时的TEMP/SIzE的计算。我们早己 谈过需要为参数值分配空间（尽管在对库函数的调用中实际上是有差别的）。循环计算中也需要 临时变量存储地址的原因在于每个算术运算必须在一个步骤中，所以就计算A(K)*A(K)并在 下一步中添加EMP的值。如果没有足够的寄存器来放置这个临时变量值，或如果有一个调用 要求保存这个值，那么在完成计算之前应先将值存储在活动记录中。编译程序可以总是先预测 出在执行中它是否必要，然后再为分配临时变量的地址的恰当数量（以及大小）作出安排。 7.3基于栈的运行时环境 在允许递归调用以及每一个调用中都重新分配局部变量的语言中，不能静态地分配活动记 录。相反地，必须以一个基于栈的风格来分配活动记录，即当进行一个新的过程调用（活动记 录的压入(pus)时，每个新的活动记录都分配在栈的顶部，而当调用退出时则再次解除分配 (活动记录的弹出(pop)。活动记录的栈(stack of activation record)(也指运行时栈(runtime stack) 或调用栈(call stack)就随着程序执行时发生的调用链生长或缩小。每个过程每次在调用栈上可 以有若干个不同的话动记录，每个都代表了一个不同的调用。这样的环境要求的簿记和变量访 问的技术比完全静态环境要复杂许多。特别地，活动记录中必须有额外的簿记信息，而且调用 序列还包括设置和保存这个额外信息所需的步骤。基于栈的环境的正确性和所需簿记信息的数 量在很大程度上依赖于被编译的语言的特性。在本节中为了提高难度复杂性，我们将考虑基于 栈的环境的组织，它是由所涉及到的语言特性区分的。 7.3.1没有局部过程的基于栈的环境 在一个所有过程都是全局的语言（例如C语言）中，基于栈的环境有两个要求：指向当前活 动记录的指针的维护允许访问局部变量，以及位置记录或紧前面的活动记录（调用程序的活动 记录)允许在当前调用结束时读有活动记录（日金掉当前活动）。指向当前活动的指针通常称为 框架指针(ame pointer)或(p,且通常保存在寄存器中（通常也称作p)。作为一个指向先前 动记录的指针，有关先前活动的信息一般是放在当前活动中，并被认为是控制链(control link) 或动态链(dynamic link)(之所以称之为动态的，是因为在执行时它指向调用程序的活动记录)。 有时将这个指针称为旧p(old fp),这是因为它代表了p的先前值。通常，这个指针被放在栈 中参数区域和局部变量区域之间的某处，并且指向先前活动记录控制链。此外，还有一个栈 指针((stack pointer)或sp,它通常指向调用栈上的最后位置（它有时称作栈顶部((top of stack)指针， 或tos)。 现在考虑几个例子。 例7.2利用Euclid3算法的简单递归实现，计算两个非负整数的最大公约数，它的代码(C语言) 在程序清单7-2中。 程序清单7-2例7-2的C代码 sinclude int x,y:
就是Q U A D M E A N的活动记录结尾分配的未命名的地址。这个地址是一个在算术表达式计算中用 来储存临时变量值的“凑合的”地址。在 Q U A D M E A N中可能需要两个运算。一个是循环中的 T E M P + A ( K ) * A ( K )的计算，另一个是当参数在调用 S Q R T时的T E M P / S I Z E的计算。我们早已 谈过需要为参数值分配空间 (尽管在对库函数的调用中实际上是有差别的 )。循环计算中也需要 临时变量存储地址的原因在于每个算术运算必须在一个步骤中，所以就计算 A ( K ) * A ( K )并在 下一步中添加T E M P的值。如果没有足够的寄存器来放置这个临时变量值，或如果有一个调用 要求保存这个值，那么在完成计算之前应先将值存储在活动记录中。编译程序可以总是先预测 出在执行中它是否必要，然后再为分配临时变量的地址的恰当数量 (以及大小)作出安排。 7.3 基于栈的运行时环境 在允许递归调用以及每一个调用中都重新分配局部变量的语言中，不能静态地分配活动记 录。相反地，必须以一个基于栈的风格来分配活动记录，即当进行一个新的过程调用 (活动记 录的压入( p u s h ) )时，每个新的活动记录都分配在栈的顶部，而当调用退出时则再次解除分配 (活动记录的弹出( p o p ) )。活动记录的栈(stack of activation record)(也指运行时栈(runtime stack) 或调用栈(call stack))就随着程序执行时发生的调用链生长或缩小。每个过程每次在调用栈上可 以有若干个不同的活动记录，每个都代表了一个不同的调用。这样的环境要求的簿记和变量访 问的技术比完全静态环境要复杂许多。特别地，活动记录中必须有额外的簿记信息，而且调用 序列还包括设置和保存这个额外信息所需的步骤。基于栈的环境的正确性和所需簿记信息的数 量在很大程度上依赖于被编译的语言的特性。在本节中为了提高难度复杂性，我们将考虑基于 栈的环境的组织，它是由所涉及到的语言特性区分的。 7.3.1 没有局部过程的基于栈的环境 在一个所有过程都是全局的语言 (例如C语言)中，基于栈的环境有两个要求：指向当前活 动记录的指针的维护允许访问局部变量，以及位置记录或紧前面的活动记录 (调用程序的活动 记录)允许在当前调用结束时恢复活动记录 (且舍掉当前活动 )。指向当前活动的指针通常称为 框架指针(frame pointer) 或( f p )，且通常保存在寄存器中(通常也称作f p )。作为一个指向先前活 动记录的指针，有关先前活动的信息一般是放在当前活动中，并被认为是控制链 (control link) 或动态链(dynamic link) (之所以称之为动态的，是因为在执行时它指向调用程序的活动记录 )。 有时将这个指针称为旧 f p (old fp)，这是因为它代表了 f p的先前值。通常，这个指针被放在栈 中参数区域和局部变量区域之间的某处，并且指向先前活动记录控制链。此外，还有一个栈 指针(stack pointer)或s p，它通常指向调用栈上的最后位置(它有时称作栈顶部(top of stack)指针， 或t o s )。 现在考虑几个例子。 例7.2 利用E u c l i d算法的简单递归实现，计算两个非负整数的最大公约数，它的代码 ( C语言) 在程序清单7 - 2中。 程序清单7-2 例7 - 2的C代码 第 7章 运行时环境 2 7 1 下载
272 翁译原理及实践 China-pub.com 下载 int ged(int u,int v) main() return 0: 假设用户在该程序中输入了值15和10，那么main就初始化调用gcd(15,10)。这个调用 导致了另一个递归调用gcd(10,5),(因为15%10=5)，而这又引起了第3个调用 gcd(5,0)(因为10%5=0， 它将返回值5。在第 3个调用中，运行时环境如图7-2所示。请读者 8 全局/静态区城 注意指向每个调用的gc是如何向栈的顶部添 加新的大小完全相同的活动记录，并且在每 min的话动记录 新活动记录中，控制链指向先前活动记录的控 制链。还请大家注意，指向当前活动记录的 控制链，因此在下一个调用中当前的印就会变 成下一个活动记录的控制链了。 调用最后 个gcd的之后，将按顺序从栈中 控制链 鲜济用 别去每个活动，这样当在main中执行printf 返回地址 语句时，只在环境中保留了main和全局/静态区 域的活动记录（我们已将main的记录显示为空 在实际中，它应包含将控制传回到操作系统的 返因地计 信息)。 最后，应指出在调用gcd时调用程序不 钱生长方向 需要为自变量值安排空间（与图71中的 FORTRAN7?7环境中的常量3不同)，这是因为C 图7-2例7.2的基于栈的环境 语言使用值参数。7.5节将详细探讨这一点。 例7.3考虑程序清单7-3中的C代码。这个代码包括将用来进一步描述本节相关内容的变量， 但是它的基本操作如下所示。从main来的第1个调用是到g(2)的（这是因为x在这一点上有值 2)。在这个调用中，m变成了2，而y则变成了1。接着g调用￡(1)，而￡也相应地调用g(1)。 在这个到g的调用中，m变成了1，而y则变成了0，所以再也没有别的调用了。该点（在对g的第 二次调用期间)上的运行时环境显示在图7-3a中。 程序清单7-3例7.3的C程序 int x=21 void g(int):/*prototype *
假设用户在该程序中输入了值 1 5和1 0，那么m a i n就初始化调用g c d ( 1 5 , 1 0 )。这个调用 导致了另一个递归调用 g c d ( 1 0 , 5 )，(因为 15 % 10 = 5) ，而这又引起了第 3个调用 g c d ( 5 , 0 )(因为1 0 % 5 = 0 )，它将返回值5。在第 3个调用中，运行时环境如图 7 - 2所示。请读者 注意指向每个调用的 g c d是如何向栈的顶部添 加新的大小完全相同的活动记录，并且在每个 新活动记录中，控制链指向先前活动记录的控 制链。还请大家注意， f p指向当前活动记录的 控制链，因此在下一个调用中当前的 f p就会变 成下一个活动记录的控制链了。 调用最后一个g c d的之后，将按顺序从栈中 删去每个活动，这样当在 m a i n中执行p r i n t f 语句时，只在环境中保留了m a i n和全局/静态区 域的活动记录(我们已将m a i n的记录显示为空。 在实际中，它应包含将控制传回到操作系统的 信息)。 最后，应指出在调用 g c d 时调用程序不 需 要为自变量值安排空间（与图 7 - 1 中的 F O RT R A N 7 7环境中的常量3不同），这是因为C 语言使用值参数。7 . 5节将详细探讨这一点。 例7.3 考虑程序清单7 - 3中的C代码。这个代码包括将用来进一步描述本节相关内容的变量， 但是它的基本操作如下所示。从 m a i n来的第1个调用是到g ( 2 )的(这是因为x在这一点上有值 2 )。在这个调用中， m变成了2，而y则变成了1。接着g调用f ( 1 )，而f也相应地调用 g ( 1 )。 在这个到g的调用中，m变成了1，而y则变成了0，所以再也没有别的调用了。该点 (在对g的第 二次调用期间)上的运行时环境显示在图7-3a 中。 程序清单7-3 例7 . 3的C程序 2 7 2 编译原理及实践 下载 图7-2 例7 . 2的基于栈的环境 控制链 返回地址 栈生长方向 全局／静态区域 main 的活动记录 第一次调用 g c d 时的活动记录 第二次调用 g c d 时的活动记录 第三次调用 g c d 时的活动记录 控制链 返回地址 控制链 返回地址 自由空间
China-pub.com 第7章运行时环境 273 下载 g(n) void g(int m) gly): main() 【g(x), return 0; 现在对g和￡的调用退出(E在返回之前它的静态局部变量x减)，它们的活动记录从栈中弹 出，且控制返回到紧随在第1次对g的调用的E的调用之后的点。现在g给外部变量x减1，并进 行另一次调用g(1),将m设为2将y设为1，这样就得到了图7-3b中的运行时环境。在此之后再 也没有调用了，从栈中就会弹出剩余的活动记录，程序退出。 (from)1 全局/静态区 受在om:0 全局/静态区 main的话动记录 main的话动记录 m:2 调用g时的活动 调用g时的活动 记录 返回地址 记录 y:1 y:1 n:1 m:1 调用！时的活动 控制 记录 返国地址 返地址 动 y:0 m:1 用g时的活动 y:0 记录 自由 图7-3程序清单73中程序的运行时环境 )在第2次对g的调用时，程序清单73中程序的运行时环境 b)在第3次对g的调用时，程序清单一3中程序的运行时环境 请注意，在图7-3中，对g的第3次调用的活动记录占据着（并覆盖）E的活动记录先前占着 的存储器区域。大家还应注意到：由于￡中的静态变量x必须坚持通过所有对E的调用，所以不 可在的活动记录中分配。因此，尽管不是全局变量，也必须在全局静态区域中与外部变量x
现在对g和f的调用退出(f在返回之前它的静态局部变量 x减1 )，它们的活动记录从栈中弹 出，且控制返回到紧随在第 1次对g的调用的f的调用之后的点。现在 g给外部变量x减1，并进 行另一次调用g ( 1 )，将m设为2将y设为1，这样就得到了图7-3b 中的运行时环境。在此之后再 也没有调用了，从栈中就会弹出剩余的活动记录，程序退出。 图7-3 程序清单7 - 3中程序的运行时环境 a) 在第2次对g 的调用时，程序清单7 - 3中程序的运行时环境 b) 在第3次对g 的调用时，程序清单7 - 3中程序的运行时环境 请注意，在图7-3b 中，对g的第3次调用的活动记录占据着 (并覆盖)f的活动记录先前占着 的存储器区域。大家还应注意到：由于 f中的静态变量x必须坚持通过所有对f的调用，所以不 可在f的活动记录中分配。因此，尽管不是全局变量，也必须在全局 /静态区域中与外部变量 x 第 7章 运行时环境 2 7 3 下载 控制链 返回地址 全局／静态区 main 的活动记录 调用 g 时的活动 记录 全局／静态区 main 的活动记录 调用 g 时的活动 记录 调用 g 时的活动 记录 调用 f 时的活动 记录 调用 g时的活动 记录 控制链 返回地址 控制链 返回地址 控制链 返回地址 控制链 返回地址 y:0 自由空间 自由空间 a) b)
274翁济原理及实践 China-pub.com 下载 在一起分配。因为符号表会总能区分它与外部的x,并在程序每一个点上判定访问的正确变量， 所以它们不会有什么混淆。 活动树(activation tree)是分析程序中复杂调用 main() main() 结构的有用工具，每个活动记录（或调用）都成为该 树的一个节点，而每个节点的子孙则代表了与该节 gcd(15,10) 点相对应的调用时进行的调用。例如，程序清单7 gcd(10,5) 2中程序的活动树是线性的，在图7-4a中描述（对 goa(5,01 g(2) 于输入15和10而言)，而程序清单7-3中程序的活动 树在图7-4b中描述。请注意，图7-2和图7-3中显 a b 示的环境表示了在调用时由活动树的每个叶子代表 的调用。一般而言，在特定调用开头的活动记录栈 图7-4程序清单7-2和程序清单7-3中 与活动树的相应节点到根节点的通路有一个结构等 程序的活动树 价。 )对名称的访问在基于栈的环境中，再也不能像在完全静态环境中那样用固定的地址访 问参数和局部变量。而它们由当前框架指针的偏移量发现。在大多数的语言中，每个局部声明 的偏移量仍是可由编译程序静态地计算出来，因为过程的声明在编译时是固定的，而且为每个 声明分配的存储器大小也根据其数据类型而固定。 考虑程序清单7-3中C程序的过程g(参见图7-3中画出的运行时环境)。g的每个活动记录 的格式完全相同，而参数m和局部变量y也总是位于活动记录中完全相同的相对位置。我们 把这个距离称作moE￡set和yoffset。然后，在对g的任何调用期间，都有下面的局部环 境图： 控制鞋 mOffset. Ep 返回地址 y m和y都可根据它们从的固定偏移进行访问。例如，具体地假设运行时栈从存储器地址的 高端向低端生长，整型变量的存储要求两个字节，地址要求4个字节。若活动记录的组织如上 所画，就有moffset=+4和yoffset=-6,且对m和y的引用写成机器代码（假设是标准的汇 编器约定)为4(Ep)和-6(EP)。 局部数组和结构与简单变量相比分配和计算地址并不更加困难，如以下示例所示。 例7.4考虑C过程 double yi 对￡调用的活动记录显示为：
在一起分配。因为符号表会总能区分它与外部的 x，并在程序每一个点上判定访问的正确变量， 所以它们不会有什么混淆。 活动树(activation tree) 是分析程序中复杂调用 结构的有用工具，每个活动记录 (或调用)都成为该 树的一个节点，而每个节点的子孙则代表了与该节 点相对应的调用时进行的调用。例如，程序清单 7 - 2中程序的活动树是线性的，在图 7-4a 中描述(对 于输入1 5和1 0而言)，而程序清单7 - 3中程序的活动 树在图7-4b 中描述。请注意，图 7 - 2和图7 - 3中显 示的环境表示了在调用时由活动树的每个叶子代表 的调用。一般而言，在特定调用开头的活动记录栈 与活动树的相应节点到根节点的通路有一个结构等 价。 1) 对名称的访问 在基于栈的环境中，再也不能像在完全静态环境中那样用固定的地址访 问参数和局部变量。而它们由当前框架指针的偏移量发现。在大多数的语言中，每个局部声明 的偏移量仍是可由编译程序静态地计算出来，因为过程的声明在编译时是固定的，而且为每个 声明分配的存储器大小也根据其数据类型而固定。 考虑程序清单 7 - 3中C程序的过程 g (参见图7 - 3中画出的运行时环境 )。g的每个活动记录 的格式完全相同，而参数 m和局部变量 y也总是位于活动记录中完全相同的相对位置。我们 把这个距离称作 m O f f s e t和y O f f s e t。然后，在对 g的任何调用期间，都有下面的局部环 境图： m和y都可根据它们从f p的固定偏移进行访问。例如，具体地假设运行时栈从存储器地址的 高端向低端生长，整型变量的存储要求两个字节，地址要求 4个字节。若活动记录的组织如上 所画，就有m O f f s e t = +4和y O f f s e t = -6，且对m和y的引用写成机器代码(假设是标准的汇 编器约定)为4 ( f p )和- 6 ( f p )。 局部数组和结构与简单变量相比分配和计算地址并不更加困难，如以下示例所示。 例7.4 考虑C过程 void f(int x, char c) { int a[10]; double y; . . . } 对f调用的活动记录显示为： 2 7 4 编译原理及实践 下载 图7-4 程序清单7 - 2和程序清单7 - 3中 程序的活动树 m y 控制链 返回地址 a) b)
China-pub.com 第7章运行时环境 275 下载 T偏移量 偏移量 控制链 返同地址 a[9] 偏移 a11 a[o] y 而且假设整型是两个字节、地址4个字节、字符1个字节、双精度浮点数8个字节，那么就 有以下的偏移值（再次假设栈的生成为负方向），这些值在编译时都是可计算的： 名称 偏移量 X U +《 -32 现在对a【1】一个访问将要求计算地址 （-24+2*i)(Ep) (这里在产生式2*i中的因子是比例因子(scale factor),它是从假设整型值占有两个字节得来的)： 这样的存储器访问依赖于1的地址以及体系结构，可能只需要一条指令。 对于这个环境中的非局部的和静态名字而言，不能用同局部名字一样的方法访问它们。实 际上，我们此处所考虑的情况一一不带有过程的语言一一所有的非局部的名字都是全局的，因 此也就是静态的。所以在图73中，外部的（全局的）C变量x具有一个固定的静态地址，因此也 就可以被直接访问（或是通过某个基指针的偏移而不是p)。对来自￡的静态局部变量x的访问也 使用完全相同的风格。请注意，正如前一章所描述的，这个机制实现静态（或词法的）作用域。 如果需要动态作用域，那么就要使用一个更为复杂的访问机制（本节后面将要提到）。 2)调用序列谓用序列大致由以下的步骤组成©。当周用一个讨时程时， ①计算自变量并将其存放在过程的新活动记录中的正确位置（将其妥当地压入到运行时栈 中就可做到这一点)。 ②将印作为控制链存放（压入）到新的活动记录中 ③改变p以使其指向新的活动记录的开始（如已有了一个s即，则将该s即复制到该点上的p中， 也可以做到这一点)。 日这个描述忽略了必须发生的奇存晷的任何保存。它还忽略了将返回值放在一个可用的地址的需要
而且假设整型是两个字节、地址 4个字节、字符1个字节、双精度浮点数 8个字节，那么就 有以下的偏移值(再次假设栈的生成为负方向)，这些值在编译时都是可计算的： 名 称 偏 移 量 X + 5 C + 4 A -2 4 Y -3 2 现在对a [ i ]一个访问将要求计算地址 ( - 2 4 + 2 * i ) ( f p ) (这里在产生式2 * i中的因子是比例因子(scale factor)，它是从假设整型值占有两个字节得来的)。 这样的存储器访问依赖于i的地址以及体系结构，可能只需要一条指令。 对于这个环境中的非局部的和静态名字而言，不能用同局部名字一样的方法访问它们。实 际上，我们此处所考虑的情况——不带有过程的语言——所有的非局部的名字都是全局的，因 此也就是静态的。所以在图 7 - 3中，外部的(全局的) C变量x具有一个固定的静态地址，因此也 就可以被直接访问(或是通过某个基指针的偏移而不是 f p )。对来自f的静态局部变量x的访问也 使用完全相同的风格。请注意，正如前一章所描述的，这个机制实现静态 (或词法的)作用域。 如果需要动态作用域，那么就要使用一个更为复杂的访问机制 (本节后面将要提到)。 2) 调用序列 调用序列大致由以下的步骤组成 。当调用一个过程时， ① 计算自变量并将其存放在过程的新活动记录中的正确位置 (将其妥当地压入到运行时栈 中就可做到这一点)。 ② 将f p作为控制链存放(压入)到新的活动记录中。 ③ 改变f p以使其指向新的活动记录的开始(如已有了一个s p，则将该s p复制到该点上的f p中， 也可以做到这一点)。 第 7章 运行时环境 2 7 5 下载 控制链 返回地址 x 偏移量 c 偏移量 a 偏移量 y 偏移量 这个描述忽略了必须发生的寄存器的任何保存。它还忽略了将返回值放在一个可用的地址的需要