Stanford Compiler Week 6 Runtime Organization

课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

备注：

图片均来自于课件。

这次回顾运行时组织。

运行时组织

我们已经涵盖了编译器的前端阶段
- 词法分析
- 解析
- 语义分析
接下来是后端阶段
- 优化
- 代码生成

需要了解的内容

在讨论代码生成之前，我们需要了解我们试图生成的内容；
有许多用于构造可执行代码的标准技术，这些技术被广泛使用；
- 运行时资源管理
- 如下两者的对应关系
  - 静态（编译时）结构
  - 动态（运行时）结构
- 仓储组织

程序的运行流程

程序的执行最初是在操作系统的控制下；
当调用程序时：
- 操作系统为程序分配空间；
- 代码被加载到部分空间中；
- 操作系统跳至入口点（即“main”）；

内存布局

按照传统，机器组织的布局如下：
- 顶部的低地址；
- 底部高地址；
- 划定不同数据区域的线（line）。
这些图片是简化的：
- 例如，并非所有内存都必须是连续的。
其他空间 = 数据空间。
编译器负责：
- 生成代码；
- 协调使用数据区域。

激活(Activation)

代码生成有两个目标：
- 正确
- 速度
代码生成中的复杂性来自于试图既快速又正确。

两个假设：

执行是顺序的，控制流从程序中的一个位置按定义好的顺序移动到另一个位置。
调用过程时，控制流总是返回到调用后的位置。

激活(Activation)

引入激活(Activation)的概念：

过程P的调用是对P的激活。
P的激活生命周期为：
- 执行P的所有步骤；
- 包括过程P调用中的所有步骤。
变量x的生命周期是定义x的执行部分。
请注意
- 生命周期是一个动态（运行时）概念；
- 作用域是一个静态概念。
观察
- 如果P调用Q时，那么Q在P返回之前返回。
所以过程激活的生命周期已正确嵌套。

激活的生命周期可以描述为一棵树。

例1

Class Main {
    g() : Int { 1 };
    f(): Int { g() };
    main(): Int {{ g(); f(); }};
}

图示

例2

Class Main {
    g() : Int { 1 };
    f(x:Int): Int { if x = 0 then g() else f(x - 1) fi}; 
    main(): Int {{f(3); }};
}

图示

激活树取决于运行时行为；
对于同一程序，不同输入产生的激活树可能不同；
由于激活是正确嵌套的，因此堆栈可以跟踪当前活动的过程；

习题

第一项正确。

激活记录

管理一个过程激活所需的信息称为激活记录（AR）或栈帧（frame）
如果过程F调用G，则G的激活记录包含F和G的混合信息。
- F被“暂停”，直到G完成，此时F恢复。
- G的AR包含如下内容所需的信息
  - 完成G的执行
  - 恢复执行F
  - G返回值的空间
  - 实际参数
  - 指向上一个激活记录的指针
    - 控制链接；指向G的caller的AR
  - 调用G之前的机器状态
    - 寄存器和程序计数器的内容
    - 局部变量
  - 其他临时值

例子

Class Main {
    g() : Int { 1 };
    f(x:Int):Int {if x=0 then g() else f(x - 1)(**)fi}; 
    main(): Int {{f(3); (*)
}};}

f的AR

Main没有参数或局部变量，并且永远不会使用其结果；它的AR没有太多意义
$\mathrm{(\star)}$和$\mathrm{(\star \star)}$是f调用的返回地址
- 返回地址是过程调用完成后恢复执行的位置
这只是许多可能的AR设计之一；
也适用于C，Pascal，FORTRAN等。

下图显示了调用f的第二次调用后的状态

将返回值放在第一个栈帧中的优点是，调用方可以在与自己的帧相距固定偏移量的位置找到它；
这个组织没有什么特殊的地方
- 可以重新排列栈帧元素的顺序；
- 可以不同地划分caller/call的职责；
- 如果组织能够提高执行速度或简化代码生成，那么它会更好。
真正的编译器将尽可能多的栈帧保存在寄存器中
- 特别是方法的结果和参数。
编译器必须在编译时确定激活记录的布局，并生成可正确访问激活记录中位置的代码。
因此，AR布局和代码生成器必须一起设计！

全局变量和堆

全局变量

所有对全局变量的引用都指向同一个对象
- 所以无法在激活记录中存储全局变量。
因此需要为全局变量分配一次固定地址
- 具有固定地址的变量是“静态分配的”。
根据语言，可能还有其他静态分配的值

堆

动态分配的值不能存储在AR中
```
method foo() { new Bar }
```
Bar值必须在foo的AR释放后依然存在，因为foo的调用者可能使用Bar。
具有动态分配数据的语言使用堆来存储动态数据。
代码区域包含目标代码
- 对于许多语言，目标代码是固定大小和只读的。
静态区域包含具有固定地址的数据（非代码）（例如，全局数据）
- 固定大小，可能是可读或可写的。
堆栈包含每个当前活动过程的AR
- 每个AR通常固定大小，并且包含局部变量。
堆包含所有其他数据
- 在C中，堆由malloc和free管理。

堆和堆栈

堆和堆栈都会增长
必须注意不要互相影响
解决方案：
- 将堆和堆栈顶在内存的两端，然后让它们彼此靠近：

对齐

大多数现代机器是32或64位
- 一个字节为8位；
- 一个字中有4或8个字节；
- 机器是字节或字可寻址的。
如果数据始于字边界，则该数据是字对齐的。
大多数机器都有一些对齐限制
- 不好的对齐会导致性能较差；
- 有些会相差10倍。

例子

字符串
$\text{“ Hello”}$
包含5个字符（不带\0的结尾）
要使得根据下一个字对齐，请在字符串中添加3个“填充”字符；
填充不是字符串的一部分，只是未使用的内存。

堆栈机

堆栈机唯一的存储是堆栈。
指令$\mathrm{r = F(a_1,\ldots, a_n)}$：
- 从堆栈中弹出$\mathrm n$个操作数；
- 使用操作数计算操作$\mathrm F；$
- 将结果$\mathrm r$压入堆栈；
考虑两条指令
- $\text{push i}$
  - 将整数$\text {i}$推入堆栈。
- $\text{add}$
  - 相加两个整数。
- 考虑程序：
```
push 7 
push 5 
add
```
- 图示：

堆栈机VS寄存器机

堆栈机是非常简单的机器模型
- 可以产生一个简单的小型编译器；
- 但不一定会产生非常快速的代码。
没有明确说明操作数/结果的位置
- 因为始终位于栈顶。
与寄存器机相反
- 用$\text{add}$而不是$\mathrm{add\ r_1,\ r_2, \ r_3}$；
- 会产生更紧凑的程序；
- 这也是Java字节码使用堆栈的原因之一。
在纯堆栈机和纯寄存器机之间有一个中间点：
- $\mathrm n$寄存器堆栈机
  - 从概念上讲，将纯堆栈机堆栈的前$\mathrm n$个位置保留在寄存器中。
考虑一个$\mathrm 1$寄存器堆栈计算机：
- 该寄存器称为累加器。
在纯堆栈机中
- 一次$\text{add}$执行三次内存操作；
- 两次读取，一次写入堆栈。
在$\mathrm 1$寄存器堆栈计算机中，$\text{add}$运算符只要使用如下方式即可
$\mathrm{acc} \leftarrow \mathrm{acc}+\text {top_of_stack }$
考虑一个表达式$\mathrm {op\left(e_{1}, \ldots, e_{n}\right)}$
- 注意$\mathrm {e_1,\ldots, e_n}$是子表达式。
- 对于每个$\mathrm {e_i(0 <i <n)}$
  - 计算$\mathrm {e_i}$；
  - 将结果压入堆栈。
- 从堆栈中弹出$\mathrm {n-1}$个值，计算$\mathrm{op}$
- 将结果存储在累加器中。
对表达式求值会保留堆栈。
- 对表达式$\mathrm e$求值后，累加器将保留$\mathrm e$的值，并且堆栈剩余部分不变。