课程主页：

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

课程视频：

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

备注：

图片均来自于课件。

这次回顾寄存器分配。

寄存器分配

问题

  • 中间代码使用无限的临时变量
    • 简化代码生成和优化
    • 但是复杂化翻译为汇编的步骤
  • 典型的中间代码使用过多的临时变量
  • 问题：
    • 重写中间代码以使用不超过机器寄存器的临时变量
  • 方法：
    • 为每个寄存器分配多个临时对象
    • 但不更改程序行为

例子

  • 考虑程序

  • 可以将$a,e$和$f$全部分配给一个寄存器($r_1$)：

  • 这里假设使用后$a,e$变成dead

    • dead临时变量可以“重用”

历史

  • 寄存器分配与编译器一样古老
    • 在50年代的原始FORTRAN编译器中使用了寄存器分配
    • 这是个非常粗糙的算法
  • 1980年取得了突破
    • 基于图着色的寄存器分配方案
    • 相对简单，全局且在实际中运行良好

分析

  • 临时变量$t_1$和$t_2$以共享同一寄存器，如果在程序中的任何一点上$t_1$或$t_2$中的一个处于活动状态；
  • 或者如果$t_1$和$t_2$同时活动，则它们不能共享寄存器。

例子

  • 利用上一讲的方法计算每个点的live变量：

  • 然后构造无向图

    • 每个变量作为节点
    • 如果$t_1$和$t_2$在程序中某个点同时live，则在$t_1$和$t_2$之间存在边

  • 这是寄存器干扰图（RIG）

    • 两个临时变量可以被分配到同一个寄存器，如果它们没有边连接

  • 对于我们的例子，RIG为

    • 例如，$b$和$c$不能在同一寄存器中
  • 例如，$b$和$d$可以在同一寄存器中

习题

$A$和$C$会相互干扰，$B$和$C$会相互干扰。

小结

  • 准确提取表征合法寄存器分配所需的信息
  • 给出寄存器要求的全局图（即整个流程图）
  • RIG构建后，寄存器分配算法与体系结构无关

图着色

  • 图着色是对节点的颜色分配，使得通过边连接的节点具有不同的颜色；
  • 如果图形可以用$k$种颜色着色，则该图形为$k - \mathrm{colorable}$；
  • 在我们的问题中，颜色 = 寄存器
    • 我们需要为图节点（临时）分配颜色（寄存器）
  • 令$k =$机器寄存器的数量；
  • 如果RIG是$k - \mathrm{colorable}$，则存在不超过$k$个寄存器的寄存器分配。

图着色例子

  • 考虑RIG例子

  • 没有少于4种颜色的着色

  • 存在4种颜色的着色

  • 对应的颜色在图中

分配后的结果如下：

习题

选择第四项。

图着色的解决方案

  • 我们如何计算图着色？
  • 这并不容易：
    • 这个问题很难解决（NP-hard），即没有已知的有效算法。
      • 解决方案：使用启发式算法。
    • 对于给定数量的寄存器，可能不存在着色。
      • 解决方案：之后解决。
思路
  • 观察：
    • 在RIG中选择一个少于$k$个邻居的节点$t$；
    • 从RIG中消除$t$及其边；
    • 如果结果图是$k - \mathrm{colorable}$，则原始图也是。
  • 为什么？
    • 令${c}_{1}, \ldots, {c}_n$为在reduced图中分配给$ t$的邻居的颜色；
    • 由于$ n <k$（$t$的邻居数量小于$k$），我们可以为$ t$选择与其相邻色不同的颜色。
  • 以下内容在实际中效果很好：
    • 计算寄存器数量：
      • 选择一个少于$k$个邻居的节点$t$；
      • 将$t$ push到堆栈上，然后将其从RIG中删除；
      • 重复直到图为空。
    • 为堆栈上的节点分配颜色：
      • 从添加的最后一个节点开始；
      • 在每个步骤中，选择一种与分配给已着色邻居的颜色不同的颜色。

例子

取$k=4$。

计算寄存器数量：

删除$a$。

删除$d$。

注意现在所有节点有少于$4$个邻居。

删除$c$。

删除$b$。

删除$e$。

删除$f$。

现在图为空，第一部分完成。

着色：

现在开始给节点指定颜色，从堆栈的顶部开始。

$e$必须与$f$在不同的寄存器中。

$d$可以和$b$在同一个寄存器中。

习题

选择第一项。

溢出（Spilling）

  • 图形色启发式检测失败会怎样？
  • 在这种情况下，我们无法将所有值都保存在寄存器中。
    • 一些值溢出到内存中。

例子

  • 如果所有节点都具有$k$个或更多邻居，该怎么办？

  • 例子：尝试查找RIG的3-coloring：

  • 删除$a$，然后就卡住了

  • 选择一个节点作为溢出对象

    • 溢出值在内存中“live”
    • 假设选择了$f$

  • 删除$f$并继续进行简化

    • 现在化简成功：$b,d,e,c$

  • 最终，我们必须为$f$分配颜色

  • 我们希望在$f$的$4$个邻居中，使用少于3种颜色$\Rightarrow$乐观着色

  • 如果乐观着色失败，我们将溢出（spill）$f$

    • 即为$f$分配存储位置
      • 通常在当前栈帧中
      • 将此地址称为$\mathrm{fa}$

  • 在每个读取$f$的操作之前，插入

  • 每次写$f$的操作后，插入

处理结果

原始代码：

溢出$f$后的代码：

重新计算liveness：

分析

  • 新的liveness信息几乎和以前一样

    • 注意$\mathrm f$被划分为三个临时变量

  • $\mathrm{fi}$只有在如下条件下才为live

    • 在$\text{fi := load fa}$和下一条指令之间；
    • 在$\text{store fi, fa}$和前面的指令之间。

  • spill会降低$\mathrm f$的有效范围

    • 从而减少其干扰
    • 这导致更少的RIG邻居

  • spill节点的某些相邻边已删除

    • 在我们的情况下，$\mathrm f$仍然仅干扰$\mathrm c$和$\mathrm d$

    • 新的RIG是3-colorable

  • 在发现着色之前，可能还需要额外的spill

  • 棘手的部分是确定要spill什么

    • 但是任何选择都是正确的

  • 可能的启发式方法：

    • spill冲突最多的临时变量
    • spill定义和用途很少的临时变量
    • 在内部循环中避免spill

习题

小结

  • 寄存器分配是编译器中的“必备”：
    • 因为中间代码使用了太多的临时变量
    • 因为寄存器分配会使得性能上有很大的不同
  • 对于CISC机器，寄存器分配更为复杂

管理缓存

引子

缓存在计算机中尤为重要

  • 电力使用限制了
    • 寄存器/缓存的大小和速度；
    • 处理器速度。
  • 但
    • 缓存未命中的代价非常高；
    • 通常需要2个高速缓存来桥接快速处理器与主内存。
  • 重要的是：
    • 正确管理寄存器
    • 以及正确管理缓存。

编译器对缓存的处理

  • 编译器非常擅长管理寄存器
    • 比程序员要好得多
  • 但是编译器不善于管理缓存
    • 这个问题仍然留给程序员
    • 尚有一个未解决的问题，编译器可以做些什么来提高缓存性能
  • 一些编译器可以执行缓存优化

例子

考虑循环

for(j := 1; j < 10; j++)
	for(i=1; i<1000000; i++) 
		a[i] *= b[i]

考虑代码

for(i=1; i<1000000; i++)
	for(j := 1; j < 10; j++) 
		a[i] *= b[i]

这两段代码

  • 计算相同的东西；
  • 但是后一段具有更好的缓存行为；
  • 可能快10倍以上。

编译器可以执行此循环交换优化。