运行时存储空间组织

第八章运行时存储空间组织版权所有，1997(c)DaleCarnegie&Associates,Inc.编译程序必须进行目标程序运行环境的设计和数据空间的分配。编译程序从操作系统中获得一块存储区域以使目标程序在其上运行，该存储区域需容纳生成的目标码和目标码运行时的数据空间。•数据空间应包括：用户定义的各种类型的数据对象所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，以及组织输入/输出所需的缓冲区。•根据数据空间确定时刻的不同，运行时的存储空间组织可分为静态存储和动态存储两大类。动态存储分配一般有栈式分配和堆式分配。8.1静态存储管理——FORTRAN存储分配•FORTRAN程序的特点：不允许过程的递归性；每一个数据名的性质是完全确定的，而且每一个数据名所需的存储空间大小是常量。•结论：整个程序所需数据空间的大小、位置在编译时是完全可以确定的。•问题：FORTRAN语言的公用（COMMON）和等价（EQUIVALENCE）语句造成不同的变量名对应的存储空间在位置上有相对的关系。静态分配策略要解决这种较为复杂的“名字—地址”对应关系。8.1.1数据区•每一个FORTRAN程序段和公用块都定义了一个对应的数据区。程序段的数据区存放的是未在COMMON中出现的局部名的值，称为该段的局部数据区。公用块里的各名字的值存放在公用区中。公用块分为一个无名公用块和若干个有名公用块。一般而言程序段的局部区可直接放在该段代码和常数单元之后。有名和无名公用区可安排在目标程序的后面。•数据区的存储映象：描述数据区的内容。一般由符号表中属于该数据区局部名的入口及其相对地址构成。对公共块而言，在各个程序段相应的符号表中应有一条连接该公共块各名字的链。一个公用块在个程序段中的所有这些名链构成了该块所对应数据区的存储映象。•一个数据区的内容一般含有：返回地址、寄存器保护区、形式单元、简单变量、数组、临时变量。8.1.2公用语句的处理公用语句的形式示例如下：DIMENSIONA（10，10）COMMONX，YCOMPLEXXCOMMON/B1/A，B，C//D，E，F（100）COMPLEXA，B•编译程序要做的工作是将该程序段对应符号表中的同一公用块的变量名用公用名链CMP连接起来。公用块的信息可用一张COMLIST（公用块名表）记载。•符号表：NAME。。。CMPX2Y6A4B5C0D7E8F0•公用块名表COMLISTNAMELENGTHFTLT无名。。。18B1。。。35•考虑编译程序遇到一个COMMON语句时应做的事情。8.1.3等价语句的处理•等价语句的形式示例：EQUIVALENCE（X，A（2，3）），（I，J，A（1，2），K）•该语句含有两个等价片。由于A出现在两个等价片中，因此X，A，I，J，K这些变量都有了位置上的关系。我们所要做的事情是处理程序段中的各个等价片，将各个在等价片中出现的变量之间的位移量确定下来。•扩展符号表增加EQ和OFFSET两栏。EQ栏是用来将等价元连接起来。OFFSET栏是用来表示等价元相对一个基址的位移量。•上例等价语句处理完后符号表的内容为NAME。。。OFFSETEQI-113J-114K-112X05A-211•等价片归并算法：1．置现行程序段符号表中所有的EQ栏为NULL。2．准备开始处理一个等价片，置P：=NULL；BASE：=0；3．从等价片中取一个等价元X，令X的符号表的入口为N，求出X的足标j。如果X是复型或双实型，则置L=2，否则置L=1。置X的相对数z为z：=BASE-j*L；4。若X已出现在等价链中（EQ[N]≠null），则转第6步；否则5把X加进现行环链中。6．X已在某一个等价环链中，准备把现行环和X原来所在的那个环合并为一。这时必须根据X的老相对数OFFSET[N]和现行相对数z的差数D（D=OFFSET[N]-z）来调整现象换中个等价元的相对数（把现象环中个等价元的相对数递增D），同时调整基准BASE，置BASE：=BASE+D，然后把两环合并为一。7．如果现行片中还有等价元则转第3步。8．若还有其它未处理的等价片则转第2步；否则表示所有等价语句已处理完毕。8.1.4地址分配•存储空间分配分为公用块中的公用元分配和局部名的地址分配。•分配过程中遇到等价元要解决该等价元所在等价片上的所有变量的地址分配。对局部名的分配首先要沿等价环寻找到等价环上相对数最小的变量进行地址分配，然后以此为基准对等价环上的其它等价元进行分配。公用块的分配无须寻找等价环上相对数最小的变量，但要发现公用区冒头的问题。8.2一个简单的栈式存储分配的实现•一个简单语言的假定：无分程序结构；过程定义无嵌套，但允许过程的递归调用；允许过程含有可变数组。•活动记录：含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元。•各个业已进入工作的过程数据区按调用顺序进入运行数据存储栈。运行数据栈最顶端数据区的两个指示器SP和TOP。SP指向现行过程活动记录的起点，TOP指向栈顶单元。8.2.1C的活动记录•C的活动记录内容：1．连接数据：1)老SP值2)返回地址2．参数个数3．形式单元(存放实在参数的值或地址)4．过程的局部变量、数组的内情向量和临时工作单元•局部变量的引用——变址访问X[SP]：X代表变量的相对数。8.2.2C的过程调用，过程进入，数组空间分配和过程返回•过程调用的四元式序列：parT1parT2parTncallP，n•parTi可翻译成如下指令(i+3)[TOP]:=Ti(传递参数值)或(i+3)[TOP]:=addr(Ti)(传递参数地址)•四元式callP,n可翻译成:1[TOP]:=SP(保护现行SP)3[TOP]:=n(传送参数个数)JSRP(转子指令,转向P的第一条指令)进入过程P后的动作:SP:=TOP+11[SP]:=返回地址TOP:=TOP+LL为过程P的活动记录所需的单元数，它在编译时可静态计算出。•对数组进行存储分配的指令：1.计算各维的上下限;2.调用数组空间分配子程序,其参数是:1)各维的上下限2)内情向量单元首地址•return(E)对应的指令序列:TOP:=SP-1SP:=0[SP]X:=2[TOP]UJ0[X]UJ为无条件转移指令,按X中的返回地址实行变址转移。8.2嵌套过程语言的栈式实现•语言限定的修改：允许过程的嵌套性，但不含分程序。•嵌套层次的概念。8.3.1嵌套层次显示表DISPLAY和活动记录•一个过程Q运行时必须知道它的所有外层过程的最新活动记录的地址。由于过程的递归性和可变数组，过程的活动记录的位置往往是变迁的。•跟踪外层过程的最新活动记录位置的办法之一：每进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表DISPLAY。•DISPLAY的内容：假定进入过程的层数为i，则它DISPLAY表含有i+1个单元。该表自顶向下每一个单元依次存放现行层，直接外层，...，直至最外层等每一层过程的最新活动记录的地址。•问题：一个过程的DISPLAY表的大小在编译时是否是确定的？如何根据DISPLAY表得到一个第K外层变量的值？•LDR1，（d+k）[SP]（获得第K层的最新活动记录）•LDR2，X[R1]（把X的值传送到R2）•问题：当过程P1调用过程P2而进入P2后，P2应如何建立起自己的DISPLAY表？•当过程P1调用过程P2时需要传递的连接数据为三项：老SP值，返回地址，全局DISPLAY地址。过程调用：parTi可翻译成如下指令：(i+4)[TOP]:=Ti(传递参数值)或(i+4)[TOP]:=addr(Ti)(传递参数地址)8.3.2过程调用，过程进入•CALLP，n翻译为1[TOP]:=SP(保护现行SP)3[TOP]:=SP+d(现行DISPLAY地址)4[TOP]:=n(传送参数个数)JSRP(转子指令,转向P的第一条指令)•过程进入:定义新的SP、TOP、保存返回地址复制全局DISPLAY。过程返回：TOP：=SP-1SP：=0[SP]X：=2[TOP]UJ0[X]8.3.3参数传递parT,T为数组：可变与确定数组的传递不同parT,T为过程：T的运行环境所需DISPLAY表的获得.parT,T为标号：需传送T的地址和T所在过程的活动记录地址parT,T为形式参数：传递形式单元T的内容.8.4ALGOL的实现•分程序的概念。•分程序结构的处理：1.可看成是无参数过程处理。2.一个过程中的分程序可用静态存储的观点来看待.