目标程序运行时的存储组织(ppt 34页).ppt

10.1临时变量的存储分配,存储分配的原因：四元式产生大量临时变量(每个运算产生一个)，如不采取措施就会浪费大量存储单元。,例：ci的四元式1.(-,i,1,T1)2.(*,T1,5,T2)3.(,c,T2,T3),四元式QTi定义变量Y,则称i为Y的定义点；如果四元式QTj使用变量Z的值,则称j为Z的使用点。临时变量的存储分配可在中间代码一级进行,也可在目标代码一级进行。,现在的目标是让更多的临时变量共享内存单元。采用动态分配法，不直接给变量分配单元，只是确定抽象地址。,定义点和使用点全部落在一个基本块内的临时变量称之为良型临时变量。,只被定义一次，且只被定义一次。,定义点与使用点在一个基本块内。,良性临时变量的特点：,基本块1,基本块2,定义点,使用点,设i为临时变量T的定义点，j为最后一个使用点，则称区间i,j为T的活动区。设i,j和k,l是两个活动区,如果j=k或l=i,则称两个活动区不相交。,基本块,T1的活动区,i,j,k,l,T2的活动区,T1的活动区,i,k,j,l,T2的活动区,例子：设有语句Y:=(A*B+C)*B-D，则四元式为：1.(*,A,B,T1)A*B2.(+,T1,C,T2)A*B+C3.(*,T2,B,T3)(A*B+C)*B4.(-,T3,D,T4)(A*B+C)*B-D5.(=:,T4,X),各临时变量的定义点分别为：T11，T22，T33，T44各临时变量的最后使用点分别为：T12，T23，T34，T45各临时变量的活动区分别为：T11,2，T22,3，T33,4，T44,5,结论:每个临时变量的活动区均不相交。T1，T2，T3和T4将占用同一存储单元,从而实现节省存储的目标。尽管在四元式中出现了很多临时变量,但实际占用存储单元的还是极少数。,10.2静态链、动态链,1.以过程为单位的动态存储分配,所谓以过程为单位的动态存储分配就是以过程调用为单位来设置数据区。即设计一个数据空间栈，当程序运行时，每调用某过程一次，就根据该过程的说明为该过程在数据区栈的顶部分配一定数量的数据单元，称为该过程的数据区。当调用完毕，则释放该过程的数据区。,设有源程序：,programmain(input,output)consta=10;varb,c:integer;d,e:real;procedurep(x:real);varf:real;procedureq(y:real);constg=5;varh:boolean;procedurer(z:integer);,p,q,r,vari:integer;beginife0thenq(f);end;rbeginr(a);end;qbeginq(e);end;p,p,q,r,proceduret();varj:real;beginp(e);end;tbegint;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.以过程为单位的存储分配方案的实现,程序运行顺序：主程序tpqr,静态链：指向定义该过程的直接外层过程(或主程序)运行时刻的数据区的首(基)地址。,静态链作用：当动态地为某个过程在运行栈顶部建立数据区后，其中静态链为相应过程体内引用的所有变量提供了寻址途径，使得这些变量能以它们各自拥有的存储单元参与运算。,动态链：指向调用该过程前正在运行的过程的数据区的首(基)地址。,返回地址：记录了调用该过程时目标程序的断点，即当时的程序地址寄存器的值，是调用语句指令的下一条指令的地址。,动态链和返回地址的作用：为了当一个过程运行结束后，恢复其调用前的运行状态。,静态层次：主程序pqr0层1层2层3层,一个过程的静态外层是唯一的，而动态外层不唯一。运行顺序可以是:主程序tpqr主程序主程序tpqrq主程序主程序tpqrqr主程序,动态层次：调用该过程前正在运行的过程。,10.3过程的活动记录,过程的一次调用将占用内存的一片单元。在没有可变长度数据类型的情况下对于每个过程来说，其单元片长度是固定的。在四元式方案里该长度被记录在过程函数说明的头四元式中，称上述单元片为过程的活动记录。,Display表如下图：,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：设有：,即静态链为：主程序pq，假设动态链也为：主程序pq。,播放动画,主程序,主程序p,主程序pq,例2:现有静态链和动态链相同的程序静态链主程序pq动态链主程序pq已知x的抽象地址为x(k,off)。当程序运行到q时,求x的值。,分析：1.当x为q过程的变量，求x的值。2.当x为p过程的变量，求x的值。3.当x为主程序的变量，求x的值。,例3:现有静态链和动态链不相同的程序主程序pqrt,动态链为：主程序tpqr,活动记录：,主程序,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是被调过程的层数),再添上新的s