《编译原理与技术 运行环境.ppt》由会员分享，可在线阅读，更多相关《编译原理与技术 运行环境.ppt（52页珍藏版）》请在三一文库上搜索。
1、2019/10/28,编译原理与技术运行环境,1,编译原理与技术,运行环境,2019/10/28,编译原理与技术运行环境,2,运行环境,存储组织与分配 程序单元、运行时内存划分与活动记录 静态/动态存储分配 动态栈式的过程调用/返回 非局部名字的访问 参数传递 参数传递的方式及其实现,2019/10/28,编译原理与技术运行环境,3,存储组织与分配,程序单元 FORTRAN的子例程(subroutine) PASCAL的过程/函数(procedure/function) C的函数 程序单元的激活（调用）与终止（返回） 程序单元的执行需要： 代码段活动记录（程序单元运行所需的额外信息，如参数，局
2、部数据，返回地址等）,2019/10/28,编译原理与技术运行环境,4,运行时内存划分,代码段,静态数据区,栈（stack）,堆（heap）,大小可以静态确定,全局/局部静态变量,活动记录栈,动态分配的数据,2019/10/28,编译原理与技术运行环境,5,活动记录,活动记录AR （Activation Record） 是一连续存储区域，用于管理与存放和程序单元执行相关的重要信息。 AR中的内容 临时区域。用以保存临时计算结果 局部数据区。源程序中程序单元声明的局部变量对应在此区域。 机器状态保存区。存有机器的寄存器，程序指令计数器 ip（返回地址）等。,2019/10/28,编译原理与技术运
3、行环境,6,活动记录,AR中的内容 访问链（静态链）。当前程序单元可以访问的（静态程序中）外围程序单元的活动记录链。 控制链（动态链）。程序单元的活动记录按它们的生成（或调用）次序串成链。 实在参数 返回值,2019/10/28,编译原理与技术运行环境,7,活动记录的内容,返回值（return value） 实在参数（actual parameter） 控制链（control link） 可选的访问链（optional access/static link） 机器状态（saved machine status） 局部数据（local data） 临时区（temporaries）,2019/10
4、/28,编译原理与技术运行环境,8,活动记录内容的存取,返回值 实在参数 控制链 （old bp） 可选的访问链 机器状态 局部数据 临时区,AR的基地址bp,2019/10/28,编译原理与技术运行环境,9,活动记录内容的存取,返回值 实在参数 控制链（old bp） 可选的访问链 机器状态 局部数据 临时区,bp,偏移,d1,偏移d2,地址： bp+d1,地址： bp+d2,d1、d2谁正谁负？,2019/10/28,编译原理与技术运行环境,10,静态存储分配, 全局变量的存储绑定、AR均在编译时确定 且在整个程序执行中保持。 不支持： 1）动态数据结构 2）过程递归调用 实现静态分配的语
5、言： （早期）FORTRAN,2019/10/28,编译原理与技术运行环境,11,CALL sub SUBROUTINE sub CALL sub DATA I/10 END WRITE(*.*) I I = 100 END 第一次调用sub，输出10 第二次调用sub，输出100,e.g.1 FORTRAN静态存储分配,第一次调用前,第一次调用后,第二次调用后,2019/10/28,编译原理与技术运行环境,12,动态存储分配,栈式分配 AR在过程被调用（激活）时才在栈（stack）上分配；而在被调用过程（返回）终止时从栈上撤销。 过程中（非静态）局部变量的存储绑定在过程执行时有效；过程终止时
6、失效。 支持过程递归调用。每次递归调用时，局部变量绑定到不同的存储。,2019/10/28,编译原理与技术运行环境,13,动态存储分配,栈式分配下的AR内容布局,返回值 实在参数 可选的访问链 返回地址 调用者 bp 可选机器状态 局部数据 临时区,bp,高地址,低地址,长度固定的区域放在AR中间,长度可变的区域放在AR低端,参数/返回值区域放在AR高端靠近调用者过程的活动记录，既便于双方存取，又适应参数可变情况,栈顶sp,2019/10/28,编译原理与技术运行环境,14,栈式分配下的过程调用与返回 过程调用：分配被调过程的AR并填入相关信息，然后程序控制转移到被调过程入口； 过程A 调用
7、过程B 的过程调用序列： A的“调用”准备操作：1） 3） 1）A 计算实在参数并放入（对应栈操作push） B的活动记录中；（亦可考虑返回值存放空间） 2）A将可选的访问链放入（push）B的活动记录； 3）A将返回地址放入B的活动记录并跳转到过程B 的代码入口，开始B的执行；（一般通过A中的 代码指令“call B” 来完成这一步） 4）,2019/10/28,编译原理与技术运行环境,15,栈式分配下的过程调用与返回 过程A 调用 过程B 的过程调用序列： B的入口代码：4） 6） 4）在B自己的AR中保存A的活动记录的基址（即当前bp，对应操作 push bp）并且将这个位置作为B自己A
8、R的基址（对应操作） mov sp,bp 即 bpsp） 5）保存可选的机器状态（寄存器） 6）为局部数据分配空间，（对应操作） sub local_size，sp，即sp sp local_size 7）“开始”B的执行。（至此，B的AR建好）,2019/10/28,编译原理与技术运行环境,16,栈式分配下的过程调用与返回 过程返回：回收分配的被调过程的AR，并将程序控制转移回调用过程继续执行； 过程A 调用 过程B 的过程返回序列： B的出口代码：1） 2） 1）B回收局部数据空间；恢复原先保存的机器状态2）B恢复A的AR基址；取出返回地址将程序控制交回到A。对应操作： mov bp,sp
9、 spbp pop bp /恢复调用者A的bp ret / B执行结束并返回 注：X86-Linux中的leave 和ret组合亦能达到目的。 至此，B的AR中除了参数/返回值区域，其余区域全部回收（撤销）了。,2019/10/28,编译原理与技术运行环境,17,栈式分配下的过程调用与返回 过程A 调用 过程B 的过程返回序列： A的“调用”善后代码：3） 4） 3）A取回返回值以及引用型参数（有的话） 4）A调整栈顶sp（主要根据参数个数以及可能有的访问链和可能有的返回值）。对应操作： add para_size, sp 即spsp + para_size 至此，B的AR区域全部回收（撤销）
10、了。,2019/10/28,编译原理与技术运行环境,18,e.g.2 栈式存储分配,有C程序如下： void g() int a ; a = 10 ; void h() int a ; a = 100; g(); main() int a = 1000; h(); ,2019/10/28,编译原理与技术运行环境,19,过程g被调用时，活动记录栈的（大致）内容,e.g.2 栈式存储分配,返回地址,old bp,a : 1000,main程序的AR,返回地址,old bp,a : 100,函数h的AR,返回地址,old bp,a : 10,函数g的AR,bp,sp,2019/10/28,编译原理与
11、技术运行环境,20,e.g.3 有参函数的活动记录,void func( int a , int b ) int c , d; c = a; d = b; ,bp,bp+8,bp+12,bp4,bp8,.file “ar.c“ .text .globl func .type func,function 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,2019/10/28,编
12、译原理与技术运行环境,21,有如下C程序： main() int i ; float f; int j ; scanf(“%d%f”, ,e.g.4. scanf的可变参数,2019/10/28,编译原理与技术运行环境,22,e.g.4. scanf的可变参数,&f,&i,格式串1指针,返回地址,老bp,&j,格式串2指针,返回地址,老bp,scanf的第一次调用时AR,scanf的第二次调用时AR,由于C语言采用逆序传递参数，格式串参数将被放在AR中的“固定”位置，即bp+8。而由此参数即可确定待输入值的参数（变量）的个数。从而适应参数个数变化的情况。,bp,bp+8,2019/10/28,
13、编译原理与技术运行环境,23,e.g.5 悬空引用,有C程序如下： main() int * dangle() int * p = dangle(); int i; return ,2019/10/28,编译原理与技术运行环境,24,非局部变量访问,静态作用域规则 vs. 动态作用域规则 “最接近嵌套” vs. 现行单元活动（调用次序） 分程序 含有声明和语句；如C的 分程序具有以下特征： - 可以嵌套； - 没有参数； - 控制流沿静态文本进入、流出 - 采用“最接近嵌套”的规则,2019/10/28,编译原理与技术运行环境,25,非局部变量访问,e.g.6 分程序 main() int a
14、 = 0 ; int b =0; /local VAR of main int b = 1 ; / block 1 int a = 2 ; printf(“%d %dn”,a,b);/block 2 int b = 3 ; printf(“%d %dn”,a,b);/block 3 printf(“%d %dn”,a,b); printf(“%d %dn”,a,b); ,2019/10/28,编译原理与技术运行环境,26,分程序的实现,1）按无参过程方式来实现 控制流进入分程序时，在栈上分配局部变量空间 ，退出时撤销上述空间。e.g.6中各变量存储如下：,a0 = 0,b0 = 0,b1 =
15、1,a）进入block 1, 未进入block 2,b）进入block 2, 未进入block 3,a1 = 2,a0 = 0,b0 = 0,b1 = 1,c）退出block 2, 进入block 3,b2 = 3,a0 = 0,b0 = 0,b1 = 1,d）退出block 3, 进入block 1,a0 = 0,b0 = 0,b1 = 1,e）退出block 1, 进入main,a0 = 0,b0 = 0,2019/10/28,编译原理与技术运行环境,27,分程序的实现,2）按过程为单位统一分配 将分程序中的局部变量独立地看成过程的局部变量。e.g.6中各变量存储如下： （两种方案）,a0
16、 = 0,b0 = 0,b1 = 1,a）a1和b2将先后被分配在同一空间，因为它们的生存期（作用域）不重叠、不嵌套。,a1 = 2, b2 = 3,a0 = 0,b0 = 0,b1 = 1,b）a1和b2将被分配在不同的空间。,a1 = 2,b2 = 3,2019/10/28,编译原理与技术运行环境,28,program dynamic_static_link; procedure A ; var i : integer ; procedure B ; var j : integer; procedure C ; begin B; end; begin j := i; C ; end; be
17、gin B ; end; begin A ; end.,过程嵌套定义语言中非局部名字访问,C,B,A,主程序,主程序 : 0,A：1,B：2,C：3,i： 2,j： 3,嵌套深度：1,嵌套深度：2,嵌套深度：3,嵌套深度：4,e.g.7 嵌套的过程定义,2019/10/28,编译原理与技术运行环境,29,过程嵌套定义语言中非局部名字访问,设嵌套深度的初值为0。在“读过”程序单元的名字后，进入程序单元过程或函数时嵌套深度加1。 任何名字（包括变量名和程序单元过程或函数的名字）的嵌套深度是包围该名字声明或定义的最内层的程序单元体（body）所在的嵌套深度。 过程或函数的参数与其局部声明的嵌套深度相
18、同。,2019/10/28,编译原理与技术运行环境,30,使用静态访问链来存取非局部名字 非局部变量a的嵌套深度为na ，而该变量的使用或引用点的嵌套深度为np： 沿当前过程或函数的访问链追踪|np - na|次，即可到达包含变量a的过程或函数的活动记录；进一步可存取变量a。运行时栈上操作如下： 1）（bp + 访问链单元的偏移） Reg /追踪1次 2）（Reg + 访问链单元的偏移） Reg /追踪2次 / 追踪（np na）次 最后， 通过 （Reg + 变量a的偏移）来存取变量a （局部变量访问无需追踪访问链！） e.g.7中下划线部分：j := i 为非局部名字i的一个引用（j为局部
19、变量）。为此，需要追踪过程B的访问链1次即可到达过程A的AR从而获取i的值。 由定义非局部变量a的过程或函数（名）的嵌套深度，以及由使用该变量的过程或函数（名）的嵌套深度，也能计算出追踪访问链的次数（why？）,2019/10/28,编译原理与技术运行环境,31,过程嵌套定义语言中非局部名字访问,访问链的建立 在嵌套深度为np的过程X调用嵌套深度为na的过程Y： 1）npna 此时 np na 1 ;即调用者X是父（即最接近的外围）过程，而被调者Y为其子过程，这时将过程Y的AR中的访问链置为X的AR的基址对应的运行时栈的操作： push bp / 调用者（父过程）将自己的bp压入栈,2019/
20、10/28,编译原理与技术运行环境,32,过程嵌套定义语言中非局部名字访问,访问链的建立 2）npna 这属于内层过程X调用外围过程Y；或者两个兄弟过程X、Y之间的调用（也可能是相同过程，即递归的情况）。这时由X的AR追踪访问链（np na + 1）次，即可到达嵌套深度为（na 1） 的过程Z的AR；显然，过程Z是过程Y的父过程，将这个Z的AR的基址填入Y的访问链域。对应运行时栈上的操作： 1）（bp + 访问链单元的偏移） Reg /追踪1次 2）（Reg + 访问链单元的偏移） Reg /追踪2次 / 追踪（np na + 1）次 最后， push Reg /过程Z的活动记录基址入栈,20
21、19/10/28,编译原理与技术运行环境,33,e.g.7 嵌套的过程定义,过程的调用次序 主程序 A B C B1 过程B第一次被过程C调用时，C需追踪2次访问链才能为找到过程B1的父过程A的AR。 具体如下：,2019/10/28,编译原理与技术运行环境,34,控制链：bp(系统),主程序AR,e.g.7 嵌套的过程定义,运行时栈：主程序,2019/10/28,编译原理与技术运行环境,35,控制链：bp(系统),访问链：bp(main),返回地址1,控制链：bp(main),局部名字：i,主程序AR,过程A的AR,e.g.7 嵌套的过程定义,运行时栈：主程序 A 主程序负责建立A（活动记录
22、中）的访问链。此时该链指向主程序运行时的活动记录（why？）。此访问链的位置（或偏移）是多少？,访问链的地址表示： bp + 8 在此活动记录中的偏移为8,2019/10/28,编译原理与技术运行环境,36,控制链：bp(系统),访问链：bp(main),返回地址1,控制链：bp(main),访问链：bp(A),返回地址2,控制链：bp(A),局部名字：i,局部名字：j0,主程序AR,过程A的AR,过程B的AR,e.g.7 嵌套的过程定义,运行时栈：主程序 A B B中语句j := i如何执行的？,j := i执行如下： 取过程A的活动记录地址： (bp + 8) - R 取A中局部变量i的值
23、： (R 4 ) - R 将该值赋给B的局部变量j： R - (bp 4),2019/10/28,编译原理与技术运行环境,37,控制链：bp(系统),访问链：bp(main),返回地址1,控制链：bp(main),访问链：bp(A),返回地址2,控制链：bp(A),局部名字：i,局部名字：j0,访问链：bp(B),返回地址3,控制链：bp(B),主程序AR,过程A的AR,过程B的AR,过程C的AR,运行时栈：主程序 A B C,控制链：bp(系统),访问链：bp(main),返回地址1,控制链：bp(main),访问链：bp(A),返回地址2,控制链：bp(A),局部名字：i,局部名字：j0,
24、访问链：bp(B),返回地址3,控制链：bp(B),访问链：bp(A),返回地址4,控制链：bp(C),局部名字：j1,主程序AR,过程A的AR,过程B的AR,过程C的AR,过程B的AR,1,2,运行时栈： 主程序 A B C B1,过程C为过程B1 建立访问链： 1： (bp+8)R 2：(R+8)R 3： push R,2019/10/28,编译原理与技术运行环境,39,参数传递,实参与形参 存储单元（左值） 存储内容（右值） 根据所传递的实参的“内容”，参数传递可分为： 传值调用：传递实参的右值到形参单元； 引用调用：传递实参的左值到形参单元； 值-结果调用：传递实参的右值；在控制返回时
25、将右值写回到实参相应左值单元（如果有的话）； 换名调用：传递实参的“正文”。,2019/10/28,编译原理与技术运行环境,40,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 );,2019/10
26、/28,编译原理与技术运行环境,41,e.g.8 参数传递,讨论下面程序在不同参数传递方式下输出： 1) x := 10 ; y := 20; swap( x,y ); print ( x, y );,10,5000: x,20,4000: y,2004: a,2000: b,1990: temp,实参x,y和过程swap中形参a,b,和局部数据temp的存储分布示意,2019/10/28,编译原理与技术运行环境,42,e.g.8 参数传递传值调用,过程调用swap(x,y) 传参形、实结合,10,5000: x,20,4000: y,2004: a,2000: b,1990: temp,10
27、,20,2019/10/28,编译原理与技术运行环境,43,e.g.8 参数传递传值调用,过程调用swap(x,y) 过程执行 temp := a,10,5000: x,20,4000: y,10,2004: a,20,2000: b,10,1990: temp,2019/10/28,编译原理与技术运行环境,44,e.g.8 参数传递传值调用,过程调用swap(x,y) 过程执行 a := b,10,5000: x,20,4000: y,20,2004: a,20,2000: b,10,1990: temp,2019/10/28,编译原理与技术运行环境,45,e.g.8 参数传递传值调用,过程
28、调用swap(x,y) 过程执行 b := temp,10,5000: x,20,4000: y,20,2004: a,10,2000: b,10,1990: temp,2019/10/28,编译原理与技术运行环境,46,e.g.8 参数传递传值调用,过程swap(x,y)执行后 print( x, y ) 10, 20,10,5000: x,20,4000: y,20,2004:,10,2000:,10,1990:,2019/10/28,编译原理与技术运行环境,47,e.g.8 参数传递引用调用,过程调用swap(x,y) 传参形、实结合,10,5000: x,20,4000: y,2004
29、: a,2000: b,1990: temp,5000,4000,2019/10/28,编译原理与技术运行环境,48,e.g.8 参数传递引用调用,过程调用swap(x,y) 过程执行 temp := a,10,5000: x,20,4000: y,2004: a,2000: b,1990: temp,5000,4000,10,2019/10/28,编译原理与技术运行环境,49,e.g.8 参数传递引用调用,过程调用swap(x,y) 过程执行 a := b,10,5000: x,20,4000: y,2004: a,2000: b,10,1990: temp,5000,4000,2019/1
30、0/28,编译原理与技术运行环境,50,e.g.8 参数传递引用调用,过程调用swap(x,y) 过程执行 a := b,20,5000: x,20,4000: y,2004: a,2000: b,10,1990: temp,5000,4000,2019/10/28,编译原理与技术运行环境,51,e.g.8 参数传递引用调用,过程调用swap(x,y) 过程执行 b := temp,20,5000: x,10,4000: y,2004: a,2000: b,10,1990: temp,5000,4000,2019/10/28,编译原理与技术运行环境,52,e.g.8 参数传递引用调用,过程swap(x,y)执行后 print( x, y ) 20, 10,20,5000: x,10,4000: y,2004:,2000:,1990:,