目标程序运行时的存储组织

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,10,章,目标程序运行时的存储组织,10.1,临时变量的存储分配,存储分配的原因：四元式产生大量临时变量,(,每个运算产生一个,),，如不采取措施就会浪费大量存储单元。,例：,ci,的四元式,1.(-, i, 1, T,1,),2.(*, T,1,5, T,2,),3.(, c, T,2,T,3,),四元式,QTi,定义变量,Y,则称,i,为,Y,的,定义点,；如果四元式,QTj,使用变量,Z,的值,则称,j,为,Z,的,使用点,。,临时变量的存储分配可在中间代码一级进行,也可在目标代码一级进行。,现在的目标是让更多的临时变量共享内存单元。采用动态分配法，不直接给变量分配单元，只是确定抽象地址。,定义点和使用点全部落在一个基本块内的临时变量称之为,良型临时变量,。,只被,定义一次，且只被定义一次。,定义点与使用点在一个基本块内。,良性临时变量的特点：,基本块,1,基本块,2,定义点,使用点,设,i,为临时变量,T,的定义点，,j,为最后一个使用点，则称区间,i,j,为,T,的,活动区,。,设,i,j,和,k,l,是两个活动区,如果,j=k,或,l=i,则称两个活动区,不相交,。,基本块,T,1,的,活动区,i,j,k,l,T,2,的,活动区,T,1,的,活动区,i,k,j,l,T,2,的,活动区,例子：,设有语句,Y:=(A*B+C)*B-D,，,则四元式为：,1.(*, A, B, T,1,),A*B,2.(+, T,1,C, T,2,),A*B+C,3.(*, T,2,B, T,3,),(A*B+C)*B,4.(-, T,3,D, T,4,),(A*B+C)*B-D,5.(=:,T,4,X ),各,临时变量的定义点分别为：,T,1,1,，,T,2,2,，,T,3,3,，,T,4,4,各临时变量的最后使用点分别为：,T,1,2,，,T,2,3,，,T,3,4,，,T,4,5,各临时变量的活动区分别为：,T,1,1,2,，,T,2,2,3,，,T,3,3,4,，,T,4,4,5,结论,:,每个临时变量的活动区均不相交。,T,1,，,T,2,，,T,3,和,T,4,将占用同一存储单元,从而实现节省存储的目标。,尽管在四元式中出现了很多临时变量,但实际占用存储单元的还是极少数。,10.2,静态链、动态链,1.,以过程为单位的动态存储分配,所谓以,过程为单位的动态存储分配就是以过程调用为单位来设置数据区。即设计一个数据空间栈，当程序运行时，每调用某过程一次，就根据该过程的说明为该过程在数据区栈的顶部分配一定数量的数据单元，称为该过程的数据区。当调用完毕，则释放该过程的数据区。,设有源程序：,program,main(input, output),const a =10;,var,b, c: integer;,d, e: real;,procedure p ( x: real );,var,f: real;,procedure q ( y: real );,const g = 5;,var,h:,boolean,;,procedure r (,z:integer,);,p,q,r,var,i: integer;,begin,if e0 then q ( f );,end; r,begin,r ( a );,end; q,begin,q ( e );,end; p,p,q,r,procedure t ( );,var,j: real;,begin,p ( e );,end; t,begin,t;,end; main,t,程序运行顺序和建立的数据区：,主程序,tp(e)q(e)r(a,),q(f,),当,e0,时,主程序,t,t,t,t,t,主程序,主程序,主程序,主程序,主程序,p(e,),p(e,),p(e,),p(e,),q(e,),q(e,),q(e,),r(a,),r(a,),q(f,),1,2,3,6,5,4,2.,以过程为单位的存储分配方案的实现,主,p,t,q,r,0,层,1,层,2,层,3,层,程序运行顺序：主程序,t,p,q,r,静态链,：指向,定义,该过程的,直接,外层过程,(,或主程序,),运行时刻的数据区的首,(,基,),地址。,静态链作用,：当动态地为某个过程在运行栈顶部建立数据区后，其中静态链为相应过程体内引用的所有变量提供了寻址途径，使得这些变量能以它们各自拥有的存储单元参与运算。,动态链,：指向调用该过程前正在运行的过程的数据区的,首,(,基,),地址。,返回地址,：记录了调用该过程时目标程序的断点，即当时的程序地址寄存器的值，是调用语句指令的下一条指令的地址。,动态链和返回地址的作用,：为了当一个过程运行结束后，恢复其调用前的运行状态。,主,p,t,q,r,0,层,1,层,2,层,3,层,静态层次：主程序,p q r,0,层,1,层,2,层,3,层,一个过程的静态外层是唯一的，而动态外层不唯一。,运行顺序可以是,:,主程序,tpqr,主程序,主程序,tpqrq,主程序,主程序,tpqrqr,主程序,动态层次：调用该过程前正在运行的过程。,10.3,过程的活动记录,过程的一次调用将占用内存的一片单元。在没有可变长度数据类型的情况下对于每个过程来说，其单元片长度是固定的。在四元式方案里该长度被记录在过程函数说明的头四元式中，称上述单元片为,过程的活动记录,。,Display,表如下图：,top,外层,sp,地址,先行,DISPLAY,地址,返回地址,函数值,形参单元,本层,DSPLAY,表,临时变量单元,局部变量单元,N,3,2,1,sp,0,l,+1,项,d,项,编译时可确定,设一个变量,X,的抽象地址为,(,k,off,),则它所对应的动态地址,addr(k,off,),可按下式计算,:,addr(k,off,)=,DISPLAY(k)+off,=,CONTENT(sp+N+k)+off,其中,N,是编译可确定的。当,k,为现役过程的层数时，有：,addr(k,off,)=,sp+off,例,1,：设有：,主,p,q,P,0,P,1,P,2,即,静态链为：主程序,pq,，假设动态链也为：主程序,pq,。,播放动画,DL,外层,SP,的地址，主程序特殊,直接定义外层过程的,Display,表的首地址,RA,返回地址,函数值、形参单元,本层,Display,表,(,主程序首地址,),局部变量、临时变量单元,主程序,DL,先行,Display,表，存主程序,Display,表的首地址,SP,RA,返回地址,函数值、形参单元,主程序的,Display,表,P,过程活动记录首地址,SP,Display,表,变量单元,主程序,p,DL,先行,Display,表，存,P,过程,Display,表的首地址,SP,RA,返回地址,函数值、形参单元,主程序的,Display,表,P,过程活动记录首地址,SP,P,过程,Display,表,q,过程活动记录首地址,SP,Display,表,变量单元,主程序,pq,例,2:,现有静态链和动态链相同的程序,静态链 主程序, p q,动态链 主程序, p q,已知,x,的抽象地址为,x( k, off ),。当程序运行到,q,时,求,x,的值。,分析：,1.,当,x,为,q,过程的变量，求,x,的值。,2 .,当,x,为,p,过程的变量，求,x,的值。,3.,当,x,为主程序的变量，求,x,的值。,例,3:,现有静态链和动态链不相同的程序,主程序,p,q,r,t,动态链为：主程序,t,p,q,r,活动记录：,主程序,t,过程,r,过程,q,过程,p,过程,Display,表,主程序,Display,表,本层首地址,函数值、形参,RA,返回地址,主程序,Display,表首地址,变量,DL,动态链,10.4,活动记录的填写,每当调用一过程时，要建立新的活动记录；每当退出一过程时，要删除现役活动记录；这些工作都要目标程序来完成，主要由过程语句、过程入口和过程出口部分来完成。,过程语句所完成的工作：,1.,在要建立的新活动记录里保存现役活动记录的始地址,: 0top:=sp.,(,动态链,),2.,在要建立的新活动记录里记入先行,DISPLAY,表的始地址,:,(,静态链,),1),实在过程语句情形,:,1top:=,sp+N,.,2),形式过程语句情形,:,1top:=(,第二形参单元,).,其中第二个形参单元是给过程语句名分配的第二个单元,.,3.,把实参信息传送到新活动记录区的形参单元中,.,4.,转向相应过程的目标程序,.,过程入口处完成的工作：,1.,在要建立的新活动记录里保存返回地址,:,2top:=,返回地址,.,(,返回地址,),2.,在要建立的新活动记录里生成,DISPLAY,表,:,从,1top,所指的先行,DISPLAY,表自底向上抄录,l,个单元的内容,(,l,是被调过程的层数,),再添上新的,sp,值,.,3.,使新建的活动记录成为现役活动记录,:,sp:=top; top:=,top+Moff,其中,Moff,为被调用过程的最大,off,值,+1.,过程出口处完成的工作：,1.,删除本层活动记录,使动态外层的活动记录成为现役活动记录,:,top:=sp; sp:=0sp.,2.,按,2top,内容,(,返回地址）返回,.,