06 编译器原理与技术---运行时存储空间的组织和管理

1 .第 6 章 运行 时存储空间 的组织 和管理 编译原理与技术

2 .术语 过程的活动 过程的一次执行称为过程的一次活动 活动记录 过程 的活动需要可执行代码和存放所需信息的 存储空间，后者 称为活动记录 讨论 一个活动记录中的数据布局 程序执行过程中，所有活动记录的组织方式 第 6 章 运行时存储空间的组织和管理 内容提要

3 .影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递 存储块能否在程序控制下动态地分配 存储块是否必须显式地释放 第 6 章 运行时存储空间的组织和管理 内容提要

4 .6.1 局部存储 分配 第 6 章 运行 时存储空间 的组织 和管理

5 .6.1.1 过程 语言概念： 过程定义 过程 调用 形式参数 实在参数 活动 的 生存期 6.1 局部存储 分配

6 .6.1.2 名字的作用域和绑定 （ 1 ）名字 的作用域 一个声明起作用的程序部分称为该声明的 作用域 即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象 （ 2 ）环境和状态 环境 把名字映射到左值，而 状态 把左值映射到右值（即名字到值有两步映射） 赋值改变状态；过程调用改变环境 如果环境将名字 x 映射到存储单元 s ，则说 x 被绑定到 s 6.1 局部存储 分配 名字 存储单元 状态 值 环境

7 .（ 3 ）静态 概念和动态概念的对应 6.1 局部存储 分配 静 态 概 念 动 态 对 应 过程的定义 过程的活动 名字的声明 名字的绑定 声明的作用域 绑定的生存期

8 .6.1.3 活动记录 活动 记录的常见布局 6.1 局部存储 分配 临 时 数 据 参 数 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值

9 .6.1.4 局部数据的布局 字节是可编址内存的最小单位 变量所需的存储空间可以根据其类型而静态确定 一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间 局部数据的地址可以用相对于活动记录中某个位置的地址来表示 数据对象的存储布局还有一个对齐问题 6.1 局部存储 分配

10 .例 在 SPARC/Solaris 工作站上下面两个结构体的 size 分别是 24 和 16 ，为什么不一样？ typedef struct _a { typedef struct _b{ char c1; char c1 ; long i ; char c2 ; char c2; long i ; double f; double f ; }a ; } b; 对齐 ： char : 1, long : 4, double : 8 6.1 局部存储 分配 0 4 8 16 0 1 4 8

11 .例 在 X86/Linux 工作站 上下面两个结构体的 size 分别是 2 0 和 1 6 ， 为什么不一样？ typedef struct _a { typedef struct _b{ char c1; char c1 ; long i ; char c2 ; char c2; long i ; double f; double f ; }a ; } b; 对齐 ： char : 1, long : 4, double : 4 6.1 局部存储 分配 0 4 8 12 0 1 4 8

12 .6.1.5 程序块 本身含有局部变量声明的语句 可以嵌套 最接近的嵌套 作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重叠分配 6.1 局部存储 分配

13 .例： main() { /  begin of B 0  / int a = 0; int b = 0; { /  begin of B 1  / int b = 1; { /  begin of B 2  / int a = 2; } /  end of B 2  / { /  begin of B 3  / int b = 3; } /  end of B 3  / } /  end of B 1  / } /  end of B 0  / 6.1 局部存储 分配 声 明 作 用 域 int a = 0; B 0  B 2 int b = 0; B 0  B 1 int b = 1; B 1  B 3 int a = 2; B 2 int b = 3; B 3 a 0 b 0 b 1 a 2 , b 3 重叠分配存储单元

14 .6.2 全局 栈式存储分配 第 6 章 运行 时存储空间 的组织 和管理

15 .本节介绍 介绍程序运行时所需的各个活动记录在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元 介绍三种分配策略 静态分配策略 栈式分配策略 堆式分配策略 6.2 全局 栈式 存储分配

16 .6.2.1 运行时内存的划分 6.2 全局 栈式 存储分配 代 码 静 态 数 据 堆 栈 低地址 高地址

17 .（ 1 ）静态 分配 名字在程序被编译时绑定到存储单元，不需要运行时的任何支持 绑定的生存期是程序的整个运行期间 （ 2 ）静态 分配给语言带来限制 递归过程不被允许 数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的 数据结构不能动态建立 6.2 全局 栈式 存储分配

18 .例 C 程序的外部变量、静态局部变量以及程序中出现的常量都可以静态分配 声明 在函数外面 外部变量 -- 静态分配 静态外部变量 -- 静态分配 声明 在函数里面 静态局部变量 -- 静态 分配 自动变量 -- 不能静态分配 6.2 全局 栈式 存储分配

19 .一个 C 语言程序及其在 X86/Linux 操作系统上的编译 结果如下页。 根据所生成的汇编程序来解释程序中四个 变量 的存储分配、生存期、作用域和置初值方式等 方面的 区别 static long aa = 10; short bb = 20; func ( ) { static long cc = 30; short dd = 40; } 6.2 全局 栈式 存储分配 例题

20 .. data | .text .align 4 | .align 4 .type aa , @ object | . globl func .size aa , 4 | func : aa : | . . . .long 10 | movw $40 , - 2(% ebp ) . globl bb | . . . .align 2 | .type bb , @ object | .size bb, 2 bb : .value 20 .align 4 .type cc.2, @object . size cc.2, 4 cc.2 : .long 30 6.2 全局 栈式 存储分配 例题 static long aa = 10; short bb = 20; func ( ) { static long cc = 30; short dd = 40; }

21 .6.2.2 活动树和运行栈 （ 1 ）活动 树 用树来描绘控制进入和离开活动的方式 6.2 全局 栈式 存储分配 m q(1,9) r p(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.1 程序

22 .活动树的特点 每个结点代表某过程的一个活动 根结点代表主程序的活动 结点 a 是结点 b 的父结点，当且仅当控制流从 a 的活动进入 b 的活动 结点 a 处于结点 b 的左边，当且仅当 a 的生存期先于 b 的生存期 6.2 全局 栈式 存储分配 m q(1,9) r p(1,9) q(1,3) . . . . q(5,9) . . . .

23 .当前活跃着的过程活动可以保存在一个栈 中 —— 控制栈 例 控制栈的内容： m, q (1, 9), q (1, 3), q (2, 3) 6.2 全局 栈式 存储分配 m q(1,9) r p(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)

24 .（ 2 ）运 行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录） 6.2 全局 栈式 存储分配 main r main 栈 函数调用关系树 int i r ( )

25 .（ 2 ）运 行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录） 6.2 全局 栈式 存储分配 main r main 栈 函数调用关系树 q(1,9) int i q (1, 9) int m, n int i , j p (1, 9) int p; int m, n p(1,9)

26 .（ 2 ）运 行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录） 6.2 全局 栈式 存储分配 main r main 栈 函数调用关系树 q(1,9) int i q (1, 9) int m, n int i q (1, 3 ) int m, n p(1,9) q(1,3) p(1,3) int i , j p (1, 3) int p; int m, n

27 .（ 2 ）运 行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录） 6.2 全局 栈式 存储分配 main r main 栈 函数调用关系树 q(1,9) int i q (1, 9) int m, n int i q (1, 3 ) int m, n p(1,9) q(1,3) p(1,3) int i q (1, 0) int m, n q(1,0)

28 .6.2.3 调用序列 过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态 等 过程调用序列 过程调用时执行的分配活动记录，把信息填入它的域中，使被调用过程可以开始执行的 代码 过程返回序列 被调用过程返回时执行的恢复机器状态，释放被调用过程活动记录，使调用过程能够继续执行的 代码 调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中 6.2 全局 栈式 存储分配

29 .即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异 设计这些序列和活动 记录的 一些 原则： 以活动记录中间的 某个位置作为 基地址 长度能较早确定的域放 在活动记 录的 中间 一般把临时数据域放 在局部数据 域 的后面 把参数域和可能有的 返回值域放 在 紧靠调用者 活动记录 的地方 用同样的代码来执行 各个活动的 保存 和恢复 6.2 全局 栈式 存储分配 临 时 数 据 参 数 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值