课程主页:

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倍以上。

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