编译技术：第07章 运行时存储空间的组织

1、第七章 运行时存储空间的组织运行时环境从从“程序运行程序运行”说起说起 最初由最初由“OSOS”对程序进行控制对程序进行控制 OS OS 为程序分配存储空间为程序分配存储空间 OS OS 将代码复制到所分配的存储空间将代码复制到所分配的存储空间 OS OS 跳转到程序的入口地址（跳转到程序的入口地址（main）Zhou, Erqiang2School of Information and Software Engineering运行时环境函数的活动函数的活动 函数的函数的一次执行一次执行称为函数的一次活动称为函数的一次活动 函数的活动需要函数的活动需要 可执行代码可执行代码 存放所需信息的数据

2、结构存放所需信息的数据结构 活动记录活动记录Zhou, Erqiang3School of Information and Software Engineering活动记录关于活动记录关于活动记录 讨论讨论一个活动记录一个活动记录中的数据安排中的数据安排 程序执行过程中程序执行过程中 所有活动记录所有活动记录的组织方式的组织方式 Zhou, Erqiang4School of Information and Software Engineering活动记录Zhou, Erqiang5School of Information and Software Engineeringintint g()

3、 g() returnreturn 10; 10; intint f() f() returnreturn g(); g(); intint main() main() g(); g(); f(); f(); returnreturn 0; 0; intint g() g() returnreturn 10; 10; intint f(int x) f(int x) if if (x(x = 0)= 0) return return g(); g(); elseelse returnreturn f(x-1); f(x-1); intint main() main() f( f(2 2););

4、 returnreturn 0; 0; 函数栈帧Zhou, Erqiang6School of Information and Software Engineering函数栈帧函数栈帧(stack frame)(stack frame) 函数的每次执行都独立的对应一个函数的每次执行都独立的对应一个栈帧栈帧 当前被执行函数对应的当前被执行函数对应的栈帧栈帧在在栈的顶部栈的顶部 通过通过基址指针基址指针 与与 变量的偏移变量的偏移访问临时变量访问临时变量 void MyFunction()void MyFunction() int a, b, c; int a, b, c; a = 10; a =

5、 10; b = 5; b = 5; c = 2; c = 2;_MyFunction:_MyFunction: push push ebp ; ebp ; 保存保存“基址指针基址指针” ebpebp mov mov ebp, esp ; ebp, esp ; “基址指针基址指针” ebpebp指向栈顶指向栈顶 sub sub esp, 12 ; esp, 12 ; 在栈中为临时变量分配空间在栈中为临时变量分配空间mov ebp - 4, 10 ; mov ebp - 4, 10 ; 将将1010保存至变量保存至变量 a amov ebp - 8, 5 ; location of bmov e

6、bp - 8, 5 ; location of bmov ebp - 12, 2 ; location of cmov ebp - 12, 2 ; location of c活动记录函数被多次调用函数被多次调用 对应多个活动记录对应多个活动记录 程序运行对应一个程序运行对应一个活动记录树活动记录树 输入不同，活动记录树输入不同，活动记录树可能可能有所不同有所不同 活动记录之间活动记录之间“相互嵌套相互嵌套” 可用可用“栈栈”来跟踪各活动记录来跟踪各活动记录 当函数返回后相应的记录当函数返回后相应的记录不再不再被引用被引用Zhou, Erqiang7School of Information a

7、nd Software Engineering活动记录“当函数返回后相应的记录当函数返回后相应的记录不再被引用不再被引用”有没有反例？有没有反例？Zhou, Erqiang8School of Information and Software Engineeringfunctionfunction CreateCounter() CreateCounter() varvar counter = 0; counter = 0;returnreturn function() function() counter +;counter +;returnreturn counter; counter;

8、活动记录“当函数返回后相应的记录当函数返回后相应的记录不再被引用不再被引用”反例反例Zhou, Erqiang9School of Information and Software Engineeringfunction CreateCounter() function CreateCounter() var counter = 0;var counter = 0;return function() return function() counter +;counter +;return counter;return counter; function MyFunction() functio

9、n MyFunction() f = CreateCounter();f = CreateCounter();print(f();print(f();print(f();print(f(); MyFunctionCreateCountercounter = 0;f = 活动记录“当函数返回后相应的记录当函数返回后相应的记录不再被引用不再被引用”反例反例Zhou, Erqiang10School of Information and Software Engineeringfunction CreateCounter() function CreateCounter() var counter

10、= 0;var counter = 0;return function() return function() counter +;counter +;return counter;return counter; function MyFunction() function MyFunction() f = CreateCounter();f = CreateCounter();f();f();f();f(); MyFunctionCreateCountercounter = 1;f = counter=2;两种链接的区别？两种链接的区别？活动记录活动记录的内容活动记录的内容 返回地址返回地址

11、 控制链（动态链接）控制链（动态链接） 指向主调程序的活动记录指向主调程序的活动记录 存取链（静态链接）存取链（静态链接） 指向指向非局部变量非局部变量所在的活动记录所在的活动记录Zhou, Erqiang11School of Information and Software Engineering活动记录活动记录的内容活动记录的内容 CPU CPU 现场现场 实际参数的个数实际参数的个数 形式参数形式参数 局部变量局部变量 临时变量临时变量 等等等等Zhou, Erqiang12School of Information and Software Engineering实际参数在哪里？实际

12、参数在哪里？局部变量局部变量 和和 临时变量临时变量有什么区别？有什么区别？编译器不同而有所不同编译器不同而有所不同变量的存储分配局部变量局部变量 存储空间存储空间大小大小可根据其类型而可根据其类型而静态确定静态确定分配方法分配方法 按这些变量声明时出现的次序按这些变量声明时出现的次序 在局部数据域中依次分配空间在局部数据域中依次分配空间局部数据的地址局部数据的地址 栈帧的首地址栈帧的首地址 + + 数据的偏移数据的偏移Zhou, Erqiang13School of Information and Software Engineering变量的存储分配局部数据的地址局部数据的地址 D D表示

13、活动记录的首地址表示活动记录的首地址 offset(x) offset(x)： x x 在活动记录中的偏移在活动记录中的偏移 D+offset(x) D+offset(x) 为为 x x 的地址的地址1)1)如果如果 D D 和和 offset( offset(x x) ) 在编译时都能确定下来在编译时都能确定下来 x x 称为称为静态变量静态变量 如果语言仅支持静态变量如果语言仅支持静态变量 那么将那么将不支持不支持哪些功能？哪些功能？Zhou, Erqiang14School of Information and Software Engineering活动记录在编译时可确定活动记录在编译

14、时可确定包括包括大小大小和和位置位置变量的存储分配D D表示活动记录的首地址表示活动记录的首地址 编译时编译时静态确定静态确定( (分配分配) ) 函数每次活动时函数每次活动时 活动记录的位置活动记录的位置相对固定相对固定 进程空间只允许有该函数的进程空间只允许有该函数的一个活动一个活动记录记录 不支持递归调用不支持递归调用 不支持动态数组不支持动态数组Zhou, Erqiang15School of Information and Software Engineering相对于程序自己相对于程序自己 的进程空间的进程空间变量的存储分配2 2）如果）如果 offset( offset(x x)

15、 ) 在在编译编译时能确定下来时能确定下来 D D 在在运行运行时能确定下来时能确定下来 x x 称为称为半静态变量半静态变量 如果语言支持半静态变量如果语言支持半静态变量 程序单元可多次被激活程序单元可多次被激活 支持递归调用支持递归调用 活动记录可用栈来实现活动记录可用栈来实现 变量支持变量支持“栈式分配栈式分配”Zhou, Erqiang16School of Information and Software Engineering活动记录活动记录大小大小 在编译时可确定在编译时可确定变量的存储分配3 3）如果）如果 D D和和offset(offset(x x) ) 在编译时不能确定下

16、来在编译时不能确定下来 但运行能确定但运行能确定 x x 称为称为半动态变量半动态变量 支持语言：支持语言：C99 C99 动态数组动态数组Zhou, Erqiang17School of Information and Software Engineering活动记录活动记录大小位置大小位置在编译时不能确定在编译时不能确定在运行时可确定在运行时可确定intint f() f() intint n; n; scanf(%d, &n); scanf(%d, &n); intint ar arrayrayn;n; printf(%dn, printf(%dn, sizeofsize

17、of(arrray);(arrray); returnreturn 0; 0; 活动记录活动记录保存什么？保存什么？变量的存储分配3 3）x x 为为半动态变量半动态变量 x x 的其它属于信息，如的其它属于信息，如 数组元素的类型数组元素的类型 数组的维数数组的维数 数组首地址指针数组首地址指针 仅分配空间，运行时确定值仅分配空间，运行时确定值 x x 的描述符保存各属性的描述符保存各属性 运行时根据属性计算变量的位置运行时根据属性计算变量的位置Zhou, Erqiang18School of Information and Software Engineering变量的存储分配3 3）活动

18、记录中有）活动记录中有半动态变量半动态变量 活动记录能否由活动记录能否由“栈栈”来实现？来实现？ 半动态变量能否支持半动态变量能否支持“栈式分配栈式分配”？ 半动态变量可以半动态变量可以 动态分配在活动记录的动态分配在活动记录的“尾部尾部” 即运行栈的即运行栈的“栈顶栈顶” 半动态变量的半动态变量的生存期生存期与活动记录相同与活动记录相同 随函数的退出而消亡随函数的退出而消亡Zhou, Erqiang19School of Information and Software Engineering变量的存储分配4 4）如果）如果 offset( offset(x x) ) 在编译、运行时都不能确

19、定下来在编译、运行时都不能确定下来 x x 的大小在运行时不固定的大小在运行时不固定 运行时可动态改变，运行时可动态改变，x x 称为称为动态变量动态变量 如果将如果将 x x 保存在活动记录中保存在活动记录中 每个活动记录的长度不确定每个活动记录的长度不确定 x x 的生存期与活动记录不同步的生存期与活动记录不同步 不能使用栈式分配不能使用栈式分配 如何解决？如何解决？Zhou, Erqiang20School of Information and Software Engineering变量的存储分配4 4）x x 为为动态变量动态变量 使用另外的数据结构使用另外的数据结构“堆堆”来存储来

20、存储 需要堆的情况：需要堆的情况： 局部变量的值在单元活动后还需保留局部变量的值在单元活动后还需保留 调用单元与被调用单元调用单元与被调用单元 生存期不满足先进后出模式生存期不满足先进后出模式 Zhou, Erqiang21School of Information and Software Engineering进程的存储组织方式进程的存储组织方式 变量的存储分配Zhou, Erqiang22School of Information and Software Engineering代码代码静态数据静态数据堆堆 栈栈 变量的存储分配数据对象的存储安排中的数据对象的存储安排中的对齐问题对齐问题

21、typedeftypedef struct _a struct _a typedeftypedef struct _b struct _b charchar c1; c1; charchar c1; c1; longlong i1; i1; charchar c2; c2; charchar c2; c2; intint i1; i1; intint i2; i2; intint i2; i2;a;a; b; b;sizeof(a) sizeof(a) 与与 sizeof(b) sizeof(b) 一样吗一样吗？为什么为什么？Zhou, Erqiang23School of Informati

22、on and Software Engineering变量的存储分配数据对象的存储安排中的数据对象的存储安排中的对齐问题对齐问题Zhou, Erqiang24School of Information and Software Engineeringchar c1; 1long i1; 4char c2; 1int i2; 4char c1; 1long i1; 4int i2; 4n+4nchar c2; 1n+8n+12struct _a32位机器位机器：sizeof(struct _a) = 16变量的存储分配数据对象的存储安排中的数据对象的存储安排中的对齐问题对齐问题Zhou, Erq

23、iang25School of Information and Software Engineeringchar c1; 1char c2; 1long i1; 4int i2; 4char c1; 1long i1; 4int i2; 4char c2; 1n+4nn+1n+8struct _b32位机器位机器：sizeof(struct _b) = 12存储分配模式静态分配静态分配 程序语言仅支持静态变量程序语言仅支持静态变量栈式分配栈式分配 半静态变量、半动态变量半静态变量、半动态变量 调用关系先进后出调用关系先进后出堆式分配堆式分配 动态变量动态变量Zhou, Erqiang26Sch

24、ool of Information and Software Engineering栈式存储分配半静态变量半静态变量 offset(offset(x x) ) 在在编译编译时确定、时确定、D D 在在运行运行时确定时确定 活动记录活动记录 大小在编译大小在编译时确定、时确定、位置在运行位置在运行时确定时确定半动态变量半动态变量 D D和和offset(offset(x x) ) 在运行确定在运行确定 活动记录大小、位置在活动记录大小、位置在激活激活时确定时确定Zhou, Erqiang27School of Information and Software Engineering例子：过程例

25、子：过程A A调用过程调用过程P PSchool of Information and Software Engineering28Zhou, Erqiang栈式存储分配 之半静态变量currentfreeA A的活动记录的活动记录返回地址返回地址 IP+X动态连接动态连接currentP P的活动记录的活动记录currentfree哪些指针在返回时需要恢复？哪些指针在返回时需要恢复？返回地址：指令指针返回地址：指令指针IP？current,free处理方法处理方法(1) (1) 设置当前栈指针设置当前栈指针current 表示当前活动记录的开始位置表示当前活动记录的开始位置 （活动记录首地址

26、（活动记录首地址D D，长度为，长度为L L）(2) (2) 指针指针free表示栈顶下一个可用单元表示栈顶下一个可用单元 free = current + L(3) (3) 局部变量局部变量X X在活动记录中的位移为在活动记录中的位移为 i i 变量的地址变量的地址current+i, , 值为值为Dcurrent+i栈式存储分配 之半静态变量Zhou, Erqiang29School of Information and Software Engineering处理方法处理方法(4) A(4) A调用调用B B时，时，B B单元被激活单元被激活 在在A A的栈帧（活动记录）之上的栈帧（活动

27、记录）之上 建立建立B B的当前实例的活动记录的当前实例的活动记录 将将currentcurrent和和freefree绑定于绑定于B B的活动记录的活动记录 绑定之前保存绑定之前保存currentcurrent指针的当前值指针的当前值(5) (5) 从从B B返回时，释放其活动记录返回时，释放其活动记录 恢复恢复currentcurrent和和freefree指针指针 栈式存储分配 之半静态变量Zhou, Erqiang30School of Information and Software Engineering动态连接动态连接动态链动态链AEFGF例：例：A call E; E call

28、 F; F call G; G call F;.School of Information and Software Engineering31Zhou, Erqiang栈式存储分配 之半静态变量CALL P的翻译的翻译 1) 1) D free := ? （保存返回地址）（保存返回地址） 2) 2) Dfree + 1 := current （保存（保存currentcurrent） 3) 3) current := free （建立新的（建立新的currentcurrent） 4) 4) free := free + L （调整（调整freefree） 5) 5) ip := P（转移到（

29、转移到P P） 6) ( 6) (函数返回后需执行的指令函数返回后需执行的指令) )School of Information and Software Engineering32Zhou, Erqiang栈式存储分配 之半静态变量ip + 5例子：过程例子：过程A A调用过程调用过程P PSchool of Information and Software Engineering33Zhou, Erqiang栈式存储分配 之半静态变量返回地址返回地址动态连接动态连接currentfreeA A的活动记录的活动记录返回地址返回地址动态连接动态连接P P的活动记录的活动记录currentfree

30、如何返回？如何返回？free = currentcurrent = Dcurrent+1ip = DfreeRETURN语句的翻译语句的翻译 1) 1) 恢复恢复free free := current 2) 2) 恢复主调过程的恢复主调过程的current current := Dcurrent + 1 3) 3) 返回返回 ip := DfreeSchool of Information and Software Engineering34Zhou, Erqiang栈式存储分配 之半静态变量例子：过程例子：过程P P退出，返回过程退出，返回过程A AcurrentSchool of Inf

31、ormation and Software Engineering35Zhou, Erqiang栈式存储分配 之半静态变量返回地址返回地址动态连接动态连接currentfreeA A的活动记录的活动记录返回地址返回地址动态连接动态连接P P的活动记录的活动记录freefree = currentcurrent = Dcurrent+1ip = Dfree处理方法处理方法 在活动记录中为变量在活动记录中为变量i i 建立描述符建立描述符 在活动记录的最后（栈顶）分配变量在活动记录的最后（栈顶）分配变量 i i 用用描述中的指针域描述中的指针域指向变量指向变量 i i 的存储位置的存储位置 产生相

32、关指令产生相关指令 创建变量存储空间创建变量存储空间 修改描述符修改描述符School of Information and Software Engineering36Zhou, Erqiang栈式存储分配 之半动态变量处理方法处理方法School of Information and Software Engineering37Zhou, Erqiang栈式存储分配 之半动态变量返回地址返回地址动态连接动态连接currentfree编译时编译时A A的活动记录的活动记录变量变量x x描述符描述符( (地址地址, ,大小等大小等) )运行时运行时 获取元素个数获取元素个数 计算数组大小计算数

33、组大小其它变量其它变量x x的存储空间的存储空间free修改修改free指针指针 free = free + L修改描述符修改描述符变量的作用域变量的作用域 指可访问该变量的程序范围指可访问该变量的程序范围 如何确定这个范围？如何确定这个范围？ 制定作用域规则制定作用域规则作用域规则作用域规则 静态作用域规则静态作用域规则 动态作用域规则动态作用域规则School of Information and Software Engineering38Zhou, Erqiang非局部环境的引用静态作用域规则静态作用域规则 最近嵌套规则最近嵌套规则 引用引用最近的最近的“外层嵌套外层嵌套”中说明的变量

34、中说明的变量嵌套的层次嵌套的层次 若若A是是B的直接外层的直接外层, ,则则 B的层次的层次 = A的层次的层次 + 1+ 1School of Information and Software Engineering39Zhou, Erqiang非局部环境的引用School of Information and Software Engineering40Zhou, Erqiang非局部环境的引用unit A;y: int;unit B;end B;y: int;unit C;end D;end C;.unit D;.end A;end E;z: int;unit F;end G;unit

35、G; x,y: int; .unit E;z:=x+y;end F;.x: int;A(0)B(1)C(2)D(3)E(1)F(2)G(2)嵌套层次图嵌套层次图F F或或G G中能否调用中能否调用B?B?F F或或G G中能否调用中能否调用C?C?如何实现引用？如何实现引用？静态作用域规则的引用方法静态作用域规则的引用方法 将嵌套关系保存到活动记录将嵌套关系保存到活动记录通过通过“静态连接静态连接”实现实现静态连接静态连接 指向嵌套指向嵌套直接直接外层外层最新最新活动记录的指针活动记录的指针 保存位置：活动记录中保存位置：活动记录中第第3 3个个存储单元存储单元静态链静态链 运行时各活动记录运

36、行时各活动记录由静态连接由静态连接所构成的链所构成的链School of Information and Software Engineering41Zhou, Erqiang非局部环境的引用例：例：A call E; E call F; F call G; G call F;School of Information and Software Engineering42Zhou, Erqiang非局部环境的引用AEFGF.A(0)B(1)C(2)D(3)E(1)F(2)G(2)如何计算非局如何计算非局部部x x变量地址？变量地址？非局部变量非局部变量x x的地址的求法的地址的求法School

37、 of Information and Software Engineering43Zhou, Erqiang非局部环境的引用AEFGF.A(0)B(1)C(2)D(3)E(1)F(2)G(2)F F 引用引用 单元单元A A中的变量中的变量x x其在其在A A中的偏移为中的偏移为offsetoffsetcurrent嵌套层次：嵌套层次：2 2Dcurrent+2为静态连接为静态连接Dcurrent + 2Dcurrent + 2 + offsetcurrent非局部变量非局部变量x x的地址的求法的地址的求法 A是是B的直接外层的直接外层( (第第1个外层个外层) ) DA Dcurrent

38、 + 2 A是是B的第的第2个外层个外层 DA = DDcurrent + 2 + 2 A是是B的第的第3个外层个外层 DA = DDDcurrent + 2 2 2 可定义函数实现可定义函数实现 DA 的获取的获取 School of Information and Software Engineering44Zhou, Erqiang非局部环境的引用嵌套层次：嵌套层次：2 2Dcurrent+2为静态连接为静态连接Dcurrent + 2Dcurrent + 2 + offsetDA:单元单元A的活动记录首地址的活动记录首地址假设单元假设单元p中引用了单元中引用了单元t中的变量中的变量x

39、且且p, t的深度分别为的深度分别为np, nt设设d = np nt, , 定义函数定义函数 f(d) if( d = 0 ) then return current ; else return D f(d-1) + 2 ; f(0) = current; f(1) = Dcurrent+2; f(2) = D f(1)+2 = D Dcurrent+2 +2;School of Information and Software Engineering45Zhou, Erqiang非局部环境的引用通过通过静态连接静态连接可以引用非局部环境可以引用非局部环境 如何如何建立静态连接建立静态连接呢

40、？呢？什么时候建立？什么时候建立？ 保存位置：在活动记录的保存位置：在活动记录的第第3 3个个存储单元存储单元 在返回地址、动态连接之后保存在返回地址、动态连接之后保存 在在处理程序单元调用处理程序单元调用时建立时建立怎么建立？怎么建立？ 利用利用当前的栈帧当前的栈帧 考查嵌套结构下单元调用关系考查嵌套结构下单元调用关系School of Information and Software Engineering46Zhou, Erqiang非局部环境的引用嵌套结构下单元嵌套结构下单元 A 调用单元调用单元 BSchool of Information and Software Engineer

41、ing47Zhou, Erqiang非局部环境的引用(3) nA-nB = 1(4) nA-nB 1(1) nA-nB = -1(2) nA-nB = 0BAcall BABcall BBAcall BBcall BA通过通过当前栈帧当前栈帧建立建立B的静态连接的静态连接current=f(0)Dcurrent + 2 =f(1)f(2)f(d+1)因此，静态连接因此，静态连接 Dfree+2 的值的值为为 f(d+1)单元调用语句单元调用语句 CALL P 的翻译的翻译 1) 1) D free := ? （保存返回地址）（保存返回地址） 2) 2) Dfree + 1 := current

42、 （保存（保存currentcurrent） 3) 3) Dfree + 2 := f(d+1) （保存静态连接）（保存静态连接） 4) 4) current := free （建立新的（建立新的currentcurrent） 5) 5) free := free + L （调整（调整freefree） 6) 6) ip := P（转移到（转移到P P） 7) ( 7) (函数返回后需执行的指令函数返回后需执行的指令) )School of Information and Software Engineering48Zhou, Erqiang非局部环境的引用ip + 6动态作用域规则动态作用域

43、规则 一种最近一种最近活动规则活动规则对非局部变量对非局部变量 引用的最近的引用的最近的“调用外层调用外层”中说明的变量中说明的变量 生存期嵌套生存期嵌套例：例：AEF的调用序列的调用序列 F的直接调用外层为的直接调用外层为E E的直接调用外层为的直接调用外层为ASchool of Information and Software Engineering49Zhou, Erqiang非局部环境的引用如何引用非局部变量？如何引用非局部变量？直接使用直接使用动态连接！动态连接！数据参数传递数据参数传递School of Information and Software Engineering50Z

44、hou, Erqiang参数传递procedure swap (a , b : integer);var temp : integer;begin temp := a; a := b; b := tempend; swap ( i , ai ) i = 3 , a = 7，1，4，5，8数据参数传递之数据参数传递之引址调用引址调用 将将实参的地址实参的地址传递给相应的形参传递给相应的形参 在单元中对形参的引用在单元中对形参的引用 实际上是实际上是对对形式单元中形式单元中实参地址实参地址的引用的引用School of Information and Software Engineering51Zhou, Erqiang参数传递swap(i,ai); swap(i,ai); 相当于执行相当于执行: : a := i a := i的地址的地址; ; b := a3 b := a3的地址的地址; ; temp := a temp := a ; (temp=3); (temp=3) a a := b := b ; (i=4); (i=4) b b := temp; (a3=temp=3) := temp; (a3=temp=3)执行结果执行结果: i=4, a3=3: i=4, a3=3数据参数传递之数据参数传递之值调用值调用 形参只起形参只起局部变量局部变量作用作用 (1)(1)