编译原理运行时环境

第7章运行时环境machunyan西北工业大学软件与微电子学院1第7章运行时环境(存储空间)当源程序的目标代码被运行时，在内存中不仅有目标代码，而且还要保存各种信息例如为源程序中出现的一些量（常量、变量及某些数组等）分配运行时的存储空间。目标代码要从操作系统得到一块存储区，用于它的运行。第7章运行时环境machunyan西北工业大学软件与微电子学院2存储分配是在运行阶段进行的，但编译程序在编译阶段要为其设计好存储组织形式，并将这种组织形式通过生成的目标代码体现出来。(举例说明：函数调用分析.txt)目标代码运行时，存储空间的组织称为目标代码的运行时环境。第7章运行时环境(存储空间)(续)第7章运行时环境machunyan西北工业大学软件与微电子学院3运行时环境有三个类型：完全静态环境(fullystaticenvironment)、基于栈的环境(stack-basedenvironment)，以及完全动态环境(fullydynamicenvironment)。这3种类型的混合形式也是可能的。第7章运行时环境(存储空间)(续)第7章运行时环境machunyan西北工业大学软件与微电子学院47.1程序执行时的存储器组织7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制7.2完全静态的运行时环境第7章运行时环境(存储空间)第7章运行时环境machunyan西北工业大学软件与微电子学院57.1程序执行时的存储器组织目标代码运行时,操作系统为目标代码的运行分配的存储空间按用途可划分为下面几个部分:由于栈区和堆区的长度会随着目标代码的运行而变化，因此把它们分配在数据区的两端。一般情况下，栈向下长，堆向上长，可以使栈和堆共用一空白存储空间。第7章运行时环境machunyan西北工业大学软件与微电子学院67.1程序执行时的存储器组织（续）代码区域：目标代码的存储区域，由于代码区在执行之前是固定的，在编译时所有目标代码的地址都是可计算的，程序执行结束后代码区域内存由系统释放。全程/静态区域：静态数据区用来存放那些具有绝对地址的数据和变量(如静态变量和全程变量)；编译器可以确定其所占用存储空间的大小，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域，程序执行结束后由系统释放。本章案例分析.doc第7章运行时环境7.1程序执行时的存储器组织（续）栈区：函数中的形参和在函数中定义的局部变量以及局部临时变量（C、C++、Java），这些变量分配在栈区，每次函数执行的时候会在栈中为函数的执行分配相应的存储区，而在函数执行完毕后，释放相应的存储区。编译器“知道”存在栈中的具体数据所占内存大小和内存分配和释放的“时刻”；machunyan西北工业大学软件与微电子学院7第7章运行时环境堆区：供用户动态申请存储空间，编译器“不需要”知道究竟得从heap中分配多少空间，也不需要知道从heap上分配的空间究竟需要存在多久。在c中由malloc，free运算产生释放的存储空间，在c++中由new和delete运算符作用的存储空间，以及在Java中由new分配的存储空间都在堆中进行分配。machunyan西北工业大学软件与微电子学院87.1程序执行时的存储器组织（续）第7章运行时环境machunyan西北工业大学软件与微电子学院9第7章运行时环境machunyan西北工业大学软件与微电子学院10第7章运行时环境machunyan西北工业大学软件与微电子学院117.1程序执行时的存储器组织（续）在C语言中,采用以函数（或过程）为单位的动态存储分配方案：当一函数被调用时，就在栈顶为该函数分配所需的数据空间(过程活动记录)，当一个函数工作完毕返回时，它在栈顶的数据空间(过程活动记录)也即释放。过程的活动记录(activationrecord,AR)是一段连续的存储区，用于存放函数的一次执行所需要的信息，当调用或激活函数时，必须为被调用函数的活动记录分配空间。第7章运行时环境活动记录存放的信息至少应包括以下几个部分：machunyan西北工业大学软件与微电子学院12存放主调函数为被调函数提供的实参信息;存放目标程序临时变量的值;存放本次执行中的局部数据用于指向主调函数的活动记录的控制链和返回地址;7.1程序执行时的存储器组织（续）第7章运行时环境machunyan西北工业大学软件与微电子学院137.1程序执行时的存储器组织（续）实参返回地址控制链临时变量和局部数据实参返回地址控制链临时变量和局部数据调用者的活动记录被调用者的活动记录调用者的职责第7章运行时环境C语言所调用函数的活动记录示例(函数调用分析中的举例)控制链：指向调用函数活动记录的一个地址。machunyan西北工业大学软件与微电子学院14b:2a:1该函数调用结束时的返回地址(00401014)主调函数的控制链c:3栈底栈顶7.1程序执行时的存储器组织（续）当前函数的控制链第7章运行时环境machunyan西北工业大学软件与微电子学院157.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)第7章运行时环境machunyan西北工业大学软件与微电子学院167.2完全静态的运行时环境在完全静态环境中，不仅全局变量，所有的变量都是静态分配，即整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配，适于静态分配的语言，要求满足的条件是：每个数据名所需的存储空间的大小都是常量不允许采用动态的数据结构，即在程序运行过程中申请或释放的数据结构过程不可递归调用第7章运行时环境machunyan西北工业大学软件与微电子学院17整个程序存储器如右所示：7.2完全静态的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院187.1程序执行时的存储器组织7.2完全静态的运行时环境7.3基于栈的运行时环境7.4动态存储器7.5参数存储机制第7章运行时环境(存储空间)第7章运行时环境machunyan西北工业大学软件与微电子学院197.3基于栈的运行时环境在一个所有函数都是全局的、函数定义不允许嵌套，但允许函数递归调用的程序设计语言(例如C语言)中，基于栈的动态运行时环境有两个指针：sp:栈顶部(topofstack)指针；对于x86系统来说，它采用sp或esp寄存器存储栈顶部的地址；注：用它只可访问栈顶第7章运行时环境machunyan西北工业大学软件与微电子学院207.3基于栈的运行时环境（续）fp(framepoint)：控制链指针，即存储当前活动记录的控制链（即一个地址），对于x86系统，它采用bp或ebp寄存器存储当前活动记录的控制链，其作用如下：1.通过该指针可以访问主调函数的活动记录；即允许在当前的被调函数执行完毕时，用它来恢复主调函数的活动记录。2.通过该指针可以访问当前执行函数的实参和局部变量；第7章运行时环境machunyan西北工业大学软件与微电子学院21b:2a:1该函数调用结束时的返回地址(cs:eip)00401014主调函数的控制链(main.ebp)void__stdcallf_stdcall(inta,intb){intc;c=a+b;}c:3esp栈底栈顶ebp7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院22当一个函数被调用时，在栈顶为该函数分配所需的数据空间(过程活动记录)如下：1)将实参的值压入在该函数对应的新活动记录中。2)将被调函数执行完毕后的返回地址压入在新的活动记录中。3)完成到被调用的过程代码一个转移。4)将主调函数的fp作为控制链压入到新的活动记录中。5)改变fp以使其指向新的活动记录(将sp复制到fp中)6)将该函数的局部变量和局部临时变量压入到新的活动记录中。7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院23b:2a:1该函数调用结束时的返回地址(cs:eip)00401014主调函数的控制链(main.fp)C语言当前执行函数的活动记录示例：c:3sp栈底栈顶fp7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院24当被调函数执行完毕返回时，其对应的活动记录从栈中弹出的过程：①将fp复制到sp中。②将控制链装载到fp中。③完成到返回地址主调函数的一个转移。④改变sp以弹出实参。7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院25例：计算两个非负整数最大公约数的c代码如下：#includestudio.hintx,y;intgcd(intu,intv){if(v==0)returnu;elsereturngcd(v,u%v)}main(){scanf(“%d%d”,&x,&y);printf(“%d\n”,gcd(x,y));return0;}7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院26x:15y:10全局/静态区域main的活动记录sp,fpv:10u:15返回地址main的fp第一次调用gcd时的活动记录sp,fp第二次调用gcd时的活动记录v:5u:10返回地址第一次调用gcd时的fp第三次调用gcd时的活动记录v:0u:5返回地址第二次调用gcd时的fpsp,fpsp,fp栈生长方向自由空间7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院27例：考虑下列程序清单的c代码。intx=2;voidg(int);voidf(intn){staticintx=1;g(n);x--;}voidg(intm){inty=m-1;if(y0){f(y);x--;g(y);}}main(){g(x);return0;}画出至第二次对g调用时，程序的运行时环境：7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院28x:2x（fromf）:1全局/静态区域main的活动记录sp,fpm:2返回地址main的fpy:1第一次调用g时的活动记录fpsp第一次调用f时的活动记录n:1返回地址第一次调用g时的fpsp,fp第二次调用g时的活动记录m:1返回地址第一次调用f时的fpy:0fpsp栈生长方向自由空间7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院29目标代码的生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的代码。对名字的访问局部临时变量嵌套声明如何处理可变长度的问题7.3基于栈的运行时环境（续）第7章运行时环境machunyan西北工业大学软件与微电子学院30对名字的访问：在没有局部过程的基于栈的运行时环境中，所有的非局部的名字都是全局的，因此也就是静态的，都具有一个固定的静态地址，可以被直接访问。对函数参数和局部变量而言，在大多数的语言中，如果函数的声明在编译时是固定的，而且为每个声明分配的存储器大小也根据其数据类型而固定，每个实参和局部声明的偏移量可由编译程序计算。第7章运行时环境machunyan西北工业大学软件与微电子学院31m:2返回地址控制链y:1fpmOffsetyOffsetmOffset=+8yOffset=-4高端地址低端地址对名字的访问：（续）第7章运行时环境machunyan西北工业大学软件与微电子学院32例：考虑下面的C过程Viodf(intx,charc){inta[10];doubley;……}cx返回地址控制链a[9]…a[1]a[0]yfpcOffsetaOffsetxOffsetyOffsetxOffset=+8cOffset=+12aOffset=-40yO