chaper 7 - 运行时环境 2019.pdf 
chaper 7 - 运行时环境 2019.pdf
编译原理 Compiler Principles 第七章 运行时刻环境 湖南大学信息科学与工程学院 软件工程系 杨金民 2018 编译器要进一步考虑的问题 l 变量在哪里？ l 如何管理变量的作用域？ l 函数的起始地址（代码）在哪里？ l 函数调用如何实现？ l 参数如何在函数之间如何传递？返回值如何在函数之间 如何传递？ 编译器编译出目标代码在计算机上的运行 目标代码运行在操作系统之上： l CreateProcess( ) 进程虚拟内存空间；线程：栈； 堆； l LoadLibrary ( ) 从磁盘加载可执行文件到内存； l CreateThread( ) 线程: 栈， IP，BP，SP 程序 = 代码 + 数据； l 数据：静态变量 LoadLibrary( ) 局部变量 函数被调用时 在实时栈中实时分配； 对象数据 new /malloc( ）, delete / free( ); 中间代码的组成 函数1的中间代码 符号表 T2 id name type_id offset 函数2的中间代码 0 i 0 0 1 a 4 4 函数i的中间代码 2 k 1 52 3 t1 2 54 4 t2 2 62 静态变量符号表 常量表 符号表0,1,..n 类型表，项表 概念性的中间代码： t1 = i + k 真实的中间代码： V2.3 = V2.0 + V2.2 将概念地址(Tid.Rid)翻译成内存地址 【baseAddr + offset】 符号表的嵌套：链表 符号表 T2 id 0 1 2 3 4 offset 0 4 52 54 62 id prior size 0 BaseAddr 64 id prior size 1 0 88 id prior size 2 程序：f{ ...{... {...} ...}...} null 1 48 id prior size 3 2 32 id prior size 9 0 0 函数的起始代码—— 基于栈实现的函数调用与活动记录 Push(BaseAddr); 调用者的 BaseAddr = top; Push(Tid. size); BaseAddr top 函数文法：FT id（P）{S} PP，T id | T id | 部分SDT BaseAddr 局部变量 调用函数 调用者的 程序：fi{ ...fj.. ...} BaseAddr param p1 Push(p1) param p2 Push(p2) call f, 2 Push(nextInstr); goto callee BaseAddr 局部变量 传递参数 top 返回地址 函数返回的部分SDT Pop(Tid.size); 调用者的 BaseAddr = Pop(addr)； BaseAddr IP = Pop(addr)； BaseAddr 局部变量 goto IP; 函数文法：FT id（P）{S } top PP，T id | T id | 语义分析的又一内容：函数类型，return 值要 与函数类型匹配；请写return语句的SDT。 传递参数 返回地址 调用者的 BaseAddr 局部变量 调用者清除调用时传递的参数 Push(p1) 调用者的 Push(p2) BaseAddr Push(nextInstr); goto callee Pop(p2) Pop(p1) 程序：fi{ ...fj.. ...} BaseAddr 局部变量 top 传递参数 被调用者访问调用者传递而来的参数 以32位机器为例： 调用者的 倒数第一个参数p2； BaseAddr 【BaseAddr - 8 - p2.size】 局部变量 倒数第二个参数p1； 传递参数 【BaseAddr - 8 - p2.size - p1.size】 返回地址 调用者的活动记录 当前函数的活动记录 调用者的 BaseAddr top BaseAddr 局部变量 活动记录链 调用者的BaseAddr 局部变量 传递参数和返回地址 调用者的BaseAddr 局部变量 传递参数和返回地址 调用者的BaseAddr top 局部变量 进一步思考的问题 l 1）对于参数个数不确定的函数调用，例如调用者调用： printf(“a=%d, b=%s, c=%6.2d”,a, b, c)； 如何传递参数？被调用者如何识别参数个数每个参数的类型？ 如何定位每个参数？ 倒着入栈的道理。被调用者通过访问第一个参数，以识别共有几个参数。 l 2）对于函数：my Func(int i，int j) { int a[i]; char b[j]; int c; } 编译时如何定位a，b, c？ 静态和动态存储分配 l静态分配：把局部变量当作全局变量/静态变量处理。exe文 件有多大，所须内存就多大。和进程的生命周期相同。 üFORTRAN的早期版本 l动态分配：局部变量在栈中分配，其生命期和过程生命期相 同。附体特性。 l堆存储：有些数据生命期要跨越函数边界，比过程调用的生 命期更长，常分配在一个可重用存储的“堆”中。有明显的生 和死动作。 栈式分配 • 概念： – 活动树 – 活动记录 – 调用代码序列 – 栈中的变长数据 活动树 程序运行时，过程调用（过程活动）总是嵌套的：后调用的 先返回(LIFO) 程序运行中的所有过程活动可以用树表示：活动树。 l 每个结点对应于一个过程活动 l 根结点——main过程的活动。 快速排序的活动树 int a[11]; void ReadArray() { ....... } //读9个数，对其排序 int partition(int m, int n) { ..... } void quicksort(int m, int n) { int i; if (n>m) { i= partition(m,n); quicksort(m, i-1); quicksort(i+1, n); } } main() { readarray(); a[0]=-9999; a[10] = 9999; quicksort(1,9); } 活动记录的变化 活动树的例子 m enter main() enter readarray() q(1,9) r leave readarray() enter quicksort(1,9) enter partition(1,9) leave partition(1,9) p(1,9) q(1,3) q(5,9) enter quicksort(1,3) ......... leave quicksort(1,3) enter quicksort(5,9) p(1,3) q(1,0) q(2,3) p(5,9) q(5,5) q(7,9) ......... leave quicksort(5,9) leave quicksort(1,9) p(2,3) q(2,1) q(3,3) p(7,9) q(7,7) q(9,9) leave main() 调用序列 • 调用序列(calling sequence)为活动记录分配空间，填写 记录中的信息； • 返回序列(return sequence)恢复调用前的状态，使调用 者继续运行。 • 调用序列会分割到调用者和被调用者中。 栈中的变长数据 l对于函数： my Func(int i，int j) { int a[i]; char b[j]; int c; a[2]= 99; } a b c BP 随堂测试：Euclid算法——递归计算两个 非负整数的最大公约数 int gcd(int u, int v) { if (v==0) return u; else return gcd(v, u%v); } main() { int x, y; scanf(“%d%d”, &x, &y); printf(“%d\n”, gcd(x,y)); return 0; } 若输入为15,10 （１）试画出运行的活动树 （２）试画出运行时栈变化过程 7.3 栈中非局部数据的访问 l 过程/函数里面，不允许定义函数：无嵌套过程/函数， 例如，Ｃ语言，只有局部变量或全局变量 l C语言允许函数作为参数。 嵌套过程 void A() { int x,y; void B( ) { int b; x = b; } void C( ) { B(); } C(); B(); } 当A调用C，C又调用B时: B的活动记录 C的活动记录 B的活动记录 A的活动记录 A的活动记录 新问题：里层要访问外层的局部变量， 深度不一样，如何定位外层的局部变 量？ • 解决方法：引入访问链：指向过程的定义环境 嵌套过程 void A() { int x,y; void B( ) { int b; x = b; } void C( ) { B(); } C(); B(); } 当A调用C，C又调用B时: B的活动记录 C的活动记录 B的活动记录 A的活动记录 A的活动记录 新问题：里层要访问外层的局部变量， 深度不一样，如何定位外层的局部变 量？ • 解决方法：引入访问链：指向过程的定义环境 访问链：指向过程的定义环境 void A() { int x,y; void B( ) { int b; x = b; } void C( ) { B(); } C(); B(); } B的活动记录 我的级别=2 C的活动记录 我的级别=2 A的活动记录 我的级别=1 B的活动记录 我的级别=2 A的活动记录 我的级别=1 访问链：指向过程的定义环境 void A() { int x,y; void B( ) { int b; x = b; } void C( ) { B(); } C(); B(); } SP 局部 变量 6000 访问链 BP 级别 环境 9800 MOV AX *BP while (*(BP - 8) *(AX - 8) +1） MOV AX *AX *(BP - 4) = AX MOV AX *(BP - 4) MOV *(AX- 4) *(BP - 4) 8000 访问链：指向过程的定义环境 void A() { int x,y; void B( ) { int b; x = B; } void C( ) { B(); } C(); B(); } MOV AX *BP while (*(BP - 8) *(AX - 8) +1） MOV AX *AX *(BP - 4) = AX MOV AX *(BP - 4) MOV *(AX- 4) *(BP - 4) 当递归调用时，while循环会出现很 深现象。 SP 局部 变量 6000 访问链 BP 级别 环境 9800 8000 while循环因递归调用而出现很深 m main() { int a[11]; void ReadArray() { ....... } int partition(int m, int n) { .....} void quicksort(int m, int n) { int i; if (n>m) { i= partition(m,n); quicksort(m, i-1); quicksort(i+1, n); } } readarray(); a[0]=-9999; a[10] = 9999; quicksort(1,9); } r q(1,9) p(1,9) q(1,3) q(5,9) p(1,3) q(1,0) q(2,3) p(5,9) q(5,5) q(7,9) p(2,3) q(2,1) q(3,3) p(7,9) q(7,7) q(9,9) 解决办法：显示表(display) d[2] d[1] d[0] q(7,7)访问链 级别=1 pre=BP3 q(7,9)访问链 级别=1 pre=BP2 q(5,9)访问链 MOV pre，d[级别】 MOV d[级别], BP 级别=1 pre=BP1 q(1,9)访问链 级别=1 pre=null m访问链 null BP4 BP3 BP2 BP1 函数作为参数时，访问链的维护 main() { int a[11]; void ReadArray() { ....... } void quicksort(int m, int n) { int i; if (n>m) { i= partition(m，readarray ); quicksort(m, i-1); quicksort(i+1, n); } } quicksort(1,9); r 访问链 级别=1 环境= ? p(1,f)访问链 null q(1,9)访问链 } 级别=1 环境=BP0 int partition(int m, fun* f ) { ....f( )....} m访问链 null BP3 BP2 BP1 BP0 7.4 堆管理 • 堆空间 – 用于存放生命周期不确定、或者生存到被显式删除为止的数 据对象，例： • 分配： X *p = new X; • 回收: delete p； 分配：在堆中分配一段连续的、适当大小的堆空间。把地址作为 指针返回； 回收：把被所占空间返回空闲空间缓冲池，以备以后的分配请求。 7.4 堆管理天生的缺陷——空间碎片 • 堆空间 7.4 堆管理天生的缺陷——空间碎片 • 堆空间 新请求 空闲位置表： 起始位置 大小 4000 200 4880 300 6704 150 9260 424 其中的四个对象被释放后，出 现了磁盘碎片问题。对后来的 分配请求，尽管总空闲空间足 够，但不能满足请求要求。 堆存储管理中面临的挑战 创建对象，程序员会明确地表达出来； l 内存泄露： l 程序员常常只关注使用对象，使用之后，忘记释放对象； l 因为程序异常，导致分配，回收没有配套执行。 l 悬空指针引用(danggling pointer dereference): 因为程序控制缺陷，对象被释放后，程序还去访问它，导致 出现“访问根本不存在的内存”的严重异常错误。 l 访问越界问题； 堆存储管理中面临的挑战 l 内存泄露： l 悬空指针引用； l 访问越界问题； 编译器有办法来解决吗？如不能，能缓解该问题吗？ 期望的堆管理器特性 l 空间效率 – 使程序所需堆空间最小 – 实现手段：最小化存储碎片 l 程序效率 – 充分利用存储子系统，提高程序运行效率 • 不同的存储器，访问速度不一样 l 低开销 – 最小化分配/收回内存的开销 • 花费在分配和回收上的执行时间与总运行时间的比例 – 注：分配的开销由小型请求决定，管理大型对象的开销相对 不重要 存储器 类型 容量 访问速度 分配最小单元 Register 32个 1ns 个 1级Cache 64k 5-10ns cache line 2级Cache 4M 40-60ns memory 2GB 100-150ns 对齐align， padding Disk 800GB 3000-15000 page 编译原则：充分利用高速存储器 程序特性——局部性 90%的运行时间花费在执行10%的代码上； l 对一个函数来说，错误/异常/容错/调试的处理代码，遗留代 码，几乎不会执行； l 对一个函数库文件来说，通常仅只使用了很少几个函数； l 大部分时间在执行最内层的循环，或递归上。 程序特性——局部性 • 时间局部性 – 若一个程序当前访问的存储位置很可能随后或者紧接着被 再次访问，称之为时间局部性 • 空间局部性 – 若当前访问的存储位置的邻近位置很可能随后或者紧接着 要被再次访问，称之为空间局部性； 流水线逐级缓存的可行性：将最常用的指令和数据放在 快而小的存储器中 堆空间的分配策略 l Best-Fit（最佳适应优先） – 在满足请求的最小空闲区中分配内存 – 优点：可将大窗口保留下来以应对更大的请求； – 缺点：要扫描整个空闲位置表； l First-Fit（最先适应优先） – 在第一个满足请求的空闲区中中分配内存 – 优点：快，同一段时间内的对象分配连续空间； – 缺点：碎片问题会严重，空间利用率差； 使用容器的管理方法 • 设定不同大小的空闲块，并将同样大小的块放在容器中。 • 较小的（较常用的）尺寸设置较多的容器。 • 比如GNU的C编译器gcc使用存储管理器lea将所有存储块对 齐到8字节边界。 – 空闲块的尺寸大小：16,24,32,40,…,512 • 大于512的按照对数划分：每个容器的最小尺寸是前一 个容器的最小尺寸的两倍。 • 荒野块：可以扩展的内存块 – 分配方法： • 对于小尺寸的请求，直接在相应容器中找。 • 大尺寸的请求，在适当的容器中寻找适当的空闲块。可 能需要分割内存块。 • 可能需要从荒野块中分割更多的块。 管理和接合空闲空间 • 当回收一个块时，可能可以把这个块和相邻的块接合起来， 构成更大的块。 • 有些管理方法，比如说Lea中，不一定需要进行接合。 • 支持相邻块接合的数据结构 – 边界标记：在每一块存储块的两端，分别设置一个 free/used位；相邻的位置上存放字节总数。 – 双重链接的、嵌入式的空闲块列表：列表的指针存放在空 闲块中、用双向指针的方式记录了有哪些空闲块。 例子 • 相邻的存储块A、B、C – 当回收B时，通过对free/used位的查询，可以知道B左边 的A是空闲的，而C不空闲。 – 同时还可以知道A、B合并为长度为300的块。 • 注意：双重链表中一个结点的前驱并不一定是它邻近的块。 处理人工存储管理P280-281 • 两大问题： – 内存泄露：未能删除不能被引用的数据 – 悬空指针引用：引用已经被删除的数据 解引用：读、写、回收等沿一个指针试图使用该指针所 指对象的所有操作称为该指针的“解引用” • 还有空指针访问，或者数组越界访问 • 解决方法： – 自动存储管理 – 正确的编程模式 正确的编程模式（1） • 对象所有权（Object ownership） – 当对象的生命期可静态确定时有用 – 思想： • 为每个对象分配一个所有者（指向此对象的指针） • 所有者负责删除或传递该对象 • 可能有其他非所有者的指针也指向该对象，但它们 可随时重写，也不能通过它们来删除对象 • 当Owner消亡时，这个对象要么被删除，要么被传递给 另一个owner。 – 比如函数中有语句v=new ClassA；此时创建的 对象的所有者为v；当这个函数返回时，这个对 象被传递给另一个所有者； – 优点：可防止内存泄漏、避免多次删除对象 – 缺点：不能解决悬空指针问题 正确的编程模式（2） • 引用计数 – 当对象的生命期需要动态确定时有用 – 基本思想： • 每个动态分配的对象关联一个计数；记录有多少个指针 指向这个对象； • 在计数变成0后，删除这个对象； – 优点：可解决悬空指针问题 – 缺点： • 在递归数据结构中仍可能引起内存泄漏 • 需要较大的运行时刻开销。 正确的编程模式（３） • 基于区域的分配 – 当对象集合的生命期与计算的特定阶段关联时有用 – 基本思想： • 若某些对象的创建仅用于计算的某个步骤，则将这些 生命期相同的对象分配在同一个区域中 • 当该计算步骤完成时，将整个区域同时删除 – 缺点：适用范围不广 – 优点：效率高 • 整体删除 作业 • 7.2.5,7.2.6,7.3.2 第六章 中间代码生成 语义分析和 中间代码生成 DAG 图 中间代 码表示 类型检查 和翻译 三地 址码 表达式 翻译 静态单 赋值 中间代 码生成 控制流 翻译 回填 过程 翻译 谢 谢 谢 谢！