06-第6章-运行时存储空间的组织和管理-编译原理-中国科

编译原理和技术中国科学技术大学计算机科学与技术学院陈意云第六章运行时存储空间的组织和管理术语–过程的活动过程的一次执行称为过程的一次活动–活动记录过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录本章内容•讨论一个活动记录中的数据布局•程序执行过程中，所有活动记录的组织方式第六章运行时存储空间的组织和管理•影响存储分配策略的语言特征–过程能否递归–当控制从过程的活动返回时，局部变量的值是否要保留–过程能否访问非局部变量–过程调用的参数传递方式–过程能否作为参数被传递–过程能否作为结果值传递–存储块能否在程序控制下动态地分配–存储块是否必须显式地释放6.1局部存储分配6.1.1过程语言概念：过程定义、过程调用、形式参数、实在参数、活动的生存期6.1局部存储分配6.1.2名字的作用域和绑定1、名字的作用域•一个声明起作用的程序部分称为该声明的作用域•即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象6.1局部存储分配2、环境和状态•环境把名字映射到左值，而状态把左值映射到右值（即名字到值有两步映射）•赋值改变状态，但不改变环境•过程调用改变环境•如果环境将名字x映射到存储单元s，则说x被绑定到s名字存储单元状态值环境6.1局部存储分配3、静态概念和动态概念的对应静态概念动态对应过程的定义过程的活动6.1局部存储分配3、静态概念和动态概念的对应静态概念动态对应过程的定义过程的活动名字的声明名字的绑定6.1局部存储分配3、静态概念和动态概念的对应静态概念动态对应过程的定义过程的活动名字的声明名字的绑定声明的作用域绑定的生存期6.1局部存储分配6.1.3活动记录活动记录的常见布局返回值临时数据参数控制链访问链机器状态局部数据6.1局部存储分配6.1.4局部数据的布局•字节是可编址内存的最小单位•变量所需的存储空间可以根据其类型而静态确定•一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间•局部数据的地址可以用相对于活动记录中某个位置的地址来表示•数据对象的存储布局还有一个对齐问题6.1局部存储分配•例在SPARC/Solaris工作站上下面两个结构体的size分别是24和16，为什么不一样？typedefstruct_a{typedefstruct_b{charc1;charc1;longi;charc2;charc2;longi;doublef;doublef;}a;}b;对齐：char:1,long:4,double:86.1局部存储分配•例在SPARC/Solaris工作站上下面两个结构体的size分别是24和16，为什么不一样？typedefstruct_a{typedefstruct_b{charc1;0charc1;0longi;4charc2;1charc2;8longi;4doublef;16doublef;8}a;}b;对齐：char:1,long:4,double:86.1局部存储分配•例在X86/Linux机器的结果和SPARC/Solaris工作站不一样，是20和16。typedefstruct_a{typedefstruct_b{charc1;0charc1;0longi;4charc2;1charc2;8longi;4doublef;12doublef;8}a;}b;对齐：char:1,long:4,double:46.1局部存储分配6.1.5程序块•本身含有局部变量声明的语句•可以嵌套•最接近的嵌套作用域规则•并列程序块不会同时活跃•并列程序块的变量可以重叠分配6.1局部存储分配main()/例/{/beginofB0/inta=0;intb=0;{/beginofB1/intb=1;{/beginofB2/inta=2;}/endofB2/{/beginofB3/intb=3;}/endofB3/}/endofB1/}/endofB0/6.1局部存储分配main()/例/{/beginofB0/inta=0;intb=0;{/beginofB1/intb=1;{/beginofB2/inta=2;}/endofB2/{/beginofB3/intb=3;}/endofB3/}/endofB1/}/endofB0/声明作用域inta=0;B0B2intb=0;B0B1intb=1;B1B3inta=2;B2intb=3;B3a0b0b1a2,b3重叠分配存储单元6.2全局栈式存储分配本节介绍•介绍程序运行时所需的各个活动记录在存储空间的分配策略•描述过程的目标代码怎样访问绑定到局部名字的存储单元•介绍三种分配策略–静态分配策略–栈式分配策略–堆式分配策略6.2全局栈式存储分配6.2.1运行时内存的划分代码静态数据堆栈6.2全局栈式存储分配1、静态分配•名字在程序被编译时绑定到存储单元，不需要运行时的任何支持•绑定的生存期是程序的整个运行期间6.2全局栈式存储分配2、静态分配给语言带来限制•递归过程不被允许•数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的•数据结构不能动态建立6.2全局栈式存储分配•例C程序的外部变量、静态局部变量以及程序中出现的常量都可以静态分配•声明在函数外面–外部变量--静态分配–静态外部变量--静态分配•声明在函数里面–静态局部变量--也是静态分配–自动变量--不能静态分配6.2全局栈式存储分配6.2.2活动树和运行栈1、活动树–用树来描绘控制进入和离开活动的方式mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2全局栈式存储分配•活动树的特点–每个结点代表某过程的一个活动–根结点代表主程序的活动–结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动–结点a处于结点b的左边，当且仅当a的生存期先于b的生存期mq(1,9)rp(1,9)q(1,3)....q(5,9)....6.2全局栈式存储分配•当前活跃着的过程活动可以保存在一个栈中–例控制栈的内容：m,q(1,9),q(1,3),q(2,3)mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2全局栈式存储分配2、运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）6.2全局栈式存储分配2、运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）ma:arraym6.2全局栈式存储分配2、运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）mi:integerra:arraymr6.2全局栈式存储分配2、运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）mk:integerq(1,9)a:arraymq(1,9)r6.2全局栈式存储分配2、运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）mk:integerq(1,9)a:arrayq(1,3)k:integermq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)6.2全局栈式存储分配6.2.3调用序列•过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等•过程调用序列过程调用时执行的分配活动记录，把信息填入它的域中，使被调用过程可以开始执行的代码•过程返回序列被调用过程返回时执行的恢复机器状态，释放被调用过程活动记录，使调用过程能够继续执行的代码•调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中6.2全局栈式存储分配•即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异•设计这些序列和活动记录的一些原则–以活动记录中间的某个位置作为基地址–长度能较早确定的域放在活动记录的中间返回值临时数据参数控制链访问链机器状态局部数据6.2全局栈式存储分配•即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异•设计这些序列和活动记录的一些原则–一般把临时数据域放在局部数据域的后面–把参数域和可能有的返回值域放在紧靠调用者活动记录的地方返回值临时数据参数控制链访问链机器状态局部数据6.2全局栈式存储分配•即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异•设计这些序列和活动记录的一些原则–用同样的代码来执行各个活动的保存和恢复返回值临时数据参数控制链访问链机器状态局部数据6.2全局栈式存储分配1、过程p调用过程q的调用序列返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态6.2全局栈式存储分配1、过程p调用过程q的调用序列(1)p计算实参，依次放入栈顶，并在栈顶留出放返回值的空间。top_sp的值在此过程中被改变返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数top_sp6.2全局栈式存储分配1、过程p调用过程q的调用序列(2)p把返回地址和当前base_sp的值存入q的活动记录中，建立q的访问链，增加base_sp的值返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数控制链和返回地址base_sptop_sp6.2全局栈式存储分配1、过程p调用过程q的调用序列(3)q保存寄存器的值和其它机器状态信息返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数控制链和保存的机器状态6.2全局栈式存储分配1、过程p调用过程q的调用序列(4)q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体临时数据局部数据返回值和参数返回值和参数控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态6.2全局栈式存储分配调用者p和被调用者q之间的任务划分被调用者q的责任调用者p的责任调用者p的活动记录被调用者q的活动记录临时数据局部数据返回值和参数返回值和参数控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态6.2全局栈式存储分配2、过程p调用过程q的返回序列临时数据局部数据返回值和参数返回值和参数控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态6.2全局栈式存储分配2、过程p调用过程q的返回序列临时数据局部数据返回值和参数返回值和参数控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态(1)q把返回值置入邻近p的活动记录的地方参数个数可变场合难以确定存放返回值的位置，因此通常用寄存器传递返回值6.2全局栈式存储分配2、过程p调用过程q的返回序列(2)q对应调用序列的步骤(4)，减小top_sp的值返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数控制链和保存的机器状态6.2全局栈式存储分配2、过程p调用过程q的返回序列(3)q恢复寄存器(包括base_sp)和机器状态，返回p返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数6.2全局栈式存储分配2、过程p调用过程q的返回序列返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态(4)p根据参数个数与类型和返回值类型调整top_sp，然后取出返回值6.2全局栈式存储分配3、过程的参数个数可变的情况临时数据局部数据参数