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

第10章目标程序运行时的存储组织10.1临时变量的存储分配存储分配的原因：四元式产生大量临时变量(每个运算产生一个)，如不采取措施就会浪费大量存储单元。例：c[i]的四元式1.(-,i,1,T1)2.(*,T1,5,T2)3.([],c,T2,T3)四元式QT[i]定义变量Y,则称i为Y的定义点；如果四元式QT[j]使用变量Z的值,则称j为Z的使用点。临时变量的存储分配可在中间代码一级进行,也可在目标代码一级进行。现在的目标是让更多的临时变量共享内存单元。采用动态分配法，不直接给变量分配单元，只是确定抽象地址。定义点和使用点全部落在一个基本块内的临时变量称之为良型临时变量。只被定义一次，且只被定义一次。定义点与使用点在一个基本块内。良性临时变量的特点：基本块1基本块2定义点使用点设i为临时变量T的定义点，j为最后一个使用点，则称区间[i,j]为T的活动区。设[i,j]和[k,l]是两个活动区,如果j=k或l=i,则称两个活动区不相交。基本块T1的活动区ijklT2的活动区T1的活动区ikjlT2的活动区例子：设有语句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)各临时变量的定义点分别为：T1—1，T2—2，T3—3，T4—4各临时变量的最后使用点分别为：T1—2，T2—3，T3—4，T4—5各临时变量的活动区分别为：T1—[1,2]，T2—[2,3]，T3—[3,4]，T4—[4,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);pqrvari:integer;begin……ife0thenq(f);……end;{r}beginr(a);end;{q}beginq(e);end;{p}pqrproceduret();varj:real;beginp(e);end;{t}begin……t;……end;{main}t程序运行顺序和建立的数据区：主程序→t→p(e)→q(e)→r(a)q(f)当e0时主程序ttttt主程序主程序主程序主程序主程序p(e)p(e)p(e)p(e)q(e)q(e)q(e)r(a)r(a)q(f)1236542.以过程为单位的存储分配方案的实现主ptqr0层1层2层3层程序运行顺序：主程序→t→p→q→r静态链：指向定义该过程的直接外层过程(或主程序)运行时刻的数据区的首(基)地址。静态链作用：当动态地为某个过程在运行栈顶部建立数据区后，其中静态链为相应过程体内引用的所有变量提供了寻址途径，使得这些变量能以它们各自拥有的存储单元参与运算。动态链：指向调用该过程前正在运行的过程的数据区的首(基)地址。返回地址：记录了调用该过程时目标程序的断点，即当时的程序地址寄存器的值，是调用语句指令的下一条指令的地址。动态链和返回地址的作用：为了当一个过程运行结束后，恢复其调用前的运行状态。主ptqr0层1层2层3层静态层次：主程序pqr0层1层2层3层一个过程的静态外层是唯一的，而动态外层不唯一。运行顺序可以是:主程序→t→p→q→r→主程序主程序→t→p→q→r→q→主程序主程序→t→p→q→r→q→r→主程序动态层次：调用该过程前正在运行的过程。10.3过程的活动记录过程的一次调用将占用内存的一片单元。在没有可变长度数据类型的情况下对于每个过程来说，其单元片长度是固定的。在四元式方案里该长度被记录在过程函数说明的头四元式中，称上述单元片为过程的活动记录。Display表如下图：top→外层sp地址先行DISPLAY地址返回地址函数值形参单元本层DSPLAY表临时变量单元局部变量单元N321sp→0l+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：设有：主pqP0P1P2即静态链为：主程序—p—q，假设动态链也为：主程序—p—q。播放动画DL外层SP的地址，主程序特殊直接定义外层过程的Display表的首地址RA返回地址函数值、形参单元本层Display表(主程序首地址)局部变量、临时变量单元主程序DL先行Display表，存主程序Display表的首地址SPRA返回地址函数值、形参单元主程序的Display表P过程活动记录首地址SPDisplay表变量单元主程序—pDL先行Display表，存P过程Display表的首地址SPRA返回地址函数值、形参单元主程序的Display表P过程活动记录首地址SPP过程Display表q过程活动记录首地址SPDisplay表变量单元主程序—p—q例2:现有静态链和动态链相同的程序静态链主程序—p—q动态链主程序—p—q已知x的抽象地址为x(k,off)。当程序运行到q时,求x的值。分析：1.当x为q过程的变量，求x的值。2.当x为p过程的变量，求x的值。3.当x为主程序的变量，求x的值。例3:现有静态链和动态链不相同的程序主程序pqrt动态链为：主程序—t—p—q—r活动记录：主程序t过程r过程q过程p过程Display表主程序Display表本层首地址函数值、形参RA返回地址主程序Display表首地址变量DL动态链10.4活动记录的填写每当调用一过程时，要建立新的活动记录；每当退出一过程时，要删除现役活动记录；这些工作都要目标程序来完成，主要由过程语句、过程入口和过程出口部分来完成。过程语句所完成的工作：1.在要建立的新活动记录里保存现役活动记录的始地址:0[top]:=sp.(动态链)2.在要建立的新活动记录里记入先行DISPLAY表的始地址:(静态链)1)实在过程语句情形:1[top]:=sp+N.2)形式过程语句情形:1[top]:=(第二形参单元).其中第二个形参单元是给过程语句名分配的第二个单元.3.把实参信息传送到新活动记录区的形参单元中.4.转向相应过程的目标程序.过程入口处完成的工作：1.在要建立的新活动记录里保存返回地址:2[top]:=返回地址.(返回地址)2.在要建立的新活动记录里生成DISPLAY表:从1[top]所指的先行DISPLAY表自底向上抄录l个单元的内容(l是被调过程的层数),再添上新的sp值.3.使新建的活动记录成为现役活动记录:sp:=top;top:=top+Moff其中Moff为被调用过程的最大off值+1.过程出口处完成的工作：1.删除本层活动记录,使动态外层的活动记录成为现役活动记录:top:=sp;sp:=0[sp].2.按2[top]内容(返回地址）返回.