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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第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,T1)A*B,2.(+,T1,C,T2)A*B+C,3.(*,T2,B,T3)(A*B+C)*B,4.(-,T3,D,T4)(A*B+C)*B-D,5.(=:,T4,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内容(返回地址返回.,