1、运行时的存储组织及管理运行时的存储组织及管理2022-12-17编译技术编译技术2运行时的存储组织及管理运行时的存储组织及管理概述概述存储组织存储组织运行时的存储分配策略运行时的存储分配策略静态存储分配静态存储分配动态存储分配动态存储分配对非局部名字的访问对非局部名字的访问参数传递参数传递2022-12-17编译技术编译技术3有关源程序中的一些问题有关源程序中的一些问题问题的提出：如何构造运行程序的策略和方法问题的提出：如何构造运行程序的策略和方法过程过程活动树活动树控制栈控制栈说明的作用域说明的作用域名字的绑定名字的绑定2022-12-17编译技术编译技术4名字与存储的绑定名字与存储的绑定名
2、字名字存储单元存储单元值值存储分配存储分配程序运行程序运行环境环境状态状态l-valuer-value静态概念静态概念 动态对应动态对应过程定义过程定义 过程活动过程活动名字说明名字说明 名字的绑定名字的绑定说明的作用域说明的作用域 活动的生存期活动的生存期2022-12-17编译技术编译技术5存储组织存储组织运行时刻内存的划分：假定编译器从操作系统得到运行时刻内存的划分：假定编译器从操作系统得到一块存储区，运行时的存储空间要划分成块一块存储区，运行时的存储空间要划分成块:生成的目标代码生成的目标代码;数据对象数据对象;记录过程活动的控制栈记录过程活动的控制栈对应的数据结构对应的数据结构目标代
3、码目标代码静态数据静态数据栈栈堆堆返回值返回值实在参数实在参数控制链控制链(动态链动态链)访问链访问链(静态链静态链)保存机器状态保存机器状态局部数据局部数据临时变量临时变量2022-12-17编译技术编译技术6运行时刻存储分配策略运行时刻存储分配策略分配策略是：分配策略是：静态分配；静态分配；栈式分配，或称栈式动态分配；栈式分配，或称栈式动态分配；堆式分配，或称堆式动态分配。堆式分配，或称堆式动态分配。采用哪种分配策略是由源语言的语义决定的。采用哪种分配策略是由源语言的语义决定的。2022-12-17编译技术编译技术7堆式存储分配堆式存储分配栈式存储分配策略在下列情况下不能使用：栈式存储分配
4、策略在下列情况下不能使用：活动结束时必须保持局部名字的值活动结束时必须保持局部名字的值被调用者的活动比调用者的活动的生存期长。被调用者的活动比调用者的活动的生存期长。堆式存储器的策略：（堆管理器管理堆空间）堆式存储器的策略：（堆管理器管理堆空间）把连续存储区域分成块，当活动记录或其他对象需要把连续存储区域分成块，当活动记录或其他对象需要时就分配。时就分配。块的释放可以按任意次序进行，所以经过一段时间块的释放可以按任意次序进行，所以经过一段时间后，堆可能包含交错的正在使用的和已经释放的区域后，堆可能包含交错的正在使用的和已经释放的区域2022-12-17编译技术编译技术8堆管理器的效率问题堆管理
5、器的效率问题堆管理的效率问题是数据结构理论中的特殊问题堆管理的效率问题是数据结构理论中的特殊问题对每个感兴趣的活动记录的大小，保存一个相应大小对每个感兴趣的活动记录的大小，保存一个相应大小的空闲块的链表的空闲块的链表可能的话，为大小为可能的话，为大小为s的请求分配一个大小为的请求分配一个大小为s的块，的块，其中其中s是大小等于是大小等于s的最小块。当该块最终被释放后，的最小块。当该块最终被释放后，将其链回原来的空闲块链表将其链回原来的空闲块链表对于大块存储空间，使用堆管理器管理。对于大块存储空间，使用堆管理器管理。其具体管理方法可以参考操作系统中堆内存的管理其具体管理方法可以参考操作系统中堆内
6、存的管理方法。方法。2022-12-17编译技术编译技术9栈式存储分配栈式存储分配基于控制栈的原理：基于控制栈的原理：存储空间被组织成栈，活动记录的推入和弹出分别对存储空间被组织成栈，活动记录的推入和弹出分别对应于活动的开始和结束。应于活动的开始和结束。与静态分配不同的是，在每次活动中把与静态分配不同的是，在每次活动中把和和绑定，在活动结束时，活动记录从栈绑定，在活动结束时，活动记录从栈中弹出，因而局部名字的存储空间也随之消失。中弹出，因而局部名字的存储空间也随之消失。当控制流通过图当控制流通过图6.3的活动树时活动记录被推人或弹的活动树时活动记录被推人或弹出运行时刻的栈中的情况，设寄存器出运
7、行时刻的栈中的情况，设寄存器top标记栈顶。标记栈顶。sSa:arraytoprri:integertoptopq(1,9)q(1,9)i:integertopp(1,9)p(1,9)i:integertoptopq(1,3)q(1,3)i:integertop2022-12-17编译技术编译技术11栈式存储分配栈式存储分配确定活动记录中局部数据的地址：确定活动记录中局部数据的地址：假设假设top-sp标记一个活动记录的开始的位置，标记一个活动记录的开始的位置，dx表示表示x的地址相对于的地址相对于top-sp的偏移量。那么，的偏移量。那么，x在过程的目标在过程的目标代码中的地址可写成代码中的
8、地址可写成dx(top-sp)在运行时刻，当把在运行时刻，当把x的活动记录筑于栈顶时，寄存器的活动记录筑于栈顶时，寄存器top-sp被赋于实际的地址，被赋于实际的地址，top-sp可以是一个寄存可以是一个寄存器。器。2022-12-17编译技术编译技术12调用序列和返回序列调用序列和返回序列通过在目标代码中生成调用序通过在目标代码中生成调用序列和返回序列实现过程的调列和返回序列实现过程的调用。激活一个过程的活动是执用。激活一个过程的活动是执行过程语句的结果。行过程语句的结果。过程语句过程语句p(e1,e2,en)的目的目标代码标代码(调用序列调用序列)完成任务：完成任务：调用者对实在参数求值，
9、调用者对实在参数求值，并把它们传送给被调用过并把它们传送给被调用过程的活动记录的参数域。程的活动记录的参数域。调用者在被调用者的活动调用者在被调用者的活动记录中存放返回地址和老记录中存放返回地址和老top-sp之值。之后调用者之值。之后调用者把把top一一sp之值增加到新的之值增加到新的栈顶的活动记录的位置。栈顶的活动记录的位置。被调用者存放寄存器值和被调用者存放寄存器值和其它状态信息。其它状态信息。被调用者初始化其局部数被调用者初始化其局部数据并开始执行。据并开始执行。参数和返回值参数和返回值链和保存的状态链和保存的状态临时变量和局部数据临时变量和局部数据参数和返回值参数和返回值临时变量和局
10、部数据临时变量和局部数据控制链控制链链和保存的状态链和保存的状态控制链控制链top_sptop_sp调调用用者者的的活活动动记记录录被被调调用用者者的的活活动动记记录录调调用用者者的的任任务务被调用被调用者的任者的任务务2022-12-17编译技术编译技术13调用序列和返回序列调用序列和返回序列返回序列，返回序列，return目标代码完成的任务是：目标代码完成的任务是：被调用者在自己的活动记录的返回值域中放一个返回被调用者在自己的活动记录的返回值域中放一个返回值。值。利用状态域中的信息，被调用者恢复利用状态域中的信息，被调用者恢复top-sp和其它寄和其它寄存器，并且按返回地址转移到调用者的代
11、码之中。存器，并且按返回地址转移到调用者的代码之中。调用者复制返回值到自己的活动记录中。调用者复制返回值到自己的活动记录中。2022-12-17编译技术编译技术14可变长度的数据可变长度的数据源程序的例子源程序的例子 PROCEDURE exam(l,m,n:integer);VAR a:array 1.l of real;b:array 1.m of real;c:array 1.n of real;BEGIN END;编译时，不知编译时，不知 a,b,c的大小，仅对每个数组设置一个指针。的大小，仅对每个数组设置一个指针。可变长度的数据可变长度的数据Control linkabcTop-sp
12、topArray aArray bArray ctopP的活动记录P的动态数组参数传递参数传递2022-12-17编译技术编译技术17参数传递参数传递说明的作用域说明的作用域如果一个说明的作用域是在一个过程里，那么这个过程里出现如果一个说明的作用域是在一个过程里，那么这个过程里出现的该说明中的名字都是局部于本过程的；的该说明中的名字都是局部于本过程的；除上述之外的名称是非局部的。除上述之外的名称是非局部的。参数传递方式：过程的形式参数和实在参数的对应方式。参数传递方式：过程的形式参数和实在参数的对应方式。形式参数和实在参数的形式参数和实在参数的“左值左值”和和“右值右值”之间的对应关系之间的对
13、应关系划分参数传递方式：划分参数传递方式：传值调用传值调用引用调用（传地址调用）引用调用（传地址调用）复制复制-恢复调用恢复调用传名调用传名调用2022-12-17编译技术编译技术18参数传递参数传递传值调用传值调用传值调用：计算实参，并把它的右值传值调用：计算实参，并把它的右值传给被调用过程传给被调用过程把形参当作局部名字看待，形参的存把形参当作局部名字看待，形参的存储单元在被调用过程的活动记录中储单元在被调用过程的活动记录中调用者计算实参，并把其右值放入形调用者计算实参，并把其右值放入形参的存储单元中参的存储单元中传值调用的显著特征是对形参的运算传值调用的显著特征是对形参的运算不影响调用者
14、活动记录中的值不影响调用者活动记录中的值打印结果打印结果a is 1,b is 2swap(x,y)int x,y int temp;temp=x;x=y;y=temp;main()int a=1,b=2;swap(a,b);printf(“a is%d,b is%d”,a,b);2022-12-17编译技术编译技术19参数传递参数传递引用调用引用调用引用调用：传递时，调用过程把实参引用调用：传递时，调用过程把实参存储单元的地址传递给被调用过程存储单元的地址传递给被调用过程如果实参是有左值的名字或表达式，如果实参是有左值的名字或表达式，则传递这个左值本身；则传递这个左值本身；如果实参是表达式，
15、没有左值，则计如果实参是表达式，没有左值，则计算该表达式的值并存入新的存储单算该表达式的值并存入新的存储单元，然后传递这个单元的地址元，然后传递这个单元的地址打印结果打印结果a is 2,b is 1swap(x,y)int x,y int temp;temp=x;x=y;y=temp;main()int a=1,b=2;swap(a,b);printf(“a is%d,b is%d”,a,b);2022-12-17编译技术编译技术20参数传递参数传递复制复制-恢复恢复传值调用和引用调用的混合传值调用和引用调用的混合在控制流进入被调用过程之前计算实在控制流进入被调用过程之前计算实参，实参的右值
16、像传值调用那样传递参，实参的右值像传值调用那样传递给被调用过程，此外如果实参有左值给被调用过程，此外如果实参有左值的话，在调用之前确定它的左值的话，在调用之前确定它的左值当控制返回时，将形参的当前右值复当控制返回时，将形参的当前右值复制回实参的左值，该左值是上述调用制回实参的左值，该左值是上述调用前计算的左值。前计算的左值。打印结果打印结果a is 2,b is 1swap(x,y)int x,y int temp;temp=x;x=y;y=temp;main()int a=1,b=2;swap(a,b);printf(“a is%d,b is%d”,a,b);2022-12-17编译技术编译
17、技术21参数传递参数传递传名调用传名调用传名调用的用法类似于宏传名调用的用法类似于宏过程被看做宏，也就是说，在过程被看做宏，也就是说，在调用过程中将调用替换为被调调用过程中将调用替换为被调用过程的过程体，但要把任何用过程的过程体，但要把任何一个出现的形式参数都文字的一个出现的形式参数都文字的替换为相应的实参替换为相应的实参被调用过程中局部名字要保持被调用过程中局部名字要保持与调用过程中的名字不同与调用过程中的名字不同打印结果打印结果a is 2,b is 1swap(x,y)int x,y int temp;temp=x;x=y;y=temp;main()int a=1,b=2;swap(a,
18、b);printf(“a is%d,b is%d”,a,b);void Q(int x)int i=1;x=x+2;i=2;x=x+2;void main()int i;int B3;B1=1;B2=2;i=1;Q(Bi);试问：若参数传递方式分别采取试问：若参数传递方式分别采取(1)传值调用，传值调用，(2)引用调引用调用，用，(3)复制复制-恢复调用，恢复调用，(4)传名调用时，程序执行后传名调用时，程序执行后输出输出B1和和B2的值分别是什么？请简要写出计算过的值分别是什么？请简要写出计算过程。程。采用传值调用时，将实在参数的值传递给形式参数，而后在函数采用传值调用时，将实在参数的值传递
19、给形式参数，而后在函数调用过程中，操作的是形式参数，形式参数的值发生改变，调用过程中，操作的是形式参数，形式参数的值发生改变，而且这些改变不能重新传递给实在参数，所以得到的结果是而且这些改变不能重新传递给实在参数，所以得到的结果是B1=1；B2=2采用引用调用，将实在参数的地址传递给形式参数，此时对形式采用引用调用，将实在参数的地址传递给形式参数，此时对形式参数的操作就相当于对其指向的地址单元进行操作，其操作参数的操作就相当于对其指向的地址单元进行操作，其操作影响了实在参数，所以得到的结果是影响了实在参数，所以得到的结果是B1=5；B2=2采用复制采用复制-恢复调用，首先将实在参数的值传递给形式参数，此恢复调用，首先将实在参数的值传递给形式参数，此时，时，x=1，进行函数调用后，得到，进行函数调用后，得到，x=5，调用返回时，将形，调用返回时，将形式参数的值传递到相应的实在参数的地址中，即式参数的值传递到相应的实在参数的地址中，即x的值传递到的值传递到B1的地址中，所以得到的结果是的地址中，所以得到的结果是B1=5；B2=2采用传名调用，将采用传名调用，将Bi当成整个的一个整体，替换函数调用中的当成整个的一个整体，替换函数调用中的x，得到：，得到：i=1;Bi=Bi+2;i=2;Bi=Bi+2;计算得到，计算得到，B1=3，B2=4 2022-12-17编译技术编译技术23
