第10章目标程序运行时的组织

第10章目标程序运行时的组织10.1概述10.2数据表示10.3目标程序运行时的栈式存储组织10.4参数传递10.5堆式存储组织的讨论概述-代码生成解决语义gap高级语言支持的概念TypevalueexpressionVariableprocedureFunctionparameters目标机支持的概念bitsbyteswordsRegistersStackaddressRoutine(subroutine)概述代码生成前如何安排目标机资源运行时组织的几个问题数据表示-如何在目标机中表示每个源语言类型的值表达式求值-如何组织表达式的计算存储分配-如何组织不同作用域变量的存储过程实现-如何以例程实现过程，函数，参数传递概述任务：编译程序对目标程序运行时的组织（设计运行环境和分配存储）如通常存储区布局可为：目标代码区静态数据区Stackheap运行环境和存储分配设计分析逻辑阶段：在目标代码生成前，作准备实质：关联（Binding）将源程序的文本程序运行动作的实现源文件中的名字N运行时的存储S在语义学中，使用术语environment函数表示env:N→S(N到S的映射)静态文本中运行时动作及为实现其动作的准备（与运行时数据对象的表示有关）过程定义过程名执行过程体过程体控制数据对象的分配，为执行过程体使用源文本中同样的名字目标程序中不同的数据空间因为一个过程可以是递归的，这时同一个名字在不同的时间可能代表不同的存储单元决定运行管理复杂程度的因素——源语言本身1.允许的数据类型的多少2．语言中允许的数据项是静态确定动态确定3．程序结构决定名字的作用域的规则和结构A．段结构B．过程定义不嵌套，只允许过程递归调用C．分程序结构分程序嵌套过程定义嵌套4存储类别的多少GlobalStaticLocaldynamic术语静态：如果一个名字的性质通过说明语句或隐或显规则而定义，则称这种性质是“静态”确定的。动态：如果名字的性质只有在程序运行时才能知道，则称这种性质为“动态”确定的。例procedureA(m,n:integer);beginrealz;arrayB[m:n];begin···end;end;声明的作用域词法作用域动态作用域例：（1）programdynamic(i,0);(2)varr:real(3)procedureshow;(4)beginwrite(r:5:3)end;(5)procedruesmall;(6)varr:real;(7)beginr:=0.125;showend;(8)begin(9)r:=0.25;(10)show;small;write/n;(11)show;small;write/n;(12)end.lexicalscope0.2500.2500.2500.250dynamicscope0.2500.1250.2500.125数据表示（各种数据对象的存储分配）数据对象的属性name名字，名称type类型location内存地址value值component成分数据表示（固定长度，直接或间接表示）简单变量：char:1byteintegers:2or4bytesfloats:4to16bytesbooleans:1bit(butusually1byte)指针：unsignedintegers一维数组：一块连续的存储区多维数组：一块连续的存储区，按行存放结构（记录）：把所有域（field)存放在一块连续的存储区对象：类的实例变量象结构的域一样存放在一块连续的存储区，但方法（成员函数）不存在该对象里指令：例：按行A是1020的二维数组A[1,1]A[1,2]..第一行..A[1,20]A[2,1]..第二行........A[10,20]第十行数组元素的地址计算设A[1，1]的地址为a，每个元素占一个字A[i，j]的地址：a+（i-1）20+（j-1）=（a-21）+（20i+j）一般：arrayA[l1：u1，l2：u2，……，ln：un]令di=ui-li+1元素A[i1，i2，……，in]的地址DD=a+（i1-l1）d2d3……dn+（i2-l2）d3d4……dn+……+（in-1-ln-1）dn+（in-ln）经因子分解后得D=CONSPART+VARPART其中CONSPART=a-CC=（……（（l1d2+l2）d3+l3）d4+……+ln-1）dn+lnVARPART=（……（（i1d2+i2）d3+i3）d4+……+in-1）dn+in四元式两组VARPARTTCONSPARTT1T1[T]表示数组元素的地址数组元素引用：X：=T1[T]对数组元素赋值：T1[T]：=Xl可变(动态)数组：若一个数组所需的存储空间的大小在编译时就已知道，则称它为确定数组，否则称为可变(动态)数组。数组内情向量：编译将数组的有关信息记录在一些单元中，称为数组的“内情向量”A[l1:u1,l2:u2,,ln:un]l1u1l2u2::typea（首地址）nC目标程序运行时的存储组织存储分配策略：简单的栈式分配方案嵌套过程的栈式分配方案分程序结构的存储分配方案静态存储分配动态存储分配——栈式堆式l术语-过程活动记录AR:为说明方便，假定程序是由过程组成，过程区分为源文本，运行时称作过程的激活。一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区（块）叫做一个活动记录或frame（帧）一般这个段要记录：l临时值，如计算表达式时的中间工作单元。l局部变量（数据）l保存运行过程前的状态（返回地址，寄存器值……）l存取链（可选）对于非局部量的引用。l控制链（可选）指向调用者的活动记录，释放栈。l实参（形式单元）l返回值（对函数）（有时可使用寄存器存放返回值）简单的栈式分配方案程序结构特点:过程定义不嵌套，过程可递归调用，含可变数组;例:main全局变量的说明•procR•……•endR;•procQ•……•endQ;•主程序执行语句endmainMain----Q----RMain---Q----QTOP-----R的活动记录Q的活动记录SP------Q的活动记录Q的活动记录主程序全局主程序全局数据区数据区TOP----临时工作单元局部简单变量局部数组的内情向量保存运行过程前的状态（返回地址，寄存器值……）实参（形式单元）和参数个数SP-----控制链（老SP）TOPR的数组区SPR的活动记录Q的活动记录主程序全局数据区嵌套过程语言的栈式分配方案l主要特点：（语言）一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）。（实现）一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。关键技术：解决对非局部量的引用（存取）。设法跟踪每个外层过程的最新活动记录AR的位置。跟踪办法：1.用静态链（如PL/0的SL）。2.用DISPLAY表。consta=10;varb,c;procedurep;beginc:=b+a;end;beginread(b);whileb#0dobegincallp;write(2*c);read(b);endend.(0)jmp08转向主程序入口(1)jmp02转向过程p入口(2)int03过程p入口,为过程p开辟空间(3)lod13取变量b的值到栈顶(4)lit010取常数10到栈顶(5)opr02次栈顶与栈顶相加(6)sto14栈顶值送变量c中(7)opr00退栈并返回调用点(16)(8)int05主程序入口开辟5个栈空间(9)opr016从命令行读入值置于栈顶(10)sto03将栈顶值存入变量b中(11)lod03将变量b的值取至栈顶(12)lit00将常数值0进栈(13)opr09次栈顶与栈顶是否不等(14)jpc024等时转(24)（条件不满足转）(15)cal02调用过程p(16)lit02常数值2进栈(17)lod04将变量c的值取至栈顶(18)opr04次栈顶与栈顶相乘(2*c)(19)opr014栈顶值输出至屏幕(20)opr015换行(21)opr016从命令行读取值到栈顶(22)sto03栈顶值送变量b中(23)jmp011无条件转到循环入口(11)(24)opr00结束退栈目标代码解释执行时数据栈的布局（运行栈的存储分配）每个过程的AR有3个联系单元：–SL：静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。–DL：动态链，指向调用该过程前正在运行过程的数据段基地址。–RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址。局部变量中间结果目标代码的解释执行运行栈SM调用过程PRADLSLb..ttbPM解决对非局部量的引用（存取）用Display表Display表---嵌套层次显示表当前激活过程的层次为K，它的Display表含有K+1个单元，依次存放着现行层，直接外层…直至最外层的每一过程的最新活动记录的基地址例：programmain(i,0);程序结构图……procR(c,d);……Rend/*R*/procP(a);主……procQ(b);……PQcallRR(x,y);end/*Q*/callQ……Q(z);callPend/*P*/……callRP（W）；……R（U，V）；……end/*main*/用Display表的方案(1)主程序---(2)P---(3)Q---(4)RP的活动记录主程序的活动记录d[1]d[0]displaysptop主程序的活动记录d[0]spdisplaytop（1）（2）用Display表的方案主程序---P---Q---RR的活动记录Q的活动记录P的活动记录主程序的活动记录Q的活动记录P的活动记录主程序的活动记录displayd[2]d[1]d[0]d[1]d[0]displaysptoptopsp（3）（4）DISPLAY表的维护和建立DISPLAY表d运行栈0主程活动记录地址1R活动记录地址...0老SP1返回地址2全局DISPLAY地址3参数个数4形式单元...dDISPLAY...简单变量数组内情向量临时变量•当过程的层次为n，它的display为n+1个值。•一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。•全局DISPLAY地址分程序结构ProcedureA(m,n);integerm,n;B1:beginrealz;arrayB[m:n];B2:beginreald,e;L3:2end;B4:beginarrayC[1:m];1B5:beginreale;L6:54end;end;L8:end;分程序结构的存储分配方案处理分程序结构存储分配方案的一种简单办法是，把分程序看成“无名无参过程”，它在哪里定义就在哪里被调用。因此，可以把处理过程的存储办法应用到处理分程序中。但这种做法是极为低效的。一则，每逢进入一个分程序，就照样建立连接数据和DISPLAY表,这是不必要的。二则，当从内层分程序向外层转移时，可能同时要结束若干个分程序。按照过程处理办法，意味着必须一层一层地通过“返回”来恢复所要到达的那个分程序的数据区，但不能直接到达。例如：如果有一个从第5层分程序转出到达第1层分程序的标号L，虽然在第5层分程序工作时知道L所属的层数，我们极易从DISPLAY中获得第1层分程序的活动记录基址（SP），但是怎么知道第1层分程序进入时的TOP呢？唯一的办法是从5,4,3和2各层顺序退出。但这种办法是很浪费时间的。为了解决上述问题，可采取两种措施。第一，对每个过程或分程序都建立有自己的栈顶指示器TOP，代替原来仅有过程的栈顶指示器,每个TOP的值保存在各自活动记录中。这样，上述的第二个问题便可解决。第二，不把分程序看作“无参过程”，每个分程序享用包围它的那个最近过程的DISPLAY。每个分程序都隶属于某个确定的过程，分程序的层次是相对于它所属的那个过程进行编号的。：每个过程被当作是0层分程序。而过程体分程