编译原理与技术 运行环境 2018/11/24 《编译原理与技术》－运行环境.

Presentation on theme: "编译原理与技术 运行环境 2018/11/24 《编译原理与技术》－运行环境."— Presentation transcript:

1 编译原理与技术 运行环境 2018/11/24 《编译原理与技术》－运行环境

2 运行环境 存储组织与分配 参数传递 程序单元、运行时内存划分与活动记录 静态/动态存储分配 动态栈式的过程调用/返回 非局部名字的访问
参数传递的方式及其实现 2018/11/24 《编译原理与技术》－运行环境

3 存储组织与分配 程序单元 －FORTRAN的子例程(subroutine)
－PASCAL的过程/函数(procedure/function) －C的函数 程序单元的激活（调用）与终止（返回） 程序单元的执行需要： 代码段＋活动记录（程序单元运行所需的额外信息，如参数，局部数据，返回地址等） 2018/11/24 《编译原理与技术》－运行环境

4 运行时内存划分 代码段 静态数据区 栈（stack） 堆（heap） 大小可以静态确定 全局/局部静态变量 活动记录栈 动态分配的数据
2018/11/24 《编译原理与技术》－运行环境

5 活动记录 活动记录－AR （Activation Record） 是一连续存储区域，用于管理与存放和程序单元执行相关的重要信息。
－ 临时区域。用以保存临时计算结果 － 局部数据区。源程序中程序单元声明的局部变量对应在此区域。 － 机器状态保存区。存有机器的寄存器，程序指令计数器 ip（返回地址）等。 2018/11/24 《编译原理与技术》－运行环境

6 活动记录 AR中的内容 － 访问链（静态链）。当前程序单元可以访问的（静态程序中）外围程序单元的活动记录链。
－ 控制链（动态链）。程序单元的活动记录按它们的生成（或调用）次序串成链。 － 实在参数 － 返回值 2018/11/24 《编译原理与技术》－运行环境

7 活动记录的内容 返回值（return value） 实在参数（actual parameter） 控制链（control link）
可选的访问链（optional access/static link） 机器状态（saved machine status） 局部数据（local data） 临时区（temporaries） 2018/11/24 《编译原理与技术》－运行环境

8 活动记录内容的存取 AR的基地址bp 返回值 实在参数 控制链 （old bp） 可选的访问链 机器状态 局部数据 临时区
2018/11/24 《编译原理与技术》－运行环境

9 活动记录内容的存取 bp 返回值 实在参数 控制链（old bp） 可选的访问链 机器状态 局部数据 临时区 地址： bp+d1 偏移 d1
2018/11/24 《编译原理与技术》－运行环境

10 静态存储分配 － 全局变量的存储绑定、AR均在编译时确定 且在整个程序执行中保持。 － 不支持： 1）动态数据结构 2）过程递归调用
－ 实现静态分配的语言： （早期）FORTRAN 2018/11/24 《编译原理与技术》－运行环境

11 e.g.1 FORTRAN静态存储分配 CALL sub SUBROUTINE sub CALL sub DATA I/10
END WRITE(*.*) I I = 100 END 第一次调用sub，输出10 第二次调用sub，输出100 第一次调用前 机器状态 I （ 10 ） 第一次调用后 机器状态 I （ 100 ） 第二次调用后 机器状态 I （ 100 ） 2018/11/24 《编译原理与技术》－运行环境

12 动态存储分配 栈式分配 － AR在过程被调用（激活）时才在栈（stack）上分配；而在被调用过程（返回）终止时从栈上撤销。
－ 过程中（非静态）局部变量的存储绑定在过程执行时有效；过程终止时失效。 － 支持过程递归调用。每次递归调用时，局部变量绑定到不同的存储。 2018/11/24 《编译原理与技术》－运行环境

13 动态存储分配 栈式分配下的AR内容布局 bp 栈顶sp 返回值 实在参数 可选的访问链 返回地址 调用者 bp 可选机器状态 局部数据
临时区 参数/返回值区域放在AR高端－靠近调用者过程的活动记录，既便于双方存取，又适应参数可变情况 高地址 长度固定的区域放在AR中间 bp 低地址 长度可变的区域放在AR低端 栈顶sp 2018/11/24 《编译原理与技术》－运行环境

14 － 过程调用：分配被调过程的AR并填入相关信息，然后程序控制转移到被调过程入口； －过程A 调用 过程B 的过程调用序列：
栈式分配下的过程调用与返回 － 过程调用：分配被调过程的AR并填入相关信息，然后程序控制转移到被调过程入口； －过程A 调用 过程B 的过程调用序列： A的“调用”准备操作：1）～ 3） 1）A 计算实在参数并放入（对应栈操作－push） B的活动记录中；（亦可考虑返回值存放空间） 2）A将可选的访问链放入（push）B的活动记录； 3）A将返回地址放入B的活动记录并跳转到过程B 的代码入口，开始B的执行；（一般通过A中的 代码指令－“call B” 来完成这一步） 4） 2018/11/24 《编译原理与技术》－运行环境

15 4）在B自己的AR中保存A的活动记录的基址（即当前bp，对应操作 push bp）并且将这个位置作为B自己AR的基址（对应操作）
栈式分配下的过程调用与返回 －过程A 调用 过程B 的过程调用序列： B的入口代码：4）～ 6） 4）在B自己的AR中保存A的活动记录的基址（即当前bp，对应操作 push bp）并且将这个位置作为B自己AR的基址（对应操作） mov sp,bp 即 bpsp） 5）保存可选的机器状态（寄存器） 6）为局部数据分配空间，（对应操作） sub local_size，sp，即sp sp – local_size 7）“开始”B的执行。（至此，B的AR建好） 2018/11/24 《编译原理与技术》－运行环境

16 － 过程返回：回收分配的被调过程的AR，并将程序控制转移回调用过程继续执行； －过程A 调用 过程B 的过程返回序列：
栈式分配下的过程调用与返回 － 过程返回：回收分配的被调过程的AR，并将程序控制转移回调用过程继续执行； －过程A 调用 过程B 的过程返回序列： B的出口代码：1）～ 2） 1）B回收局部数据空间；恢复原先保存的机器状态2）B恢复A的AR基址；取出返回地址将程序控制交回到A。对应操作： mov bp,sp spbp pop bp //恢复调用者A的bp ret // B执行结束并返回 注：X86-Linux中的leave 和ret组合亦能达到目的。 至此，B的AR中除了参数/返回值区域，其余区域全部回收（撤销）了。 2018/11/24 《编译原理与技术》－运行环境

17 4）A调整栈顶sp（主要根据参数个数以及可能有的访问链和可能有的返回值）。对应操作：
栈式分配下的过程调用与返回 －过程A 调用 过程B 的过程返回序列： A的“调用”善后代码：3）～ 4） 3）A取回返回值以及引用型参数（有的话） 4）A调整栈顶sp（主要根据参数个数以及可能有的访问链和可能有的返回值）。对应操作： add para_size, sp 即spsp + para_size 至此，B的AR区域全部回收（撤销）了。 2018/11/24 《编译原理与技术》－运行环境

18 e.g.2 栈式存储分配 有C程序如下： void g() { int a ; a = 10 ; }
void h() { int a ; a = 100; g(); } main() { int a = 1000; h(); } 2018/11/24 《编译原理与技术》－运行环境

19 e.g.2 栈式存储分配 过程g被调用时，活动记录栈的（大致）内容 返回地址 main程序的AR old bp a : 1000 返回地址
函数h的AR old bp a : 100 返回地址 bp 函数g的AR old bp a : 10 sp 2018/11/24 《编译原理与技术》－运行环境

20 e.g.3 有参函数的活动记录 .file "ar.c" .text void func( int a , int b )
.globl func .type func: pushl %ebp movl %esp, %ebp subl $8, %esp movl 8(%ebp), %eax movl %eax, -4(%ebp) movl 12(%ebp), %eax movl %eax, -8(%ebp) leave ret 参数 b 参数 a 返回地址 老bp 局部变量c 局部变量d bp+12 void func( int a , int b ) { int c , d; c = a; d = b; } bp+8 bp bp－4 bp－8 2018/11/24 《编译原理与技术》－运行环境

21 e.g.4. scanf的可变参数 有如下C程序： main() { int i ; float f; int j ;
scanf(“%d%f”, &i, &f); //第一次调用时3个参数 scanf(“%d”, &j ); //第二次调用时 2个参数 return 0; } 2018/11/24 《编译原理与技术》－运行环境

22 e.g.4. scanf的可变参数 由于C语言采用逆序传递参数，格式串参数将被放在AR中的“固定”位置，即bp+8。而由此参数即可确定待输入值的参数（变量）的个数。从而适应参数个数变化的情况。 &f &i &j 格式串1指针 bp+8 格式串2指针 返回地址 返回地址 老bp 老bp bp … … … … scanf的第一次调用时AR scanf的第二次调用时AR 2018/11/24 《编译原理与技术》－运行环境

23 e.g.5 悬空引用 有C程序如下： main() int * dangle() { {
{ { int * p = dangle(); int i; … return &i; } } 2018/11/24 《编译原理与技术》－运行环境

24 非局部变量访问 静态作用域规则 vs. 动态作用域规则 “最接近嵌套” vs. 现行单元活动（调用次序） 分程序
－ 含有声明和语句；如C的{…} － 分程序具有以下特征： -- 可以嵌套； -- 没有参数； -- 控制流沿静态文本进入、流出 -- 采用“最接近嵌套”的规则 2018/11/24 《编译原理与技术》－运行环境

25 非局部变量访问 e.g.6 分程序 main() { int a = 0 ; int b =0; //local VAR of main
{ int b = 1 ; // block 1 { int a = 2 ; printf(“%d %d\n”,a,b);//block 2 } { int b = 3 ; printf(“%d %d\n”,a,b);//block 3 } printf(“%d %d\n”,a,b); } 2018/11/24 《编译原理与技术》－运行环境

26 分程序的实现 1）按无参过程方式来实现 －控制流进入分程序时，在栈上分配局部变量空间 ，退出时撤销上述空间。e.g.6中各变量存储如下：
a0 = 0 a0 = 0 a0 = 0 a0 = 0 a0 = 0 b0 = 0 b0 = 0 b0 = 0 b0 = 0 b0 = 0 b1 = 1 b1 = 1 b1 = 1 b1 = 1 a1 = 2 b2 = 3 a）进入block 1, 未进入block 2 b）进入block 2, 未进入block 3 c）退出block 2, 进入block 3 d）退出block 3, 进入block 1 e）退出block 1, 进入main 2018/11/24 《编译原理与技术》－运行环境

27 分程序的实现 2）按过程为单位统一分配 －将分程序中的局部变量独立地看成过程的局部变量。e.g.6中各变量存储如下： （两种方案）
a0 = 0 a0 = 0 b0 = 0 b0 = 0 b1 = 1 b1 = 1 a1 = 2 a1 = 2, b2 = 3 b2 = 3 a）a1和b2将先后被分配在同一空间，因为它们的生存期（作用域）不重叠、不嵌套。 b）a1和b2将被分配在不同的空间。 2018/11/24 《编译原理与技术》－运行环境

28 过程嵌套定义语言中非局部名字访问 e.g.7 嵌套的过程定义 主程序 : 0 A：1 i： 2 B：2 C B A 主程序 j： 3 C：3
program dynamic_static_link; procedure A ; var i : integer ; procedure B ; var j : integer; procedure C ; begin B; end; j := i; C ; B ; A ; end. 主程序 : 0 嵌套深度：1 A：1 嵌套深度：2 i： 2 C B：2 B A 嵌套深度：3 主程序 j： 3 C：3 嵌套深度：4 e.g.7 嵌套的过程定义 2018/11/24 《编译原理与技术》－运行环境

29 过程嵌套定义语言中非局部名字访问 设嵌套深度的初值为0。在“读过”函数名字后，即进入新的嵌套层次，嵌套深度加1。也即，函数体（从参数算起）区域的嵌套深度与函数名字的嵌套深度之差为1。 定义点嵌套深度N-def： 任何名字（包括普通变量名和函数名）的定义点嵌套深度是包围该名字定义的最内层函数体（body）的嵌套深度。 一个名字有且仅有一个定义点嵌套深度。 2018/11/24 《编译原理与技术》－运行环境

30 过程嵌套定义语言中非局部名字访问 引用点嵌套深度N-ref：
任何名字（包括普通变量名和函数名）的一个引用点嵌套深度是引用该名字的语句所在的最内层函数体（body）的嵌套深度。 一个名字可以有多个不同引用点嵌套深度。（名字可能出现在不同函数体的多条语句里嘛。^_^） 函数的参数与其局部声明变量均定义在同一函数体内，它们的定义点嵌套深度相同哦！ 2018/11/24 《编译原理与技术》－运行环境

31 使用静态访问链来存取非局部名字 名字 类别 定义点 嵌套深度Def 引用点 嵌套深度Ref 层次差diff = Ref - Def
dynamic_static_link 函数 A 1 i 变量 2 3 B 2/4 0/2 j C 2018/11/24 《编译原理与技术》－运行环境

32 使用静态访问链来存取非局部名字 一个函数的活动记录中的静态链，指向包围该函数定义的最内层函数所对应的一个活动记录，此最内层函数也即是“父”函数。 在函数体C中被引用的名字a的定义点嵌套深度为defa ，而该名字在该函数体中的引用点嵌套深度为refa。由于“定义在先，引用在后”，故而， refa≥ defa 2018/11/24 《编译原理与技术》－运行环境

33 使用静态访问链来存取非局部名字 设层差diff = refa – defa，那么，通过追踪函数C的活动记录的静态链diff次，即到达定义了名字a的某个（父或祖先）函数P对应的活动记录。 base = bp; while(diff--) base = base[offset_StaticLink] 当层差diff==0，名字a的定义点和引用点位于同一个函数体内，即函数C和P是同一个函数，也即当前函数就是父函数！此时，无需追踪静态链！ 2018/11/24 《编译原理与技术》－运行环境

34 使用静态访问链来存取非局部名字 当层差diff==0，无需追踪静态链！
1）如名字a是普通变量，则可以通过当前活动记录（对应函数C）基址bp+offset_a来访问。 2）如名字a是函数名，显然，a是定义在函数C中（子）函数。引用a属于父函数调用子函数。则函数a的静态链就是当前活动记录（对应函数C）基址bp。（建立函数a静态链，push bp） 2018/11/24 《编译原理与技术》－运行环境

35 使用静态访问链来存取非局部名字 当层差diff==1，名字a是一个函数。
1）调用函数C(caller)与被调函数a(callee)是兄弟函数，拥有相同的父函数。则仅需追踪C的静态链1次，即可获得父函数P活动记录基址，也即是函数a的静态链。 2）调用函数C与被调函数a是同一个函数，也即函数C是递归函数。 2018/11/24 《编译原理与技术》－运行环境

36 使用静态访问链来存取非局部名字 当层差diff >1，名字a是一个函数。则被调函数a(callee)是调用函数C(caller)的父/祖先函数（或父/祖先函数的兄弟函数）。 2018/11/24 《编译原理与技术》－运行环境

37 静态链的追踪操作 当层差diff ≥1，静态链追踪操作的语义如下 base = bp;
while(diff--) base = base[offset_StaticLink] 代码序列可以是： 1）(bp + offset_StaticLink)  Reg //追踪1次 2）(Reg + offset_StaticLink) Reg //追踪2次 … … // 追踪diff次 对于变量读写: (Reg+Var_offset) 对函数调用，建立静态链：push Reg 2018/11/24 《编译原理与技术》－运行环境

38 e.g.7 嵌套的过程定义 过程的调用次序 主程序 A  B  C  B1 …
过程B第一次被过程C调用时，C需追踪2次访问链才能为找到过程B1的父过程A的AR。 具体如下： 2018/11/24 《编译原理与技术》－运行环境

39 e.g.7 嵌套的过程定义 … 主程序AR 控制链：bp(系统) 运行时栈：主程序 2018/11/24 《编译原理与技术》－运行环境

40 e.g.7 嵌套的过程定义 … 主程序AR 控制链：bp(系统) 访问链：bp(main) 访问链的地址表示： bp + 8 在此活动记录中的偏移为8 返回地址1 过程A的AR 控制链：bp(main) 局部名字：i 运行时栈：主程序 A 主程序负责建立A（活动记录中）的访问链。此时该链指向主程序运行时的活动记录（why？）。此访问链的位置（或偏移）是多少？ 2018/11/24 《编译原理与技术》－运行环境

41 e.g.7 嵌套的过程定义 运行时栈：主程序 A  B B中语句j := i如何执行的？ 主程序AR j := i执行如下：
… 主程序AR j := i执行如下： 取过程A的活动记录地址： (bp + 8) -> R 取A中局部变量i的值： (R – 4 ) -> R 将该值赋给B的局部变量j： R -> (bp – 4) 控制链：bp(系统) 访问链：bp(main) 返回地址1 过程A的AR 控制链：bp(main) 局部名字：i 访问链：bp(A) 返回地址2 过程B的AR 控制链：bp(A) 局部名字：j0 运行时栈：主程序 A  B B中语句j := i如何执行的？ 2018/11/24 《编译原理与技术》－运行环境

42 运行时栈：主程序 A  B  C 主程序AR 过程A的AR 过程B的AR 过程C的AR … 控制链：bp(系统)
访问链：bp(main) 返回地址1 过程A的AR 控制链：bp(main) 局部名字：i 访问链：bp(A) 返回地址2 过程B的AR 控制链：bp(A) 局部名字：j0 访问链：bp(B) 过程C的AR 返回地址3 控制链：bp(B) 运行时栈：主程序 A  B  C 2018/11/24 《编译原理与技术》－运行环境

43 运行时栈： 主程序 A  B  C  B1 过程C为过程B1 建立访问链： 1： (bp+8)R 2：(R+8)R
… 主程序AR 控制链：bp(系统) 访问链：bp(main) 返回地址1 过程A的AR 控制链：bp(main) 局部名字：i 2 访问链：bp(A) 运行时栈： 主程序 A  B  C  B1 返回地址2 过程B的AR 控制链：bp(A) 过程C为过程B1 建立访问链： 1： (bp+8)R 2：(R+8)R 3： push R 局部名字：j0 1 访问链：bp(B) 过程C的AR 返回地址3 控制链：bp(B) 访问链：bp(A) 返回地址4 过程B的AR 控制链：bp(C) 局部名字：j1

44 参数传递 实参与形参 － 存储单元（左值） － 存储内容（右值） 根据所传递的实参的“内容”，参数传递可分为：
－ 传值调用：传递实参的右值到形参单元； － 引用调用：传递实参的左值到形参单元； － 值-结果调用：传递实参的右值；在控制返回时将右值写回到实参相应左值单元（如果有的话）； － 换名调用：传递实参的“正文”。 2018/11/24 《编译原理与技术》－运行环境

45 e.g.8 参数传递 procedure swap( a , b ) a, b : int; temp : int; begin
temp := a ; a := b; b := temp; end. 讨论下面程序在不同参数传递方式下输出： 1) x := 10 ; y := 20; swap( x,y ); print ( x, y ); 2) i := 10; a[ i ] := 20; swap( i, a[ i ] ); print( i, a[ i ] ); 2018/11/24 《编译原理与技术》－运行环境

46 e.g.8 参数传递 讨论下面程序在不同参数传递方式下输出： 1) x := 10 ; y := 20; swap( x,y );
print ( x, y ); 5000: x 10 4000: y 20 2004: a 2000: b 1990: temp 实参x,y和过程swap中形参a,b,和局部数据temp的存储分布示意 2018/11/24 《编译原理与技术》－运行环境

47 e.g.8 参数传递－传值调用 过程调用－swap(x,y) 传参－形、实结合 5000: x 10 4000: y 20 2004: a
2000: b 20 1990: temp 2018/11/24 《编译原理与技术》－运行环境

48 e.g.8 参数传递－传值调用 过程调用－swap(x,y) 过程执行 temp := a 5000: x 10 4000: y 20
2000: b 20 1990: temp 10 2018/11/24 《编译原理与技术》－运行环境

49 e.g.8 参数传递－传值调用 过程调用－swap(x,y) 过程执行 a := b 5000: x 10 4000: y 20
1990: temp 10 2018/11/24 《编译原理与技术》－运行环境

50 e.g.8 参数传递－传值调用 过程调用－swap(x,y) 过程执行 b := temp 5000: x 10 4000: y 20
2018/11/24 《编译原理与技术》－运行环境

51 e.g.8 参数传递－传值调用 过程swap(x,y)执行后 print( x, y ) 10, 20 5000: x 10 4000: y
2004: 20 2000: 10 1990: 10 2018/11/24 《编译原理与技术》－运行环境

52 e.g.8 参数传递－引用调用 过程调用－swap(x,y) 传参－形、实结合 5000: x 10 4000: y 20 2004: a
2000: b 4000 1990: temp 2018/11/24 《编译原理与技术》－运行环境

53 e.g.8 参数传递－引用调用 过程调用－swap(x,y) 过程执行 temp := a 5000: x 10 4000: y 20
2000: b 4000 1990: temp 10 2018/11/24 《编译原理与技术》－运行环境

54 e.g.8 参数传递－引用调用 过程调用－swap(x,y) 过程执行 a := b 5000: x 10 4000: y 20
1990: temp 10 2018/11/24 《编译原理与技术》－运行环境

55 e.g.8 参数传递－引用调用 过程调用－swap(x,y) 过程执行 a := b 5000: x 20 4000: y 20
1990: temp 10 2018/11/24 《编译原理与技术》－运行环境

56 e.g.8 参数传递－引用调用 过程调用－swap(x,y) 过程执行 b := temp 5000: x 20 4000: y 10
2018/11/24 《编译原理与技术》－运行环境

57 e.g.8 参数传递－引用调用 过程swap(x,y)执行后 print( x, y ) 20, 10 5000: x 20 4000: y
2004: 2000: 1990: 2018/11/24 《编译原理与技术》－运行环境

58 e.g.9 参数传递 以下C程序的输出是什么？ void func(char *s){s = (char*)malloc(10);}
int main() { char *p = NULL; func(p); if(!p)printf("error\n");else printf("ok\n"); return 0; } 2018/11/24 《编译原理与技术》－运行环境

59 e.g.10.1 参数传递 swap void swap1(int p,int q) { int temp; temp = p; p = q; q = temp; } pushl %ebp movl %esp, %ebp subl $4, %esp movl 8(%ebp), %eax movl %eax, -4(%ebp) movl 12(%ebp), %eax movl %eax, 8(%ebp) movl -4(%ebp), %eax movl %eax, 12(%ebp) leave ret 2018/11/24 《编译原理与技术》－运行环境

60 e.g.10.2 参数传递 swap void swap2(int *p,int *q) { int temp; temp = *p; *p = *q; *q = temp; } pushl %ebp movl %esp, ebp subl $4, %esp movl 8(%ebp), %eax movl (%eax), %eax movl %eax, -4(%ebp) movl 8(%ebp), %edx movl 12(%ebp), %eax movl (%eax), %eax movl %eax, (%edx) movl 12(%ebp), %edx movl -4(%ebp), %eax movl %eax, (%edx) leave ret 2018/11/24 《编译原理与技术》－运行环境

61 e.g.10.3 参数传递 swap void swap3(int *p, int *q) { int *temp ; temp = p ; p = q ; q = temp; } pushl %ebp movl %esp, ebp subl $4, %esp movl 8(%ebp), %eax movl %eax, -4(%ebp) movl 12(%ebp), %eax movl %eax, 8(%ebp) movl -4(%ebp), %eax movl %eax, 12(%ebp) leave ret 2018/11/24 《编译原理与技术》－运行环境

62 e.g.10.4 参数传递 swap void swap4(int &p, int &q) { int temp; temp = p; p = q; q = temp; } pushl %ebp movl %esp,%ebp subl $4, %esp movl 8(%ebp), %eax movl (%eax), %eax movl %eax, -4(%ebp) movl 8(%ebp), %edx movl 12(%ebp), %eax movl (%eax), %eax movl %eax, (%edx) movl 12(%ebp), %edx movl -4(%ebp), %eax movl %eax, (%edx) leave ret 2018/11/24 《编译原理与技术》－运行环境