写点什么

CPU 的性能,编译器是这样压榨的!

用户头像
GPU
关注
发布于: 2020 年 06 月 02 日

1.一个例子

先来看一段非常简单的伪代码:

a = 0;
L1: b = a + 1;
c = c + b;
a = b * 2;
if a < 9 goto L1;
return c;















2. 活跃变量分析

2.1 活跃变量的定义

如果程序中的变量在某个点之后会被使用,则该变量在该点是活跃的。

1 a = 0;
2 L1: b = a + 1;
3 c = c + b;
4 a = b * 2;
5 if a < 9 goto L1;
6 return c;

定义比较抽象,看完下面的例子就明白定义的具体含义了。

  • 活跃变量定义举例

在上图的代码中,变量c在第4行是活跃的,因为变量c在第4行之后还会继续使用(第6行会使用变量c),这就是我们所说的活跃变量。

2.2 活跃变量分析的用途

只要两个变量不会同时活跃,那么这两个变量就可以共用同一个寄存器,不用担心寄存器的内容被覆盖的问题。

也就是说当一个寄存器中的变量在后续不再活跃,我们可以重新分配该寄存器给其他变量。

知道了变量的活跃信息之后,就可以重复利用CPU中的寄存器啦。

看完这篇文章你就会知道最后的迷底,知道这段小程序最少需要几个寄存器。

2.3 符号及说明

  • in[b]表示在基本块b入口处活跃的变量集合。

  • out[b]表示在基本块b出口处活跃的变量集合。

  • use[b]表示在基本块b使用,但是使用前在基本块b中没有定义的变量集合。

  • def[b]表示在基本块中被定义的变量集合。

  • succ[b]表示基本块b的后继基本块。

2.4 计算方程与伪代码

  • 如果一个变量在基本块b中使用,则该变量在基本块b的入口处是活跃的。

  • 如果一个变量在基本块b的入口处是活跃的,在该变量在基本块b的所有前驱节点的出口是活跃的。

  • 如果一个变量在基本块b的出口处是活跃的,且该变量在基本块b中没有定义,则该变量在基本块b的入口处是活跃的。

用公式表示就是:

伪代码如下:



伪代码用一句话概括就是:从后向前计算每个节点的in和out值,然后不断的循环,直到当前循环和上一次循环的所有节点in和out值一致时结束循环。

2.5 实例

公式和代码可能比较抽象,下面来看一个具体实例。

控制流图,是用在编译器中的一个抽象数据结构,它用图的形式表示一个过程内所有基本块执行的可能流向, 也能反映一个程序的实时执行过程。为简单起见,这里将每一条语句作为一个节点。

还是文章最初的那段代码,放在下面方便回看。

1 a = 0;
2 L1: b = a + 1;
3 c = c + b;
4 a = b * 2;
5 if a < 9 goto L1;
6 return c;

上面代码对应的控制流图如下:



下表是根据伪代码和公式1、公式2计算的控制流图中每个节点的in和out值。

每一遍迭代后的结果

以节点4的第一次迭代为例,表格中其它节点的计算原理与节点4一致。 文中所提到的公式1与公式2,是2.4节中已经标明的计算in与out的两个公式。

  1. use[4]和def[4]的计算:

  • use[4] = {b}

因为第四行的等式右边使用了b。

  • def[4] = {a}

因为第四行对变量a进行了赋值,也就是对变量a进行了定义。

需要注意的是活跃变量分析要获得将来的信息,因此是从后向前的一个过程,也就从节点6向节点1的一个过程。

  1. in[4]与out[4]的计算:

从控制流图中可知,4的后继节点为5,所以有:

代人到out的计算公式(公式2)里面:

前面已经计算出succ[4] = {5},代入到上式可得:

对于in[4]的计算,直接带入到in的计算方程(公式1)中可得:

其中use[4],out[4]和def[4]已知,因此就可以求出in[4]了。

当然这只是第一遍迭代的结果,还需要继续迭代直到前一次计算的in与out与本次in与out的结果一致,此时算法收敛,迭代结束。

可以看到表格中第三遍迭代的结果与第二遍迭代的结果一致,因此程序迭代到第三次后结束。

3. 最终答案

再来回顾一下这段代码

1 a = 0;
2 L1: b = a + 1;
3 c = c + b;
4 a = b * 2;
5 if a < 9 goto L1;
6 return c;
  • 变量a的活跃范围是:

1->2 和 4->5->2

  • 变量b的活跃范围是:

2->3->4

  • 变量c的活跃范围是:

1->2->3->4->5->2和5->6

因此最初问题的答案如下:

只需要2个寄存器就可以了,因为变量a与变量b的活跃范围并不会冲突。

当然本文只是讲解了数据流分析中的活跃变量分析,这是寄存器分配的基础。 后面我会写一篇关于图着色算法进行寄存器分配的文章,结合两篇文章就可以了解我们的编译器是如何分配CPU中的寄存器了。

4.总结

本文介绍了数据流分析中活跃变量计算的迭代算法。活跃变量计算是寄存器分配的基础,后续还会写一篇图着色算法在分配寄存器时的应用,两个算法结合在一起才构成了完整的寄存器分配。

本文介绍的寄存器的高效利用只是编译器后端优化中的一种,减少程序中的冗余计算也是编译器要做的事情。

实际上不管什么语言,程序中总会存在一些程序员容易忽略的冗余计算编译器后端在做优化时会优化掉这些冗余计算。比如公共子表达式删除、复写传播、死代码删除、循环不变量外提等。

所以学习一些编译器后端算法会深刻的影响你写代码的思维,也会让你的代码更加高效。公众号会写一个编译器后端算法的专栏,欢迎家关注。

5.往期文章推荐

GPU探秘:从计算机图形学到人工智能

该文章涵盖了三个方向:计算机图形学,人工智能、GPU体系结构。这三个方向也是连续三届图灵奖授予的领域。

仔细阅读全文就会发现文章以GPU发展为线索贯穿了三个领域,另外还有异构计算部分,有兴趣的读者可以点击上方的链接接直达该文章。

关于作者

目前在一家半导体公司从事GPU编译器研发,未来来打算写一些关于计算机基础和计算机热点的文章。欢迎大家关注本公众号(程序芯世界)。

为了保证文章的质量,更新的频率会低一些,但会坚持下去的,敬请期待。



发布于: 2020 年 06 月 02 日阅读数: 75
用户头像

GPU

关注

还未添加个人签名 2018.10.10 加入

还未添加个人简介

评论

发布
暂无评论
CPU的性能,编译器是这样压榨的!