1、第八章 运行时空间组织,常见的分配策略：1，静态分配策略，适用于编译时能完全确定每个数据项存储空间的位置情况，如 FORTRAN；2，动态分配策略，编译时不能完全确定数据项的性质，大小等，如 ALGOL, 它允许递归过程和可变数组，名字作用域和生存期满足分程序结构所限定的作用范围，可采用栈式动态分配策略（内存先申请先释放）；当一种语言内存申请和释放不遵循先请后放时，一般的处理方法是：让运行程序持有一个大存区（称为堆），凡申请者从堆中分给一块，凡释放者归还给堆，叫做堆式动态分配策略,1,8.1 静态存储管理 - FORTRAN 存储分配,FORTRAN 的特点：1，过程不允许递归；2，每个数据名
2、所需的存储空间是常数（无可变数组）3，数据名的性质完全确定,FORTRAN 的可调数组：不是可变数组，例子：,子程序：FUNCTION DIA ( A, N, L ) DIMENSION A ( L, L ) DIA = A ( 1, 1 ) DO 6 I = 2, N 6 DIA = DIA + A ( I, I ) RETURN END,主程序： DIMENSION X ( 50, 50 ), DIMENSION Y( 100, 100 ) P1 = DIA ( X, 10, 50 ) + DIA ( Y, 100,100),2,8.1.1 数据区,一个 FORTRAN 程序：,3,符号表
3、：,子程序：SUBROTINE SWAP ( A, B ) T = A A = B B = T RETURN END,4,分层分配方案,1，将源表示成一个有层次的有向图2，从有向图的最低层开始, 往上逐层对程序块分配存储单元,20-30,13-19,8-12,6-14,15-18,如果不重叠, 需要55个单元现在只要31个,5,关于区 COMPILER 所作的工作,1，名字填符号表2，分局部区号3，构造数据区的相应存储映象：局部区，公用块,局部数据区的内容,6,COMMON语句介绍,COMMON/n1/a1,a2,an,/n2/b1,b2,bn/ /R,X,Y,Z,1, 格式,公用区名,变量名
4、, 数组名, 数组说明符,无名公用区,2, 用途,A, 不同程序块的变量之间建立联系,主程序:COMMON Z1,Z2,AL,BE,GAREAD(11,1)AL,BE,GACALL QUAD,子程序:SUBROUTINE QUADCOMMON X1,X2, A,B,C,结果,初值,B, 节省单元,2块程序可以公用一个公用块, 特别是数组,7,组说明符,数组名,交换次序,3, 使用,A, COMMON A(2,3),B,DIMENSION A(2,3)COMMON A,C,COMMON ADIMENSION A(2,3),8,8.1.2 公用语句处理,用途：不同程序段之间共享数据,COMMON
5、/B1/A,B,C,COMMON /B1/E,F,G,B1,9,处理方法,COMMON / B1 / A, B, C ( 50 )DIMENSION A ( 10, 10 ), B ( 100 )COMPLEX A, B,当首次扫描到 B1 的时候并不能立即确定每个公用元的相对地址 怎么办？,10,CMP 和 公用表名 COMLIST,以 COMMON /B1/ A, B, C 为例,引入 CMP 后的符号表：,COMLIST 表：,123,B1区链完成的最后结果,新段开始, FT,LT= 0,查COMLIST表无B1,填B1, B1.FT=B1.LT=null, length不变,B1,nu
6、ll,null,2,3,0,0,对A(入口为 1 ),1,1,对B(入口为 2 ),2,3,0,A,B,C,11,1，若块名 BLK1 未出现在 COMMLIST 中，则把它填入并形成它的空链（FT 和 LT 原来已经为 NULL）2，把符号表中的 NAM1 和 NAM2 标志为属于公用区，并把他们依次连接到 BLK1 原链的末端。若原链为空则把 NAM1 的入口填到 FT 栏中。最后，调整 LT 使它指向新链的末端。,处理 COMMON /BLK1 /NAM1, NAM2的算法,12,8.1.3 等价语句处理,1, 等价语句介绍,a, 格式:EQUIVALENCE(变量表1),(变量表2),
7、b, 用途: 同一等价片中的变量共同存储单元 1) 节省: EQU(A,B,C,D) 变量A,B,C,D共同单元 2) 同一量定义不同名字,13,c,使用: 1) 数组等价 : DIMENSION A(2,3), B(4) EQU(A(1,2),B(1)2) 间接联系 : DIM A(2,3), B(4) EQU(A(1,2),C),(C,B(1)3) 不可矛盾 : DIM A(10) EQU(X, A(1), (X,A(3) DIM A(5), B(10) EQU(A(1), B(2)(A(3),B(3),14,2, 等价语句处理,FORTRAN 的等价语句目的在于建立一个程序段中诸变量或数
8、组之间的存储空间的一致性,例, 处理等价语句：EQUIVALENCE ( X, A( 2, 3 ),(I, J, A( 1, 2 ), K)1,规则 :a, 对于简单变量 I,J 属一个等价片, 表示 I,J 占用同一单元b, 对于(X, A2,3),名表中无A2,3, 只有A,要指出 X 与 A 位置关系, 引入相对数-A11,相对 X 的地址. c, 对于同一个等价元 A11 在不同的片中出现, 表示这两片的等价元存储是相关的, 他们应予以合并, 原则是后一等价片按照第一片调整相对数.,15,数组 A(i1, i2,in) 的足标 j 的计算公式：1，若等价元为简单变量，则足标为 0；2，
9、若等价元为数组元素，则足标为(di 为维长) :,( i1 - 1) + d1 * ( i2 -1 ) + + di * *dn-1 * ( in 1 ),2,语句为存储分配提供信息, 指出那些是等价片. 对它的处理需在名表中增加记号, 为此设栏目.引入 EQ -指出同一片的,下一个等价元的入口引入 OFFSET -指出他们的偏移量, OFFSET的计算需要引入足标j, 基准BASE,3,算法 : 2 个工作变量 ： P 和 BASE P 指示现行等价链首元在名表入口 BASE 计算等价元相对数的基准, 若在本链中, BASE = 0, 否则 BASE = 新链基在老链基的相对数 z 相对数,
10、 z = BASE j*L (L 所需字数),16,4, 等价环的建立过程(具体做法),等价语句 EQUIVALENCE ( X, A( 2, 3 ),(I, J, A( 1, 2 ), K), 指针p指向等价环首部, 这里没有画出.,1, 第1片, 第1元 x, x为基准, 它相对自己的 z = 0, OFFSET = 0, 本链内 BASE = 0名表工作: 自环.,2, 第2元 A2,3, A1,1相对x的 地址为z = BASE j*L = -21 名表工作: A1,1 与x 链接, A1,1 的 OFFSET = z = -21.,3, 第2片, 第1元I , I 为基准地址, 本链
11、内的 BASE = 0, 名表工作: 自环,4, 第2片, 第2元J , z = BASE j*L= 0, 名表工作: J 链入 I, OFFSET =0,5, A1,2, A1,2由于第一片的A2,3, 已经在第一片中占有一席之地, 现在由于与I,J 等价, 它将把I, J 带入第一等价片中合并, 关键之一是老环中 I, J 的相对数的计算. A1,2以I 为基准, A1,1 相对于I 的相对数为 Z = BASE j*L = -10a, 当把新环中的等价元I, J链入到原环时, 新环的相对数都要调整:z = z原+D, 其中 D = (A的老相对数 - 21) (A的新相对数-10)b,
12、合并环, 新环指针 p c, 基准改变, BASE = BASE + D = -11, 现行等价链的基准要搬到老链来看,6, 第2片, 第3元K , K 首变, z = BASE j*L= -11 OFFSET, K与I 等价, 应与I 有相同的 z 插入链中, 由 p 指出,加入 EQ 和 OFFSET 栏之后的符号表（等价语句 EQUIVALENCE ( X, A( 2, 3 ),(I, J, A( 1, 2 ), K)）,12345,环：XAIKJX,1,5,2,4,3,18,算法,BEGIN 把符号表中所有 EQ 栏置为 null /初始化WHILE 存在未处理的等价片 DOBEGIN
13、 /* 开始处理新等价片 */P := null ; BASE := 0 ;WHILE 现行片中尚有未处理的等价元 DOBEGIN 取出下一个等价元 X , 假定它在符号表的 入口为 N, 计算出 X 的足标 j ; IF X 为“双实型” 或者 “复型” THEN L := 2 ELSE L := 1; z := BASE j * L ; IF EQ N = null BEGIN IF P = null THEN,19,P := N ; ELSE EQ N := EQ P ; EQ P := N; OFFSET N := z;END ELSE BEGIN D := OFFSET N z;BA
14、SE := BASE + D;IF P = null THEN P := N ELSEBEGIN Q := P;LOOP: IF Q = N THENIF D != 0 THEN ERROR （等价冲突）ELSE GOTO NXELE;OFFSET Q := OFFSET Q + D;Q1 := Q; Q := EQ Q ;IF Q != P THEN GOTO LOOP;MERGE:,20,EQ Q1 := EQ N ; EQ N := P;END OF MERGING; END;NXELE; END OF THE INNER WHILE;END OF THE OUTER WHILE;END
15、,21,8.1.4 地址分配,对于所有说明性语句处理后，即类型信息等以及EQ,OFFSET,在名表建立，COMLIST建立之后，可以对变量，数组名进行分配地址，即填DA,ADDR,对于易碎的个体，地址分配无什么要求，但COMMON 的公共块B1要求其成员必须保持其顺序，而EQUIVALENCE中的等价片元必须使等价元共享存储。等价片和公共块谁先处理？决定于前者的处理不要给后者的处理设置障碍。先等价，后公共，问题更多。先公共，后等价比较容易处理，只有一点限制（冒头），所以我们先处理公共语句的块.,先分配COMMON的原因,COMMON A1,B,C,A,DDEMENSION A(10,10)EQ
16、UIVALANCE(I,J,A1,2,K) (X, A2,3),1,公用块中公用元分配,A1.EQ = NULL, 非等价元,即可分配地址a, a后移 size(A1)B,C 同理,1,2,3,104,4103,14,14,14,25,公共区长度:S = MAX(fi-f1+size(Ni), i 从1到m这时候的局部区长度len = a + S,分配到数组 A, A1,2 A2,3 为等价元等价片中其他元的地址为ADDR( NI )=a + (fI fA), 当前a=4,a,等价片内部是一个整体,不论片中哪一个元作为公共元出现,内部相对队形不变,但是遇到不同的元,在公共块中等价片的位置要变化
17、,若先遇到I,那么A1,1 就要跑到A1之前,可能出现冒头,这是错误.使用EQ链和OFFSET(NI)可以计算出ADDR(NI),因此各NI的地址可填,剩下2个问题:1,D分到哪里?2,公共区长度如何算?,D应该分配到公共区之后,故ADDR(D) = a + S = 4 + 100 = 104,公用区冒头一例:,A1,2,A10,1,A9,1,A8,1,A1,1,A2,2,A2,3,A10,10,D,冒头!,24,公用区地址分配算法,a: 地址计数器; len: 长度计数器; d 公用区编号FOR COMLIST 中每个 FT 不为 null 的项 i , DOBEGIN a := 0; le
18、n := 0; d := i + 127; N := FT i ; WHILE N != null DOBEGIN IF DA N != 0 THEN IF DA N != d OR ADDR N != a THEN ERROR (冲突) ELSE IF EQ N = null THEN DA N := d; ADDR N := a ELSE BEGIN N1 := N; f := OFFSET N ;,REPEAT a1 := a + ( OFFSET N1 - f); IF a1 0 THEN ERROR (冒头); IF DA N1 != 0 AND ( DA N1 != d OR AD
19、DR N1 != a1)THEN ERROR (非法等价); ELSE BEGINDA N1 := d; ADDR N1 := a1 ;len := MAX ( len, a1 + size( N1 );N1 := EQ ( N1 ) ;ENDUNTIL N1 = NEND;a := a + size N ;len := MAX ( len, a );,REPEATN := CMP N ;END OF WHILE;LENGTH i := MAX ( LENGTH i , len );FT i := null; LT i := null ;END OF FOR LOOP;,2,局部区地址分配,例
20、子: DIMENSION A(10,10), B(4) REAL Y EQUIVALANCE(X, A2,3 ), REAL Z,Y,Z,a,假定 f2 最小,N2 的地址为 a其他, ADDR(Ni)=a + (fi f2), 特别地, 对X有 f1 = 0, f2 = -21 ADDR(N1)=a + (f1 f2)= a + 21,N1 X f1N2 A f2Nm fm,Y 已经分配,Xf1=0,f2 = -21,算法:1, 环内求 Min offset(Ni) = f;2, 环内每个元 Ni 做 DA 栏为现行程序区号ADDR栏 = a + offset(Ni) - f局部区长度:le
21、n = MAX(len, (offset(Ni)-f) + size(Ni);3, 处理完本等价环后地址移动: a = a + len为改等价环后地变量指出分配地址,3,临时变量的地址分配,临时变量的作用域不相交,则可以公用一个存储单元,大部分临时变量名用来存放表达式的中间结果,这类变量名有一个特点,它们均只被定值一次,被引用一次.它们的作用域是层次嵌套的 - 栈,例子:对赋值语句 X := A * B C * D + E * F产生的临时变量的处理,四元式,地址,临时变量名,( 1 ) * A B T1,T1,a,( 2 ) * C D T2,T2,a+1,( 3 ) - T1 T2 T3,
22、( 4 ) * E F T4,( 5 ) + T3 T4 T5,( 6 ) := T5 X,T3,T4,T5,a,a+1,a,T1, T2 不再使用它们的存储单元可以回收,T3, T4 不再使用它们的存储单元可以回收,最后只是用了一个单元 : a,“代真”后的四元式序列,(1) * A B $a,四元式,K(初始值为 a),(2) * C D $(a+1),(3) - $a $(a+1) $a,(4) * E F $(a+1),(5) + $a $(a+1) $a,(6) := $a x,a + 1,a + 2,a + 1,a + 2,a + 1,a,a, a + 1 存储单元不再使用可以回收
23、,a, a + 1 存储单元不再使用可以回收,最后只使用了单元 a,8.2 动态存储分配 - 简单栈式,特点: 1, 没有分程序结构;2, 过程定义不允许嵌套;3, 允许过程递归调用;4, 允许过程含有可变数组;(但不允许全局可变数组),主程序全局数据区,Q 的活动记录,Q 的数组区,R 的活动记录,R 的数组区,调用方向,C 语言程序的存储组织,主程序调用 Q,分配数组区完成,主程序调用 R,分配数组区完成,最终情形,8.2.1 C 过程的活动记录,210,C 的过程调用，过程进入，数组空间分配和过程返回,过程调用的四元式序列par T1par T2.par Tncall P, n,(i +
24、 3)TOP := Ti 或者(i + 3)TOP := addr(Ti)其中:x SP 表示变址访问地址 x + SP,36,call P, n,1 TOP := SP (保护现行SP),3 TOP := n (传送参数个数),JSR P (转子指令，转向 P 的第一条指令),SP := TOP + 1 (定义新SP),1SP:= 返回地址 (保护返回地址),TOP := TOP + L (定义新TOP),1，计算各维上下限2，调用数组空间分配子程序,37,return (E),T 送寄存器（等待调用段取走）,TOP := SP 1SP := 0SPX := 2TOPUJ 0X,另:过程通过
25、 end 自动返回的方法：如果过程是函数过程，则按同样的办法传送结果值，否则直接执行上述返回指令,38,8.3 嵌套过程语言的栈式实现,重点：嵌套层次的概念和处理方法,39,引入 DISPLAY 表以后的活动纪录,40,活动纪录表： AR,.引用 Py, Qx.,call R,call Q,( Py,Qx 为参数 ),SP1.2,41,建立 DISPLAY 的方法,DISPLAY 的结构,1，表项和层次有关，底层若从 0 层开始，表项 = 层次+12，与调用层有关,42,DISPLAY 的建立方法（从Q2 调用 R）,进入新过程时1，应把它的外层的 D 表地址作为连接数据传过来，若进R, 应把
26、d SP1.2 传到 ARR 的全局 D 表;2,进入 R 时，根据 SP1.2 从 Q 的活动纪录中截取 d SP1.2 (d + lR) SP1.2 (l 为层数)， 再添加进入 R 时新建立的 SP2,43,现行过程中引用了某一外层过程（层数为k）获得 X 值的方法,LD R1, ( d + k ) SP (获得第 k 层过程的最新活动纪录)LD R2, X R1 (把 X 的值传送到 R2),当过程 P1 调用过程 P2 而进入了 P2 后，P2 建立自己的DISPLAY 的方法,1，若 P2 是一个真实过程，2 种情形,P1,P2,CALL P2,P0,P2,P1,CALL P2,做
27、法：只需要把 P1 的 DISPLAY 地址作为连接数据之一传给 P2, WHY?,44,45,( i + 4) TOP := Ti; 或者( i + 4) TOP := ADDR( Ti ),call P, n,1 TOP := SP;3 TOP := SP + d;4 top := n;JSR P,定义新的 SP , TOP； 保护返回地址,46,按第三项连接数据所提供的全局 DISPLAY 的地址，自低向上抄录 l 个单元的内容（l 为P 的层数），再添上新的 SP 以形成新的DISPLAY ( l + 1 个单元),TOP := SP -1 ;SP := 0 SP;X := 2 TOP
28、;UJ 0 X;,47,8.3.3 参数传递,如果实参是一个简单变量，数组元素或者临时变量，则根据传地址或者传值对 par T 的解释是正确的；如果实参为数组，过程或者标号，par T 的作用都是传地址，而且在传地址之前要做别的工作。,1, par T, T 为数组若要求运行时对形-实数组的维数一致性和体积相容性进行动态检查，则应传送 T 的内情向量；否则，只传送 T 的首地址。,2, par T, T 为过程例子：假定 过程 P 把过程 T 作为实参传递给过程 Q，随后，Q 又通过引用相应的形式参数调用 T,48,调用关系,Call Z,Call Q(T),49,P 和 T 仅有的两种关系,
29、1, P 的 DISPLAY 正好就是 T 的直接外层的 DISPLAY :,2, P 的 DISPLAY 包含了 T 的直接外层的 DISPLAY :,不论何种情况，假定 T 的层数为 l，那么，T 的 DISPLAY 是由 P 的 DISPLAY 的前 l 个单元的内容和 SP 的现行值组成,50,目的：使得过程 T 工作时能知道 P 的 DISPLAY,方法：在 P 把 T 作为实参传送给 Q 的时候，把 P 自身的DISPLAY 地址也传过去,过程 P 中的 par T的作用：建立下面两个相继临时单元的值B1 : 过程 T 的入口地址；B2 : 现行的 DISPLAY 地址 （Dp）然
30、后，把第一临时单元 B1 的地址传送给 Q (执行 (i + 4) TOP := ADDR(B1) 假定后来执行到 CALL Z, m Z 为形式参数 ，含有B1的地址。,B1,B2,过程 T,T,Q,P,B2作为全局DISPLAY传给T,51,3，par T, T 为标号, 形如：,GOTO z;,CALL Q(T)T:,52,假定标号 T 是在过程 P0 中定义的（P0是P自身或某一外层），P 中 par T ( T 为标号)的功能为建立如下 2 个临时单元：,第一临时单元B1: 标号 T 的地址；第二临时单元B2：P0 的活动记录地址,B1 Q（B1地址给Q）,执行到 GOTO z (
31、z 已经含有 B1 地址),53,逐级恢复SP 和 TOP 到 SP 指向 P0 的活动纪录（栈不动，SP 动）,B2 := ( l + d ) SP （取得 P0 的活动纪录地址）其中，l 为 P0 的层数，d 为 DISPLAY 的相对地址,54,8.4 ALGOL 的实现,ALGOL 的特点：1，分程序 分程序的嵌套性2，参数换名,分程序和过程的区别和联系：相同：都可以引用外层变量不同：过程有名字，都有变量说明，流程和书面写法不相同，可以单独运行分程序没有名字，流程和书面写法相同，不能单独运行,55,8.4.1 分程序结构,一种可能的处理方法,把分程序看作“无参数过程”，在哪里定义就在哪
32、里被调用,引入的 问题,1，每次进入一个分程序都要建立连接数据和 DISPLAY；2，分程序返回时必须从各层依次退出（一次退出可以获得目标层活动纪录地址，但是无法知道目标层的 TOP，因为 TOP 是共有的）,56,解决办法,1，TOP 私有化，每一个过程和每一个分程序都保有一个 TOP；2，分程序不作为无参数过程调用处理,例子 新的活动纪录,Procedure A ( m, n ); integer m, n ;B1: begin real z ; array B m : n ;B2: begin real d, e; L3: end;B4: begin array C 1 : m ;B5:
33、 begin real e;L6:end;end;L8: end;,57,Procedure A 的活动纪录,KD6543210,58,8.4.2 分程序的进入和退出 以 procedure 为例,到达标号 B1 处,进入分程序 B1,数组 B 分配之后,进入分程序 B2,进入分程序 B4 分配数组 C 之后,进入分程序 B5,59,8.4.3 过程调用，进入和返回,一个例子：过程 Q 中的某一个分程序 B 里调用了过程 P,60,语句 Call P, m 的执行过程:,B 的 TOP 送变址器 X : X := B.TOP,建立未来的 P 的连接数据和实现转子 : 2 X := SP 4 X
34、 := SP + d 5 X := X 6 X := mJSR P,进入 P 后立即执行：SP := X +10 SP := X + L （L 是过程 P 的活动纪录长度）2 SP := 返回地址,61,P 出口的动作： X := 2 SP SP := 1 SP UJ 0 X ,建立 P 的 DISPLAY 表的方法：根据 3 SP (即：4 X ) 中所指的全局 D 表 ( Q 的 DISPLAY)从 Q 的 AR 中取出 D 表, 再加上过程 P 的层数 lP ，送到形参单元之上，形成本过程（P）的DISPLAY.,62,8.4.4 参数子程序,ALGOL 的换名形式参数对应的实参的处理方
35、法：子程序，俗称thunk,处理办法：1，若实参是简单变量或者下标变量，thunk 直接计算该变量的地址；2，若实参是一个其他表达式， thunk 的任务是计算此表达式的值并把它存放在某个确定的工作单元中，然后回送此单元的地址。,63,例子,过程 P 中的某个分程序 B 内通过语句 Q ( E ) 调用了过程 Q ,此处实参 E 是一个表达式。过程 Q 中的某一个分程序 B1 对 Q 的形式参数 Z 的引用意味着对 E 的 thunk 调用,64,注意：1，B1 对 Q 的形式参数 Z 的引用意味着对 E 的 thunk 的调用，这个 thunk 必须工作在 P 的环境中；2，如果参数表达式
36、E 中含有函数调用，会改写栈中 B.TOP 所指位置以上的部分，所以必须预先把 B 的 TOP 值暂时改称指向栈的最高位置（B1.TOP），以保护他们（实际上就是 Q 的数据区）不被破坏 。（具体解释见后面的图示）,65,4，JSR Z /* 间接转子，进入 thunk */,1，2 X := 返回地址；,进入 thunk 后的执行,2，3 X := B.TOP ( thunk 所在的 B )；,3，B.TOP := X +3 ； /*指向现行栈顶的最高位置 */,4，进行 thunk 的工作；,5，X := B.TOP - 3 ；,6，SP := 1 X ； /* 恢复 SP*/,7，B.T
37、OP := 3 X ； /* 恢复 B.TOP */,8，X := 2 X ；,9，UJ 0 X ； /* 返回 Q */,具体的动作 （Z 中含有thunk 的入口地址）,1，X := B1.TOP; /* 现行栈顶地址送变址器 X */,2，1 X := SP; /* 保护 SP */,3，SP := 1 SP /* 把 SP 变成指向调用段 P 的活动纪录 */,栈的活动情况,返回地址,SPQ,B.TOP,解释一下：现行 SP 是 Q 的 SP = SPQ, SPQ + 1 中的内容 1 SPQ 是 P的活动记录地址（老 SP），把它送 SP, 得到SPP,66,参考文献,1，Kenneth C.Louden,冯博琴译，编译原理与实践，机械工业出版社，P267-P296;2,严尉敏，数据结构与算法，清华大学出版社，动态存储管理 部分。3，Randell 和 Russell1964，Algol60基于栈的环境；4，Johnson 和 Ritchie1981, C 编译器活动记录组织和调用序列；5，Fraser 和 Hanson1995，编译时堆结构设计；6，Wilson1992，Cohen1981，垃圾回收。,
