针对 GPU 单指令多数据流的编译优化算法

关注
发布于: 2020 年 07 月 06 日
1.单指令多数据流首先来看一段简单的if-else语句：
if(A)
{
    B = 1;//Instruction S1
    C = 2;//Instruction S2
}
else
{
    B = 3;//Instruction S3
    C = 4;//Instruction S4
}
假设代码中每条语句转换成指令后分别是S1、S2、S3、S4.
如果在CPU的单指令单数据流中，A=true时会取指令S1和S2执行，A=false时会取指令S3和S4执行，不存在A=true和A=false同时存在的这种情况。
但是在GPU的单指令多数据流（SIMD）中却存在A=true和A=false同时存在的情况。
如下图所示是GPU单指令多数据流的执行情况：
GPU单指令多数据流
从图中可以看到，GPU共有4个通道lane1、lane2、lane3、lane4，分别对应4笔不同的数据。这四个通道共享同一组指令S1、S2、S3、S4（如图中左边所示）。但是在4个不同的lane中，A的值在不同的lane中有时是true，有时是false。红色表示执行该指令，橙色表示不执行该指令。
如果按照CPU单指令单数据流的方式去编译，生成的汇编指令是大概这样的：
goto     !A , Labe1;//如果A为false，跳转
mov      B , 1;//指令S1
mov      C , 2;//指令S2
Lable1:
mov      B , 3;//指令S3
mov      C , 4;//指令S4
可以看到goto指令会根据A的值进行跳转，GPU中A的值在不同的lane中取值不同，不同的lane根据自己的A值进行跳转是行不通的。因为所有的lane共享同一组指令，不可能有的lane在执行S1、S2语句，有的lane在执行S3、S4语句。
所以GPU的指令应该转换成顺序执行，类似与下面这种。
(p0) mov      B , 1;//指令S1
(p0) mov      C , 2;//指令S2
(p1) mov      B , 3;//指令S3
(p1) mov      C , 4;//指令S4
此时不同的lane都会按照顺序取值S1，S2，S3，S4，但是具体的lane中会根据前面的p寄存器的取值确定是否执行该指令。例如对于同一条指令S1，根据A的输入，有的lane是执行的（红色），有的lane是不执行的（橙色）。
一句话总结就是：GPU是单指令多数据流（SIMD）架构，当多笔数据过来时，不一定同时跳转，本文介绍的if-conversion算法能够消除所有的跳转指令，可以将控制依赖转换为数据依赖。
2.if-conversion算法总共分四步：
计算直接后继支配节点
计算控制依赖CD
计算R&K函数
Augment K
首先要计算直接后继支配节点，因为在控制依赖CD的计算中需要用到。
什么是控制依赖CD，一个简单的例子就是if语句中的block y是受if语句所在的block x所控制的。此时CD(y) = x, 称为y控制依赖于x。
R&K分别对应寄存器p的use与def，即寄存器p的使用与定义。
R(x):表示分配给block x的谓词寄存器。block x的执行与否受R(x)中的寄存器控制。也可以说是p的use，即寄存器p用于block x。
K(p):表示谓词寄存器p需要在K(p)中的block中定义。也就是寄存器的def，即寄存器p在那个block定义。
2.1 直接后继支配节点首先要弄清楚两个概念：后继支配节点、直接后继支配节点。
后继支配节点：如果从节点y到出口节点的每一条路径都经过节点x，则x为y的后继支配节点。
记作：x pdom y
直接后继支配节点：x pdom y，不存在节点z，使得x pdom z 且 z pdom y。 则x为y的直接后继支配节点。
记作：x ipdom y
计算后继支配节点的迭代算法：
change = true;
//init pdom set
pdom(exit_block) = {exit_block}
pdom(0:eeit_block-1) = {all blocks}
//iterate flow graph
while(change)
{
  change = false;
  for( each block n) with post order
  {
    tmp = {all blocks}; 
    //求节点n所有直接后继节点的共同后继支配节点
    for(each n's successor block p)
    {
      tmp = tmp & pdom(p);//求交集
    }
    //n的后继支配节点包括他本身
    tmp = tmp | {n};
    if(tmp!=pdom(n))
    {
      pdom(n) = tmp;
      change = true;
    }
  }
}
求后继支配节点的算法一句话概括：节点n的后继支配节点包括他本身，以及他所有直接后继节点的共同后继支配节点。
计算直接后继支配节点的算法：
//remove itself from it's pdom set
for each node n
{
  pdom(n)-={n};
}
for each node n with post order
{
  for each s in pdom(n){
  //移除直接后继支配节点的后继支配节点 
    for each t in set( pdom(n)-s ){
      if( t is in pdom(s) )
        pdom(n)-={t}
    }
  }
}
后继支配节点 = 直接后继支配节点 + （直接后继支配节点）的后继支配节点
前面已经求出了后继支配节点，因此在后继支配节点中移除（直接后继支配节点）的后继支配节点，即可得到直接后继支配节点。
下图是一个计算直接后继支配节点的例子：
直接后继支配节点
2.2. CDCD是Control Dependent的缩写。直接上英文定义可能更准确一些，详细证明可参考文章末尾给出的论文，公众号后台回复SIMD关键字即可下载。
Y is control dependent on X iff
(1) there exists a directed path P from X to Y with any Z in P (excluding X and Y) post-dominated by Y
(2) X is not post-dominated by Y.
计算CD的算法：
pdom(x) = {y in N: y pdom x}
ipdom(x) = {y in N: y ipdom x}
for [x,y,label] in E such that y not in pdom(x)
{
    Lub = ipdom(x);
    if !label 
      x = -x
    t = y;
    while(t!=Lub)
    {
      CD(t) = CD(t) U {x}//U表示求并集
      t = ipdom(t);
    }
}
上述伪代码中的！label表示由block x到block y的执行条件为false。
计算CD的算法用一句话概括： 对于[x,y,label],在支配节点树中，从ipdom(x)到y的路径上的所有节点都控制依赖于x，不包括ipdom(x)。
以[1,2,true]为例，ipdom(x) = 7,从下面的后继支配节点树可知，7到2经过的节点有6,2（不包括7）,因此节点6和2都控制依赖于节点1.
后继支配节点树
下图是CD计算的结果：整篇文章都使用同一个控制流图作为实例
CD计算结果
2.3. 计算R&K
p = 1;
for x in N
    t = CD(x);
    if t in K
    {
        //性质2
        R(x) = q such that K(q) = t;
    }
    else
    {
        K(p) = t;
        R(x) = p++;
    }
性质1：每一个block x有且仅有一个对应的p = R(x)
性质2：对与两个不同的block，如果它们的控制依赖都为k(p),则这两个block对应的寄存器都为p（对应上述算法中的if语句）
R与K的计算结果
2.4. Augment Kk(p)表明p需要在哪些block初始化，但是存在一条路径，刚好没有经过k(p),这个时候p没有被初始化。因此需要在start节点对p进行初始化。
主要是针对类似的if语句嵌套：
//原始的控制流
if(condition1)
{
    block1
    if(codition2)
    {
        block2
    }
    else
    {
        block3
    }   
}
上面的控制流最终会转化成如下的顺序执行，只是每个block会有一个p寄存器去guard。
最终会转化为这样:
//转换后的顺序执行，是否执行受p寄存器控制
（p1) block1;//p2与p3都会在block1中初始化
 (p2) block2;
 (p3) block3;
原始的控制流中p2与p3都会在block1中初始化，如果block1没有执行，那么p2与p3就没有被初始化。因此需要在开始节点处将p2与p3初始化为false。
为什么初始化为false而不是true？因为block1没有执行，说明block2与block3也不应该执行，所以初始化为false。
上述过程是为什么要做Augment K，实际上Augment K要做的只有一件事：找到未初始化的寄存器p，在start节点处将p初始化为false。
在程序中找到为初始化的变量很简单，从后向前做活跃变量分析，如果变量在入口处还是活跃的，则该变量每有被初始化。
因为从后向前做活跃变量分析的时候，变量的每次定义都会被Kill掉，如果在程序的入口处都没有被Kill掉说明该变量是没有被初始化过的。
﻿
本算法中只需要对p寄存器进行活跃变量分析，use和def分别对应已经求出的R与K。
Augment K结果
四个步骤做完后最终的结果如下：
p寄存器分配的最后结果
图中B2(t2)p2表示寄存器p2控制B2，条件t2与B2相关联。
3.后记刚接触if-conversion算法的时候觉得挺复杂的，在写文章的过程中对整个算法的理解又有了更深刻的理解，有一种无法言喻的喜悦。
公众号目前没有考虑过盈利，主要是希望通过写一系列编译器后端算法加深自己的理解，分享自己学到的知识，同时也希望通过文章认识更多的对这方面感兴趣的朋友，一起交流，共同进步。
接下来准备写的文章：
1.静态单赋值（SSA）
目前GCC与LLVM都是基于SSA进行后端编译器优化的。
2.基于SSA的稀有条件常数传播（SCCP）
SCCP是后端编译优化中的经典算法。
3.基于图着色的寄存器分配算法
寄存器分配算法是编译器后端算法中比较复杂的算法，基于图着色的寄存器分配算法的中文资料非常少。
关于支配概念的总结
4.往期阅读从连续两届图灵奖看GPU发展史
﻿
欢迎关注我的个人公众号（程序芯世界），主要通过写作加深理解，也希望认识更多对这方面感兴趣的朋友，欢迎交流。
﻿