CPU 的性能，编译器是这样压榨的！

关注
发布于: 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的两个公式。
use[4]和def[4]的计算：
use[4] = {b}
因为第四行的等式右边使用了b。
def[4] = {a}
因为第四行对变量a进行了赋值，也就是对变量a进行了定义。
需要注意的是活跃变量分析要获得将来的信息，因此是从后向前的一个过程，也就从节点6向节点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编译器研发，未来来打算写一些关于计算机基础和计算机热点的文章。欢迎大家关注本公众号（程序芯世界）。
为了保证文章的质量，更新的频率会低一些，但会坚持下去的，敬请期待。
﻿