8hh第6章运行时存储空间组织

第6章运行时存储空间组织前面讨论了对源程序进行静态分析的编译程序的不同阶段,这些分析仅取决于源程序本身的特性,与目标机及目标机的操作系统特性无关。但编译程序的最终目的是把源程序翻译成能在目标机上运行的目标程序,这就要求编译程序不仅能生成目标代码,还要在生成目标代码之前进行目标程序运行环境的设计和数据空间的分配。例如,目标程序运行时,源程序中各种变量、常量等如何在存储器中存放?如何对它们进行访问?源程序中各种变量、常量的作用域和生存期如何确定?递归过程的数据空间如何在运行过程中实现动态的分配?这些问题对于编译程序是非常复杂又十分重要的。分配目标程序数据空间的基本策略:1.静态分配策略若一个程序语言不允许有递归过程,不允许含可变体积的数据项或待定性质的名字,则在编译时能完全确定其程序的每个数据项目的存储空间位置,这种策略叫静态分配策略。例如,FORTRAN语言2.栈式动态分配策略若程序语言允许有递归过程和可变数组,则程序数据空间的分配需采用动态策略,即在程序运行时进行数据空间的分配,此时目标程序可用栈作为动态的数据空间。程序运行时,每当进入一个子程序,其所需的数据空间就动态地分配于栈顶,一旦该子程序运行结束,其所占用的空间就释放,这种方法叫栈式动态分配策略。3.堆式动态分配策略若程序语言允许用户动态地申请和释放存储空间,并且申请和释放之间不一定遵守“先申请后释放”的原则,则必须让运行程序拥有一个大存储区(堆),申请时从堆中分配一块,释放时退还给堆,这种方法叫堆式动态分配策略。6.1静态存储分配6.2简单的栈式存储分配6.3嵌套过程语言的栈式实现6.4堆式动态存储分配6.5参数传递补遗6.1静态存储分配若编译时能确定程序运行时所需存储空间的大小,则编译时能安排好程序运行时的全部数据空间,并能确定每个数据项的地址,这种存储分配方法叫做静态分配。FORTRAN语言不允许有递归过程,每个数据名所需存储空间的大小是常量(即不允许含可变体积的数据),且所有数据名的性质是完全确定的(不允许出现动态确定其性质的数据名)。故FORTRAN程序可静态分配存储空间。(1)数组的上下界必须是常数;(2)过程调用不允许递归;(3)不允许采用动态数据结构,即程序运行过程中不允许申请和释放存储空间。适于静态存储分配的语言需满足的条件:满足条件的语言有FORTRAN,BASIC等。这些语言的编译程序可完全确定程序中数据项所在地址(通常为相应于各数据区起始地址的位移量)。由于过程调用不允许递归,因此数据项的存储地址与过程相联系。过程调用所使用的局部数据区直接安排在过程的目标代码后,并把各数据项的存储地址填入相关的目标代码,以便在过程运行时访问这个局部数据区。采用静态存储分配时,不存在对存储区的再利用问题,目标程序执行时不必进行运行时存储空间管理,因此,过程进入和退出很简单。FORTRAN语言的静态存储管理特点使FORTRAN程序中各程序段可独立地进行编译。在编译过程中,给程序中变量或数组分配存储单元的一般方法为:为每个变量(或数组)确定一个有序整数对,并把这一对整数填入符号表相应登记项的信息栏中。其中第一个整数指示数据区的编号,第二个整数指明该变量(或数组)所对应的存储起始单元相应于其所在数据区起点的位移。各数据区的起始地址在编译时暂不确定,待各程序段全部编译完后,再由连接装配程序最终确定,并将各程序段的目标代码组装成一个完整的目标程序。FORTRAN程序段的局部数据区可由图6-1所示的项目组成:临时变量数组简单变量形式单元寄存器保护区隐参数返回地址图6-1一个FORTRAN程序段的局部数据区隐参数指过程调用时的连接信息,如返回地址、寄存器保护区等;形式单元用来存放过程调用时与形参对应的实参地址或值。首先考虑一种简单程序语言:没有分程序结构,过程定义不允许嵌套,但允许过程的递归调用,允许过程含可变数组。C语言除了不允许含可变数组外,就是这样一种语言。6.2简单的栈式存储分配C语言的程序结构如下:全局数据说明main( ){main中的数据说明}voidR( ){R中的数据说明}voidQ(){Q中的数据说明}计算n!的C程序的执行过程可用栈实现:#include“stdio.h”longfactorial(intn){if(n1)return(n*factorial(n-1));elsereturn(1);}main( ){intnum;do{scanf(“%d”,&num);if(num=0&&num15)printf(“%d\n”,factorial(num));elseprintf(“error!\n”);}while(num=0);}6.2.1栈式存储分配与活动记录使用栈式存储分配法意味着程序运行时,每当进入一个过程(或函数)就有一个相应的活动记录累筑于栈顶,此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。在执行可执行语句之前,把局部数组所需空间累筑于栈顶,从而形成过程工作时的完整数据区。注意:(1)每个过程的活动记录的体积在编译时可以静态地确定。(2)由于允许含有可变数组,故数组的大小在运行时才能知道。(3)由于可变数组的大小不能预先获知,为了扩充方便,把数组区累筑于活动记录之上的当前栈顶。(4)当一个过程执行完毕返回时,它在栈顶的数据区(包括活动记录和数组区)随即不复存在。由于C语言不含可变数组,故其活动记录本身包含了局部数组的空间。图6-2和图6-3分别给出了C语言和含可变数组的某简单语言程序运行时的数据空间结构,即显示了主程序调用了过程Q,Q调用了过程R,R投入运行后的存储结构。SPTOPR的活动记录Q的活动记录main的活动记录全局数据区图6-2C语言程序的存储组织SP总是指向执行过程活动记录的起点,TOP始终指向栈顶单元。当进入一个过程时,SP指向为此过程创建的活动记录的起点,TOP指向为此过程创建的活动记录的顶端。当进入一个过程时,SP指向为此过程创建的活动记录的起点,TOP指向为此过程创建的活动记录的顶端;若含有可变数组,则分配数组区后,TOP又改为指向数组区的顶端。图6-3含可变数组的程序的存储组织R的数组区R的活动记录Q的数组区Q的活动记录TOPSPmain的数组区main的活动记录主程序全局数据区C的活动记录含以下几个区段:(1)连接数据(两项):老SP值和返回地址,其中老SP为前一活动记录的起始地址;(2)参数个数;(3)形式单元(存放实参的值或地址);(4)过程的局部变量(简单变量)、数组的内情向量和临时工作单元。1TOP临时工作单元内情向量简单变量形式单元参数个数返回地址老SPSP20图6-4C过程的活动记录C语言不允许函数嵌套,即不允许一个过程的定义出现在另一过程的定义之内。因此,C语言的非局部变量仅能出现在源程序头,非局部变量可采用静态存储并在编译时确定它们的地址。C语言中,过程的每个局部变量或形参在活动记录中的位置是确定的。因此,变量和形参运行时在栈上的绝对地址:绝对地址=活动记录基址(SP)+相对地址对于当前正在执行的过程,其任一局部变量或形参A的引用均可表示为变址访问X[SP],其中X代表A相对于活动记录基址的偏移量,这个偏移量在编译时可完全确定下来。过程的局部数组的内情向量的相对地址在编译时同样可完全确定下来。当数据空间在过程中获得分配后,对数组元素的引用易于用变址方式访问。6.2.2过程的执行1.过程调用过程调用的四元式序列为:parT1parT2……parTncallP,n由于此时TOP指向被调过程P之前的栈顶,而P的形式单元与活动记录起点之间的距离是确定的(等于3),因而由调用过程给被调过程P的活动记录(正在形成)的形式单元传递实参值或实参地址,即每个parTi(i=1,…,n)可直接翻译成如下指令:(i+3)[TOP]=Ti//传参数值或(i+3)[TOP]=addr[Ti]//参数地址四元式callP,n翻译成:1[TOP]=SP//保护现行SP3[TOP]=n//传递参数个数JSRP//转向P过程参数个数nTOP+3SPT2T1现行SP值P的活动记录调用过程TOP43210……图6-5调用过程P之前先构造P的活动记录的部分内容2.过程进入转入过程P后,首先要做的是定义新活动记录的SP,保护返回地址和定义新活动记录的TOP值,即执行下述指令:SP=TOP+1//定义新SP1[SP]=返回地址//保护返回地址TOP=TOP+L//定义新TOP其中L是过程P的活动记录所需的单元数,该数在编译时可静态计算出。对含可变数组的情况,紧接上述指令之后是对数组进行存储分配的指令。对数组进行存储分配的指令是在翻译数组说明时产生的,对每个数组说明,相应的目标指令组将做以下工作:(1)计算各维的上下限;(2)调用数组空间分配子程序。数组空间分配子程序计算并填好内情向量的所有信息,然后在TOP所指位置之上留出数组所需空间,并将TOP调整为指向数组区顶端。P的数组区…返回地址P的活动记录(长度为L)1调用过程SPTOP0此后,在执行语句过程中,凡引用形参、局部变量或数组元素都以SP为基址进行相对访问。进入过程P后所做工作如下图:3.过程返回C语言及其它一些语言含return(E)形式的返回语句。假定E值已计算出来并存放在某临时单元T中,则此时可将T值传送到某个特定寄存器中(调用过程将从这个特定寄存器中获得被调过程P的结果)。剩下的工作是恢复SP和TOP,并按返回地址实行无条件转移,即执行下述指令序列:TOP=SP–1//恢复调用过程的TOP值SP=0[SP]//恢复调用过程的SP值X=2[TOP]//将返回地址送XUJ0[X]//无条件转移到调用过程一个过程也可通过它的end语句(C语言为})自动返回。若此过程是一个函数,则按上述办法传递结果值,否则仅直接执行上述返回指令序列。SPTOP…返回地址老SPP空间调用过程空间图6-7过程P的返回示意图6.3嵌套过程语言的栈式实现在简单程序语言实现中允许过程的递归调用,且过程中可含可变数组。现在再加上一种功能--允许过程的嵌套性,如PASCAL。由于PASCAL含有文件和动态变量,故它的存储分配不能简单地用栈式方法实现。考虑PASCAL的一个子集,即去掉文件和动态变量这两种数据类型,则可用下述方法实现存储分配:6.3.1嵌套层次显示表和活动记录假定主程序的层数为0。若过程Q是在层数为i的过程P内定义的,且P是包围Q的最小过程,则Q的层数为i+1。编译程序处理过程说明时,过程的层数作为过程名的一个重要属性登记在符号表中。由于过程定义是嵌套的,因而一个过程可以引用包围它的任一外层过程所定义的变量或数组,即运行时过程Q可引用它的任一外层过程P的最新活动记录中的某些数据。因此,过程Q运行时必须知道它的所有外层的最新活动记录的地址。由于允许递归和可变数组的存在,过程的活动记录位置往往是变迁的,因而必须设法跟踪每个外层过程的最新活动记录的位置。一种常用的跟踪每个外层过程最新活动记录位置的有效办法:每进入一个过程后,在建立它的活动记录区的同时建立一张嵌套层次显示表DISPLAY。假定现在进入的过程层数为i,则它的DISPLAY表含有i+1个单元。DISPLAY表本身是一个栈,自顶而下依次存放着现行层、直接外层…第0层的最新活动记录的起始地址。表6.1DISPLAY表假设过程R的外层为Q,Q的外层为主程序P,则R运行时的DISPLAY表的内容如表6.1所示。2R的现行活动记录的起始地址(SP的现行值)1Q的最新活动记录的起始地址0P的活动记录的起始地址由于过程的层数可静态确定,因此每个过程的DISPLAY表的体积在编译时即可知道。为了便于组织存储区,把DISPLAY表作为活动记录的一部分置于形式单元的上端。由于每个过程的形式单元数在编译时已知,因此DISPLAY表的相对地址d在编译时已确知。被调过程为了建立自己的DISPLAY,必须知道它的直接外层过程的DISPLAY。这意味着必须把直接外层的DISPLAY地址(称为全局DSPLAY地址)作为连接数据