编译原理与技术运行环境2024/7/251编译原理与技术运行环境运行环境存储组织与分配 程序单元、运行时内存划分与活动记录 静态/动态存储分配 动态栈式的过程调用/返回 非局部名字的访问参数传递 参数传递的方式及其实现2024/7/252编译原理与技术运行环境存储组织与分配程序单元FORTRAN的子例程(subroutine)PASCAL的过程/函数(procedure/function)C的函数程序单元的激活（调用）与终止（返回）程序单元的执行需要：代码段活动记录（程序单元运行所需的额外信息，如参数，局部数据，返回地址等）2024/7/253编译原理与技术运行环境运行时内存划分代码段静态数据区栈（stack） 堆（heap） 大小可以静态确定全局/局部静态变量活动记录栈动态分配的数据2024/7/254编译原理与技术运行环境活动记录活动记录AR （Activation Record）是一连续存储区域，用于管理与存放和程序单元执行相关的重要信息。AR中的内容 临时区域。用以保存临时计算结果 局部数据区。源程序中程序单元声明的局部变量对应在此区域。 机器状态保存区。存有机器的寄存器，程序指令计数器 ip（返回地址）等。2024/7/255编译原理与技术运行环境活动记录AR中的内容 访问链（静态链）。当前程序单元可以访问的（静态程序中）外围程序单元的活动记录链。 控制链（动态链）。程序单元的活动记录按它们的生成（或调用）次序串成链。 实在参数 返回值2024/7/256编译原理与技术运行环境活动记录的内容返回值（return value）实在参数（actual parameter）控制链（control link）可选的访问链可选的访问链（optional access/static link）机器状态（saved machine status）局部数据（local data）临时区（temporaries）2024/7/257编译原理与技术运行环境活动记录内容的存取返回值 实在参数 控制链 （old bp）可选的访问链可选的访问链 机器状态 局部数据 临时区 AR的基地址bp2024/7/258编译原理与技术运行环境活动记录内容的存取返回值 实在参数 控制链（old bp） 可选的访问链可选的访问链 机器状态 局部数据 临时区 bp偏移d1偏移d2地址： bp+d1地址： bp+d2d1、d2谁正谁负？2024/7/259编译原理与技术运行环境静态存储分配 全局变量的存储绑定、AR均在编译时确定且在整个程序执行中保持。 不支持：1）动态数据结构2）过程递归调用 实现静态分配的语言：（早期）FORTRAN2024/7/2510编译原理与技术运行环境CALL sub SUBROUTINE subCALL sub DATA I/10END WRITE(*.*) I I = 100 END第一次调用第一次调用sub，输出，输出10 第二次调用第二次调用sub，输出，输出100e.g.1 FORTRAN静态存储分配机器状态I （ 10 ）机器状态I （ 100 ）第一次调用前第一次调用后机器状态I （ 100 ）第二次调用后2024/7/2511编译原理与技术运行环境动态存储分配栈式分配 AR在过程被调用（激活）时才在栈（stack）上分配；而在被调用过程（返回）终止时从栈上撤销。 过程中（非静态）局部变量的存储绑定在过程执行时有效；过程终止时失效。 支持过程递归调用。每次递归调用时，局部变量绑定到不同的存储。2024/7/2512编译原理与技术运行环境动态存储分配栈式分配下的AR内容布局返回值 实在参数 可选的访问链可选的访问链 返回地址调用者 bp可选机器状态局部数据 临时区 bp高地址高地址低地址低地址长度固定的区长度固定的区域放在域放在ARAR中间中间长度可变的区域放在AR低端参数参数/返回值区域放在返回值区域放在AR高端靠近调用者过程的高端靠近调用者过程的活动记录，既便于双方存活动记录，既便于双方存取，又适应取，又适应参数可变参数可变情况情况栈顶sp2024/7/2513编译原理与技术运行环境栈式分配下的过程调用与返回 过程调用：分配被调过程的AR并填入相关信息，然后程序控制转移到被调过程入口；过程A 调用调用 过程B 的过程调用序列：A的“调用”准备准备操作：1） 3）1）A 计算计算实在参数并放入（对应栈操作push）B的活动记录中；（亦可考虑返回值存放空间）2）A将可选的访问链放入（push）B的活动记录；3）A将返回地址放入B的活动记录并跳转到过程B的代码入口，开始B的执行；（一般通过（一般通过A中的中的代码指令代码指令“call B” B” 来完成这一步）来完成这一步）4）2024/7/2514编译原理与技术运行环境栈式分配下的过程调用与返回 过程A 调用调用 过程B 的过程调用序列：B的入口代码：4） 6）4）在B自己的AR中保存A的活动记录的基址（即当前bp，对应操作 push bp）并且将这并且将这个位置作为个位置作为B自己自己AR的基址的基址（对应操作） mov sp,bp 即即 bpsp）5）保存可选的机器状态（寄存器）6）为局部数据分配空间，（对应操作） sub local_size，sp，即sp sp local_size7）“开始”B的执行。（至此，B的AR建好）2024/7/2515编译原理与技术运行环境栈式分配下的过程调用与返回 过程返回：回收分配的被调过程的AR，并将程序控制转移回调用过程继续执行；过程A 调用调用 过程B 的过程返回序列：B的出口代码：1） 2）1）B回收局部数据空间；恢复原先保存的机器状态2）B恢复A的AR基址；取出返回地址将程序控制交回到A。对应操作：mov bp,sp spbppop bp /恢复调用者A的bpret / B执行结束并返回注：X86-Linux中的leave 和ret组合亦能达到目的。至此，B的AR中除了参数/返回值区域，其余区域全部回收（撤销）了。2024/7/2516编译原理与技术运行环境栈式分配下的过程调用与返回 过程A 调用调用 过程B 的过程返回序列：A的“调用”善后代码：3） 4）3）A取回返回值以及引用型参数（有的话）4）A调整栈顶sp（主要根据参数个数以及可能有的访问链和可能有的返回值）。对应操作：add para_size, sp 即spsp + para_size至此，B的AR区域全部回收（撤销）了。2024/7/2517编译原理与技术运行环境e.g.2 栈式存储分配 有C程序如下：void g() int a ; a = 10 ; void h() int a ; a = 100; g(); main() int a = 1000; h(); 2024/7/2518编译原理与技术运行环境过程g被调用时，活动记录栈的（大致）内容e.g.2 栈式存储分配返回地址返回地址old bpa : 1000main程序的程序的AR返回地址返回地址old bpa : 100 函数函数h的的AR返回地址返回地址old bpa : 10 函数函数g的的ARbpsp2024/7/2519编译原理与技术运行环境e.g.3 有参函数的活动记录void func( int a , int b ) int c , d; c = a; d = b;bpbp+8bp+12bp4bp8参数参数 b b参数参数 a a返回地址返回地址老老bpbp局部变量局部变量c c局部变量局部变量d d.file ar.c .text.globl func .type func,functionfunc: 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 2024/7/2520编译原理与技术运行环境有如下C程序：main() int i ; float f; int j ; scanf(“%d%f”, &i, &f); /第一次调用时3个参数 scanf(“%d”, &j ); /第二次调用时 2个参数 return 0; e.g.4. scanf的可变参数2024/7/2521编译原理与技术运行环境e.g.4. scanf的可变参数&f&i格式串1指针返回地址老bp&j格式串2指针返回地址老bpscanf的第一次调用时ARscanf的第二次调用时AR由于C语言采用逆序逆序传递参数，格式串参数将被放在AR中的“固定”位置，即bp+8。而由此参而由此参数即可确定待输数即可确定待输入值的参数（变入值的参数（变量）的个数量）的个数。从而适应参数个数变化的情况。bpbp+82024/7/2522编译原理与技术运行环境e.g.5 悬空引用有C程序如下：main()int * dangle()int * p = dangle();int i;return &i;2024/7/2523编译原理与技术运行环境非局部变量访问静态作用域规则 vs. 动态作用域规则“最接近嵌套” vs. 现行单元活动（调用次序）分程序 含有声明和语句；如C的 分程序具有以下特征：- 可以嵌套；- 没有参数；- 控制流沿静态文本进入、流出- 采用“最接近嵌套”的规则2024/7/2524编译原理与技术运行环境非局部变量访问e.g.6 分程序main() int a = 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);2024/7/2525编译原理与技术运行环境分程序的实现1）按无参过程方式来实现控制流进入分程序时，在栈上分配局部变量空间，退出时撤销上述空间。e.g.6中各变量存储如下：a0 = 0b0 = 0b1 = 1a）进入block 1, 未进入block 2b）进入block 2,未进入block 3a1 = 2a0 = 0b0 = 0b1 = 1c）退出block 2, 进入block 3b2 = 3a0 = 0b0 = 0b1 = 1d）退出block 3, 进入block 1a0 = 0b0 = 0b1 = 1e）退出block 1, 进入maina0 = 0b0 = 02024/7/2526编译原理与技术运行环境分程序的实现2）按过程为单位统一分配将分程序中的局部变量独立地看成过程的局部变量。e.g.6中各变量存储如下： （两种方案）a0 = 0b0 = 0b1 = 1a）a1和b2将先后被分配在先后被分配在同一空间同一空间，因为它们的生存期（作用域）不重叠、不嵌套。 a1 = 2, b2 = 3a0 = 0b0 = 0b1 = 1b）a1和b2将被分配在不同不同的空间的空间。a1 = 2 b2 = 32024/7/2527编译原理与技术运行环境program dynamic_static_link; procedure A ; var i : integer ; procedure B ; var j : integer; procedure C ; begin B; end; begin j := i; C ; end; begin B ; end;begin A ;end.过程嵌套定义语言中非局部名字访问CBA主程序主程序主程序主程序 : 0A：1B：2C：3i： 2j： 3 嵌套深度：嵌套深度：1嵌套深度：嵌套深度：2 嵌套深度：嵌套深度：3 嵌套深度：嵌套深度：4e.g.7 嵌套的过程定义2024/7/2528编译原理与技术运行环境过程嵌套定义语言中非局部名字访问设嵌套深度的初值为0。在“读过”程序单元程序单元的名字后，的名字后，进入程序单元过程或函数时嵌套深度加1。任何名字（包括变量名和程序单元过程或函数的名字）的嵌套深度是包围该名字声明或定义的最内层的程序单元体最内层的程序单元体（body）所在的嵌套深度。过程或函数的参数与其局部声明的嵌套深度相同。2024/7/2529编译原理与技术运行环境使用静态访问链来存取非局部名字使用静态访问链来存取非局部名字非局部变量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为局部变量）。为此，需要追踪过程B的访问链1次次即可到达过程A的AR从而获取i的值。由定义非局部变量a的过程或函数（名）的嵌套深度，以及由使用该变量的过程或函数（名）的嵌套深度，也能计算出追踪访问链的次数（why？）2024/7/2530编译原理与技术运行环境过程嵌套定义语言中非局部名字访问访问链的建立在嵌套深度为np的过程X调用调用嵌套深度为na的过程Y：1）npna 此时 np na 1 ;即调用者X是父（即最接近的外围）过程，而被调者Y为其子过程，这时将过程Y的AR中的访问链置为X的AR的基址对应的运行时栈的操作：push bp / 调用者（父过程）将自己的bp压入栈2024/7/2531编译原理与技术运行环境过程嵌套定义语言中非局部名字访问访问链的建立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的活动记录基址入栈2024/7/2532编译原理与技术运行环境e.g.7 嵌套的过程定义过程的调用次序主程序 A B C B1 过程B第一次第一次被过程C调用时，C需追踪2次访问链才能为找到过程B1的父过程A的AR。具体如下：2024/7/2533编译原理与技术运行环境控制链：控制链：bp(系统系统)主程序主程序ARe.g.7 嵌套的过程定义运行时栈：主程序2024/7/2534编译原理与技术运行环境控制链：控制链：bp(系统系统)访问链：访问链：bp(main)返回地址返回地址1控制链：控制链：bp(main)局部名字：局部名字：i主程序主程序AR过程过程A的的ARe.g.7 嵌套的过程定义运行时栈：主程序 A 主程序负责建立A（活动记录中）的访问链。此时该链指向主程序运行时的活动记录（why？）。此访问链的位置（或偏移）是多少？访问链的地址表示：bp + 8在此活动记录中的偏移为8 2024/7/2535编译原理与技术运行环境控制链：控制链：bp(系统系统)访问链：访问链：bp(main)返回地址返回地址1控制链：控制链：bp(main)访问链：访问链：bp(A)返回地址返回地址2控制链：控制链：bp(A)局部名字：局部名字：i局部名字：局部名字：j0主程序主程序AR过程过程A的的AR过程过程B的的ARe.g.7 嵌套的过程定义运行时栈：主程序 A BB中语句中语句j := i如何执行的？如何执行的？j := i执行如下：取过程A的活动记录地址：(bp + 8) - R取A中局部变量i的值：(R 4 ) - R将该值赋给B的局部变量j：R - (bp 4)2024/7/2536编译原理与技术运行环境控制链：控制链：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 2024/7/2537编译原理与技术运行环境控制链：控制链：bp(系统系统)访问链：访问链：bp(main)返回地址返回地址1控制链：控制链：bp(main)访问链：访问链：bp(A)返回地址返回地址2控制链：控制链：bp(A)局部名字：局部名字：i局部名字：局部名字：j0访问链：访问链：bp(B)返回地址返回地址3控制链：控制链：bp(B)访问链：访问链：bp(A)返回地址返回地址4控制链：控制链：bp(C)局部名字：局部名字：j1主程序主程序AR过程过程A的的AR过程过程B的的AR过程过程C的的AR过程过程B的的AR12运行时栈：主程序 A B C B1 过程C为过程B1建立访问链：1： (bp+8)R 2：(R+8)R3： push R参数传递实参与形参 存储单元（左值）存储单元（左值） 存储内容（右值）存储内容（右值）根据所传递的实参的“内容”，参数传递可分为： 传值调用：传递实参的右值到形参单元； 引用调用：传递实参的左值到形参单元； 值-结果调用：传递实参的右值；在控制返回时将右值写回到实参相应左值单元（如果有的话）； 换名调用：传递实参的“正文”。2024/7/2539编译原理与技术运行环境e.g.8 参数传递procedure swap( a , b )a, b : int; temp : int;begintemp := 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 );2024/7/2540编译原理与技术运行环境e.g.8 参数传递 讨论下面程序在不同参数传递方式下输出：1) x := 10 ; y := 20;swap( x,y ); print ( x, y );105000: x204000: y 2004: a 2000: b 1990: temp实参x,y和过程swap中形参a,b,和局部数据temp的存储分布示意2024/7/2541编译原理与技术运行环境e.g.8 参数传递传值调用 过程调用swap(x,y)传参形、实结合105000: x204000: y 2004: a 2000: b 1990: temp10202024/7/2542编译原理与技术运行环境e.g.8 参数传递传值调用 过程调用swap(x,y)过程执行temp := a105000: x204000: y10 2004: a20 2000: b101990: temp2024/7/2543编译原理与技术运行环境e.g.8 参数传递传值调用 过程调用swap(x,y)过程执行a := b105000: x204000: y20 2004: a20 2000: b101990: temp2024/7/2544编译原理与技术运行环境e.g.8 参数传递传值调用 过程调用swap(x,y)过程执行b := temp105000: x204000: y20 2004: a10 2000: b101990: temp2024/7/2545编译原理与技术运行环境e.g.8 参数传递传值调用 过程swap(x,y)执行后print( x, y ) 10, 20105000: x204000: y20 2004: 10 2000: 10 1990: 2024/7/2546编译原理与技术运行环境e.g.8 参数传递引用调用 过程调用swap(x,y)传参形、实结合105000: x204000: y 2004: a 2000: b 1990: temp500040002024/7/2547编译原理与技术运行环境e.g.8 参数传递引用调用 过程调用swap(x,y)过程执行temp := a105000: x204000: y 2004: a 2000: b 1990: temp50004000102024/7/2548编译原理与技术运行环境e.g.8 参数传递引用调用 过程调用swap(x,y)过程执行a := b105000: x204000: y 2004: a 2000: b101990: temp500040002024/7/2549编译原理与技术运行环境e.g.8 参数传递引用调用 过程调用swap(x,y)过程执行a := b205000: x204000: y 2004: a 2000: b101990: temp500040002024/7/2550编译原理与技术运行环境e.g.8 参数传递引用调用 过程调用swap(x,y)过程执行b := temp205000: x104000: y 2004: a 2000: b101990: temp500040002024/7/2551编译原理与技术运行环境e.g.8 参数传递引用调用 过程swap(x,y)执行后print( x, y ) 20, 10205000: x104000: y2004: 2000: 1990: 2024/7/2552编译原理与技术运行环境