《编译课件第十章》由会员分享,可在线阅读,更多相关《编译课件第十章(73页珍藏版)》请在金锄头文库上搜索。
1、第十章 目标程序运行时的组织,10.1 概述 2 运行环境和存储分配设计分析 10.3 栈式存储组织 10.4 参数传递 10.5 堆式存储组织,10.1 概述-代码生成解决语义gap,高级语言支持的概念 Type value expression Variable procedure Function parameters,目标机支持的概念 bits bytes words Registers Stack address Routine(sub routine),概述,代码生成前如何安排目标机资源 运行时组织的几个问题: 数据表示-如何在目标机中表示每个源语言类型的值 表达式求值-如何组织表
2、达式的计算 存储分配-如何组织不同作用域变量的存储 过程实现-如何以例程实现过程,函数,参数传递,任务:编译程序对目标程序运行时的组织(设计运行环境和分配存储) 如 通常存储区布局可为:,目标代码区 静态数据区 Stack heap,10.2 运行环境和存储分配 设计分析,逻辑阶段:在目标代码生成前,作准备 实质: 关联(Binding) 将源程序的文本 程序运行动作的实现 源文件中的名字N 运行时的存储S 在语义学中,使用术语environment函数表示 env: NS (N到S的映射),决定运行管理复杂程度的因素源语言本身,1.,允许的数据类型的多少,2,语言中允许的数据项是,静态确定,
3、动态确定,3,程序结构,决定名字的作用域的规则和结构,A,段结构,B,过程定义不嵌套,只允许过程递归调用,C,分程序结构,分程序嵌套,过程定义嵌套,4存储类别的多少,Global Static Local dynamic,10.3 目标程序运行时的存储组织,存储分配策略:,简单的栈式分配方案 嵌套过程的栈式分配方案 分程序结构的存储分配方案,AR,简单的栈式分配方案,程序结构特点: 过程定义不嵌套 过程可递归调用 含可变数组; 例: main 全局变量的说明 proc R end R; proc Q end Q; 主程序执行语句 end main,嵌套过程语言的栈式 分配方案,主要特点: (语
4、言)一个过程可以引用包围它的任一外层过程所定义的标识符(如变量,数组或过程等)。 (实现)一个过程可以引用它的任一外层过程的最新活动记录中的某些数据。,关键技术:解决对非局部量的引用(存取)。 设法跟踪每个外层过程的最新活动记录AR的位置。 跟踪办法: 1. 用静态链。 2. 用DISPLAY表。,目标代码解释执行时数据栈的布局(运行栈的存储分配),每个过程的AR有 3个联系单元: SL: 静态链,指向定义该过程的直接外过程 (或主程序)运行时最新数据段的基地址。 DL: 动态链,指向调用该过程前正在运行过 程的数据段基地址。 RA: 返回地址,记录调用该过程时目标程序的断点,即调用过程指令的
5、下一条指令的地址。 局部变量 中间结果,DISPLAY表,每进入一个过程后,在建立它的活动记录的同时建立一张嵌套层次表display。 Display是一个指针数组d,也可以看成是一个小栈。当前激活过程的层次为K,它的Display表含有K+1个单元,依次存放着现行层,直接外层直至最外层(0层)的每一过程的最新活动记录的基地址。 嵌套层次i的过程的局部变量a是由display元素di所指的那个活动记录中存放的。也就是说嵌套层次i1过程中的非局部变量可能在i,i1,0层等每一层过程的最新活动记录的地址。,Procedure p procedure Q procedure R ,用Display表
6、的方案,(1)主程序-(2)P-(3)Q-(4)R,d1 d0,d0,(1),用Display表的方案,主程序-P-Q-R,d2 d1 d0,d1 d0,top,(3),(4),DISPLAY表的维护和建立,DISPLAY表d 运行栈 0 主程活动记录地址 1 R活动记录地址,.,分程序结构 Procedure A(m,n); integer m,n; B1:begin real z; array Bm:n; B2:begin real d, e; L3: 2 end; B4:begin array C1:m; 1 B5:begin real e; L6: 5 4 end; end; L8:e
7、nd;,分程序结构的存储管理,处理分程序结构存储分配方案的一种简单办法是,把分程序看成 “无名无参过 程”.它在哪里定义就在哪里被调用。 原因:每逢进入 一个分程序,就照样建立连接数据和DISPLAY表,这是不必要的。 当从内层分程序向外层转移时,可能同时要结束若干个分程序。,为了解决上述问题,可采取两种措施。第一,对每个过程或分程序都建立有自己的栈顶指示器TOP,代替原来仅有过程的栈顶指示器, 每个TOP的值保存在各自活动记录中。这样,上述的第二个问题便可解决。第二,不把分程序看作“无参过程”,每个分程序享用包围它的那个最近过程的DISPLAY。每个分程序都隶属于某个确定的过程,分程序的层次
8、是相对于它所属的那个过程进行编号的。,:,每个过程被当作是0层分程序。而过程体分程序(假定是一个分程序)当作是它所管辖的第1层分程序。 这样,每个过程的活动记录所含的内容有: 1.过程的TOP值,它指向过程活动记录的栈顶位置。 2.连接数据,共四项: (1)老SP值; (2)返回地址; (3)全局DISPAY地址; (4)调用时的栈顶单元地址,老TOP。,3. 参数个数和形式单元 4. DISPAY表。 5. 过程所辖的各分程序的局部数据单元。 对于每个分程序来说,它们包括: (1)分程序的TOP值。当进入分程序时它含现行栈顶地址,以后,用来定义栈的新高度(分程序的TOP值); (2)分程序的
9、局部变量, 数组内情向量和临时工作单元。,B,Z,B,1,T,O,D I S P L A Y,D I S P L A Y,形式单元,m,n,2,形式单元,m,n,2,连,接,数,据,连接,数,据,A,的,T O P,A,的,T O P,(c),(d),(c ),数组,B,分配之后;,(,d,)进入分程序,B2,2,;,10. 3参数传递,(1)procedure exchangel(i,j:integer); (2) var x:integer; (3) begin; (4) x:=ai; ai:=aj; aj:=x (5) end;,带有非局部变量和形参的PASCAL过程 非局变量ai和aj
10、的值进行交换,i,j为形参(在这里是传值),(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程序,传地址(变量
11、参数) 例如:过程 swap(var x,y:integer); swap(a,b);( a,b为调用时的实参 ) 调用结果a,b的值被改变。 传值(值调用) 特点是对形式参数的任何运算不影响实参的值。例如:过程 swap(x,y:integer); swap(a,b);其结果: a,b调用前的值不改变。,传值的实现,1.形式参数当作过程的局部变量处理,即在被调过程的活动记录中开辟了形参的存储空间,这些存储位置即是我们所说的形式单元(用以存放实参)。 2.调用过程计算实参的值,并将其放在对应形式单元开辟的空间中。 3.被调用过程执行时,就像使用局部变量一样使用这些形式单元。,procedure
12、 swap( x,y:integer); var temp:integer; begin temp:=x; x:=y; y:=temp end; 调用swap(a,b) 过程将不会影响a和b的值。 其结果等价于执行下列运算: x :=a; y :=b; temp :=x; x :=y; y :=temp,传地址的实现,(call- by- reference )(call-by-address)(call-by-location) 把实在参数的地址传递给相应的形参,即调用过程把一个指向实参的存储地址的指针传递给被调用过程相应的形参: 1实在参数是一个名字,或具有左值的表达式-传递左值 2实在参
13、数是无左值的表达式-计算值,放入一存储单元,传此存储单元地址 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( (10) 在一个值调用过程中使用指针的C程序 在C程序中无传地址所以用指针实现。,值结果传递,除了未建立真正的别名之外,这个机制得到的结果与地址传递类似: 在过程中复制和使用自变量的值,然后当过程退出时,再将参数的最终值复制回自变量的地址
14、。因此,这个方法有时也被称为复制进,复制出,或复制存储。 值结果传递与地址传递的唯一区别在于别名的表现不同。例如,在以下的代码中(C语法): void p (int x, int y) +x; +y; main() int a=1; p(a,a); return 0; 在调用p之后,若使用了地址传递,则a的值为3;若使用了值结果传递,则a的值为2。,名字传递,这是传递机制中最复杂的参数了。由于名字传递的思想是直到在被调用的程序真正使用了自变量(作为一个参数)之后才对这个自变量赋值,所以它还称作延尽赋值(delayed evaluation)。因此,自变量的名称或是它在调用点上的结构表示取代了它对应的参数的名字。例如在代码 void p (int x) +x; 中,若做了一个如p(ai)的调用时,其结果是计算+(ai)。因此,若在p中使用x之前改变i,那么它的结果就与在地址传递或在值结果传递中的不同,int i; int a 10; void p (int x) +i