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

第10章 目标程序运行时的组织 教学要求：本章介绍目标程序运行时的存储组织方式，包括静态存储分配和动态存储分配。 要求掌握各种存储组织形式的基本方法。 教学重点：静态分配策略和动态分配策略的基本思想，嵌套过程语言栈式分配，活动、运行时栈的组织。 10.1 概述 从逻辑上看，代码生成前，编译程序必须进行目标程序运行环境的和数据空间的分配 数据空间包括：用户定义的各种类型的数据对象（变量和常量）所需的存储空间，作为保留中间结果和传递参数的临时工作单元，调用过程时所需的连接单元，组织输入/输出所需的缓冲区。 存储管理复杂度取决于源语言本身，具体包括： 允许的数据类型的多少? 语言中允许的数据项是: 静态确定?动态确定? 程序决定名字的作用域的规则和结构 段结构? 过程定义不嵌套?只允许过程递归调用? 分程序结构: 分程序嵌套?过程定义嵌套? 1、存储组织：编译程序对目标程序运行时的组织（运行环境和分配存储）。如通常存储区布局可为： 目标代码区用以存放目标代码，这是固定长度的，即编译时能确定的。 静态数据区用以存放编译时能确定所占用空间的数据。 堆/栈用于存放可变数据以及管理过程活动的控制信息。 三种数据区对应着下述三种不同的分配策略 2、存储分配策略： （1）静态存储分配——在编译时能确定目标程序运行中所需的全部数据空间的大小，编译时安排好目标程序运行时的全部数据空间，确定每个数据对象的存储位置。 注：1、程序结构特点：不允许递归调用，而且不含有可变数组。（如FORTRAN语言）。 2、基本策略:在编译时，根据各类数据所需的存储空间大小以及存储方式规定，在符号表中建立“名字-地址”对应关系，然后根据这些对应关系进行变量名的地址分配。 （2）动态存储分配——在运行阶段动态地为源程序中的量分配存储空间。（栈式、堆式） 注：1）若某程序设计语言允许过程递归调用，而且允许使用可变数组，那么在编译时就不可能完全为其数据项目分配存储单元，必须采取动态存储分配策略。 2)动态分配数据单元时一般使用栈，即栈式存储管理。 栈式: 简单的栈式分配方案 嵌套过程的栈式分配方案 分程序结构的存储分配方案 3、过程活动：一个过程的活动指的是该过程的一次执行。 4、活动记录（AR）：一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区（块）叫做一个活动记录。此记录含有连接数据、形式单元、局部变量、局部数组的内情向量和临时工作单元等。 每个过程的活动记录内容(非嵌套语言) 对任何局部变量X的引用可表示为变址访问: dx[SP] dx: 变量X相对于活动记录起点的地址，在编译时可确定。 SP 0 1 2 TOP 每个过程的活动记录内容(嵌套语言) 连接数据 返回地址 动态链：指向调用该过程的最新活动记录地址的指针。 静态链：指向直接外层最新活动记录地址的指针，用来访问非局部数据。 SP 0 1 2 TOP 每个过程的活动记录内容 形式单元：存放相应的实参的地址或值。 局部数据区：局部变量、内情向量、临时工作单元（如存放对表达式求值的结果）。 SP 0 1 2 TOP   SP TOP 连接数据(控制信息) SP为当前活动记录的起始位置。 TOP为栈顶单元。分别放在两个寄存器中。 访问信息 活动记录的填写 1、 call P 被翻译成: 1[TOP]:=SP (保护现行SP) JSR P (转子指令) 老SP 2、转进过程P后，首先应执行下述指令: SP:=TOP+1 (定义新的SP) 1[SP]:=返回地址 (保护返回地址) TOP:=TOP+L (新TOP) L：过程P的活动记录所需单元数， 在编译时可确定。 返回地址 TOP SP 3、 过程返回时，应执行下列指令: TOP:=SP-1 (恢复调用前TOP) X:=2[TOP] (把返回地址取到X中) SP:=0[SP] (恢复调用前SP) UJ X (按X返回) TOP SP SP TOP 10.2 栈式存储分配的实现 一、简单的栈式存储分配的实现 程序结构特点：没有分程序结构，过程定义不嵌套，过程可递归调用。 简单栈式分配方案：把存储区组织成一个栈，运行时每进入一个过程，就把它的活动记录压入栈，形成过程工作时的临时数据区，该过程结束时取消该数据区。 例: Main( ) { Main中的数据说明 } proc R( ) { R中的数据说明 } … proc Q( ) { Q中的数据说明 } 主程序→过程Q →过程R Q的活动记录 TOP R的活动记录 SP R的数组区 R的活动记录 Q的活动记录 主程序全局 数据区 分配了数组区之后的运行栈 TOP SP 二、嵌套过程语言的栈式分配的实现 1、程序结构特点：语言的定义允许嵌套，一个过程可以引用包围它的任一外层过程所定义的标识符（如变量，数组或过程等）（如PASCAL语言） 。 如何才能引用外层数据？ 2、关键：设法跟踪每个外层过程的最新活动记录AR的位置。 跟踪办法： （1） 用静态链。 （2） 用DISPLAY表。 PASCAL PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。 一个PASCAL过程： 过程头； 说明段（由一系列的说明语句组成）； begin 执行体（由一系列的执行语句组成）； end 作用域：一个名字能被使用的区域范围称作这个名字的作用域。 允许同一个标识符在不同的过程中代表不同的名字。 名字作用域规则--"最近嵌套原则" 一个在子程序B1中说明的名字X只在B1中有效（局部于B1）； 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。 program main var A, B : real; … procedure P1 var B:boolean; … begin … end procedure P2 var A:integer; … begin … end begin … end A(real) B(real) B(bool) A(integr) 非局部名字的访问的实现 主程序的层次为0；在i层中定义的过程，其层次为i+1; 过程运行时，必须知道其所有外层过程的当前活动记录的起始地址。 （1） 用静态链 在过程活动记录中增设静态链，指向包含该过程的直接外层过程的最新活动记录的起始位置。见P223-224 main p1 p2 p3 p4 main 过 程 定 义 的 嵌 套 执 行 顺 序 →p2 →p4 →p3 →p3 main活动记录 P3活动记录 存取链(静态链) 控制链(动态链) P3活动记录 存取链(静态链) 控制链(动态链) P4活动记录 存取链(静态链) 控制链(动态链) P2活动记录 存取链(静态链) 控制链(动态链) 2、用Display表 Display表---嵌套层次显示表 当前激活过程的层次为K，它的Display表含有K+1个单元，依次存放着现行层，直接外层…直至最外层的每一过程的最新活动记录的基地址。 说明：1、由于过程的层数可以静态确定，因此每个过程的Display表的体积在编译时即可以确定。 2、某过程p是在层次为i的过程q内定义的，并且q是包围p的直接外层，那么p的过程层数为i+1。 program P; var x,y: integer; ... procedure P1; var i,j:integer; ... procedure P11(a,b:integer); ... begin ... end; begin ... call P11(i,j); ... end; procedure P2; var s,t:integer; ... procedure P21; begin ... end; begin ... call P1 ... end; begin ... call P2; ... end. 主程序P 过程 P2 过程 P1 过程 P11 Display 用Display表的方案 (1)主程序--->(2)P--->(3)Q--->(4)R 用Display表的方案 (1)主程序--->(2)P--->(3)Q--->(4)R DISPLAY表的维护和建立 为便于组织存储区，将display作为活动记录的一部分，其相对地址在编译时是完全可以确定的。 假设过程P1可调用P2，为了能在P2中建立P2的display，在P1调用P2时设法把P1的display地址作为连接数据之一（全局display地址）传送给P2，因此连接数据包括： 老SP值（动态链） 返回地址 全局display地址 …… d DISPLAY 4 形式单元 3 参数个数 2 全局DISPLAY地址 1 返回地址 0 老SP 当过程的层次为n，它的display为n+1个值。 一个过程被调用时，从调用过程的DISPLAY表中自下向上抄录n个SP值，再加上本层的SP值。 10.3 堆式存储分配 堆：通常是一片连续的足够大的存储区，当需要时，就从堆中分配一小块存储区；用完就及时退还给堆。 注：在高级语言中有些数据存储空间的请求与释放不再遵循后进先出的原则，而且是全局性的。为此，需要让运行程序持有一块专用的全局存储空间来满足这些数据的存储要求。这种存储空间就是堆。 10.4 参数传递 (1)procedure exchangel(i,j:integer); (2) var x:integer; (3) begin; (4) x:=a[i]; a[i]:=a[j]; a[j]:=x (5) end; 带有非局部变量和形参的PASCAL过程 非局变量a[i]和a[j]的值进行交换，i,j为形参 传值的实现 1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的形式单元（用以存放实参）。 2.调用过程计算实参的值，并将其放在对应形式单元开辟的空间中。 3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。 (1)program reference(input,output); (2)var a,b:integer; (3)procedure swap({var} x,y:integer); (4) var temp:integer; (5) begin (6) temp:=x; (7) x:=y; (8) y:=temp (9) end; (10)begin (11) a:=1; b:=2; (12) swap(a,b); (13) writeln(‘a=‘,a);writeln(‘b=‘,b) (14)end. 带有过程swap的PASCAL程序 传地址的实现 把实在参数的地址传递给相应的形参，即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参： 1.实在参数是一个名字，或具有左值的表达式----传递左值 2.实在参数是无左值的表达式----计算值，放入一存储单元，传此存储单元地址 3.目标代码中，被调用过程对形参的引用变成对传递给被调用过程的指针的间接引用 (1)swap(x,y) (2)int *x,*y; (3){ int temp; (4)temp=*x; *x=*y; *y=temp; (5) } (6)main( ) (7){ int a=1,b=2; (8) swap(&a,&b); (9) printf(“a is now %d,b is now %d\n”,a,b);} 在一个值调用过程中使用指针的C程序, 在C程序中无传地址所以用指针实现。 (1)program param(input,output); (2)procedure b(function h(n:integer):integer); (3) begin writeln(h(2)) end{b}; (4)procedure c; (5) var m:integer; (6) function f(n:integer):integr; (7) begin f:=m+n end{f}; (8)begin m := 0; b(f) end {c}; (9)begin (10) c (11)end 嵌套过程作为参数传递 作业 (1)对以下的Pascal程序画出过程C第二次被调用时的运行栈，控制链和存取链. (2)如果把存取链改成DISPLAY，重新做(1) program env; procedure A; var x :integer; procedure B; procedure C; begin x:=2; B end; (c过程) begin C end; (B过程) begin B end ; (A过程) begin A end; (main)