皇上，还记得我吗?我就是1999年那个Linux伊甸园啊-----24小时滚动更新开源资讯，全年无休！

麻省理工学院优化LLVM IR，大大提高并行化的效率

2017-03-29 分类：开源资讯 评论(0)

作者 杨旸

麻省理工学院优化LLVM IR，大大提高并行化的效率

目的

人类文明的许多领域都能找到某种贯穿历史长河的“物种”。 它们古老而年轻——时光荏苒，不断进化，逐渐积累下最顽强、最富生命力的基因片段，并在更广袤的生态中繁衍，最终造就该领域令人叹为观止的多样性。 编译器就是计算机世界的这样一个物种，它将不同时代大师们的匠心融入自己的基因，并逐渐传递到数据库、分布式计算、自然语言应用、人脸/语音驱动等现代物种中，比如抽象语法树、中间代码、语义优化和版本化等等。

LLVM将编译器的许多优秀机制模块化，人们可以根据自己的语言、处理器、运行平台等需要，为自身应用定制编译器，在恰当的时机，快速地获得高性能的编译结果（Bitcode），然后链接其他编译结果或库，获得性能、资源使用效率、兼容性兼备的可执行代码。

许多对LLVM的介绍偏重“使用”，比如JIT或如何编译控制GPU等虚机。但功能只是起步，匠心更显价值。用厂家或社区提供的LLVM编译器（Lua、Swift、CUDA等等）实现产品后，如果进一步了解和改善内部优化分析机制，对代码效率精益求精，则更能体现软件人员的追求，追随大师们的脚步继续传承和创新。本文希望介绍一种对LLVM编译器IR和分析优化部分的改造，希望对从事这方面工作的朋友有所启发。例如对LLVM前端、分析和优化器可以进行哪些修改，需要考虑哪些问题？有哪些分析手段？如何在中间代码IR和控制流程图（Control Flow Graph)层面进行修改？这里面的许多分析优化原理在《编译原理》（英文名Compilers: Principles, techniques and tools）里有更详尽的描述。

并行编程

随着处理器从单核向多核进化，并行编程是加速数据处理和提升吞吐量的。如何在现有的非并行代码上快速修改，将计算负载高效地分布到多颗CPU，充分利用多核，又能避免花费大量精力重写和维护不同平台的不同代码？

分叉-合并（Fork-Join)是主流编译器采用的一种并行化方法，通常用语言扩展（language extension)支持，比如Cilk Plus、OpenMP等。一个程序可以分解成一系列小任务块，每个小任务块包括各自的一系列指令。互相不依赖的一组小任务块，即可考虑并行执行（分叉出一组并行的线程），然后通过合并（Join）同步，等所有进程结束后再往下运行。

具体如何实现呢？举个例子来讲：

#pragma omp for
for (int i = 0; i < N; ++i) {
    dest[i] = a[i] + b[i] * c[i];
  }

这个for循环里的N次加乘可以并行进行，由N个计算单元一次性完成。 而且不管谁先谁后，最终结果都是一样的。

实现起来非常简单：开发者可以通过Cilk Plus或OpenMP等的语言扩展，比如加上“#pragma omp for”，来表示这部分代码可以并行执行，主流的编译器GCC、ICC、LLVM等则会将这样的循环编译成并行执行。开发者无需关心执行细节，更无需将代码拆成可并行的任务以适应TBB之类的并行计算库。

同时，去掉#pragma omp for后，程序将退化为串行执行，执行结果不会变化。因此，当测试和Debug，或底层不支持并行，或编译器不支持时，可以忽略这些语言扩展关键字，程序仍会安全地编译，执行结果和并行一样，只是没有多线程多核的并行加速而已。这也叫“串行语义”（serial semantics)——确保程序必须能退化到串行执行，是Cilk、OpenMP等并行计算语言拓展的基本准则。

但这一编译和优化过程处理并行指令时，不甚完善。2017年2月，麻省理工学院的计算机科学与人工智能实验室发表的对LLVM编译器做的一系列改进，值得关注。

LLVM编译器编译并行指令的缺陷

比如优化循环时，能看到LLVM并行化的一些缺陷。请看下面这个归一化函数：

 __attribute__((const)) double norm(const double *A, int n);

void normalize(double *restrict out,
const double *restrict in, int n) {
for (int i = 0; i < n; ++i)
out[i] = in[i] / norm(in, n);
}

该函数将in数组归一化。比如，in数组可以是各地的销售额，通过该函数转化成销售额的百分占比。（norm函数可以看成计算销售额的总和）。

因为每次对norm的调用，都会产生同样的结果，不随for循环变化，所以在不考虑并行计算的情况下，编译器通常会将该结果的计算从for循环里搬到循环之前，仅需计算一次。这能将计算复杂度从)降为,这种优化也叫做循环无变化的代码移动(LICM, “Loop Invariant Code Motion”)，一种常见的编译器优化。

现在，考虑一下在多核处理器的情况下，能否通过并行执行加速？如果将第06行并行执行——将相应的i值和norm函数一起交给n个计算单元同时算，就可以将串行的n个周期缩短为并行的1个周期，速度应该大大提升。

实现起来也很容易，如前所述，只需要将for前面加上#pragma omp parallel for，或者将for换成cilk_for。 支持OpenMP或Cilk的主流编译器，都可以轻松编译，实现并行计算。 这种并行循环的场景非常典型。

编译器同样应该进行“代码移动”优化，把norm函数搬到循环外先计算，以降低计算复杂度。但GCC5.3.0、ICC16.0.3和Cilk Plus/LLVM3.9.0都没有这么做。编译成并行运行，速度有时候比串行还差。在AWS c4.8xLarge, 18核，n=64M（循环64M次）上的运行结果如下：

  1. 未做并行处理：原程序运行时间：0.312秒；
  2. 并行处理，18核：将for换成cilk_for，用Cilk Plus/LLVM版，运行180.657秒；
  3. 并行处理，1核：运行2600秒！
  4. 并行处理，18核：用OpenMP，LLVM4.0，运行0.205秒，好一些，但不明显；

这些主流编译器都支持分叉-汇合的并行机制，但对并行部分的代码的优化，为什么反而不如对串行部分做得好？哪里出了问题？

LLVM编译器

典型的LLVM编译器包括三大部分：前端（和实际编程语言相关），后端（和实际芯片或硬件平台相关）以及中间语言（Intermediate Representation）。下图分别是通用型、基于多核并行扩展Cilk Plus和基于NVidia CUDA的三种C语言编译器的LLVM结构。

麻省理工学院优化LLVM IR，大大提高并行化的效率

以第一种通用C编译器为例，前端负责类型检查和解析，将程序翻译成中间语言IR（Intermediate Code），中间语言经过优化器，进行分析和优化的多次遍历，将IR转换得更高效。一般来说，这些优化不涉及最终执行的计算机指令集。最后，后端进行底层和机器相关的优化，将优化的IR转化为机器代码（在CUDA等架构下，最后转化为PTX这样的代码，用来控制底层虚机）。

问题

根据麻省理工学院2017年2月发表的一篇论文，问题可能出在这些编译器遇到可并行部分代码的标记时，是如何处理的。

比如，受前文提到的“串行语义”所限 ，要确保无论是串行或并行，执行结果都一样，GCC、ICC和Cilk Plus/LLVM都将并行部分的代码放在前端处理。让我们回到前面的归一化函数：前端看到cilk_for的汇总-分叉关键字，知道希望将这部分代码成并行执行，就会把第05-06行的循环转换成两步：

1）第06行的循环执行内容被装进一个辅助函数。（Helper Function，把常用的计算或功能打包，以便多次调用）；

2）第05-06行的循环本身，被替换成调用一个Cilk Plus Runtime库函数。循环的上下边界和辅助都作为这个Runtime库函数的参数。该函数负责把n次循环迭代转化为n个并行任务，同时执行。

问题是循环的内容被打包了，优化器针对循环优化的扫描看不到被打包的norm函数，也就无法采用代码移动（LICM）进行优化。通过对比归一化 PClang可以看到：Cilk Plus的并行化的编译，没做任何代码移动，所以执行速度比串行还慢。

OpenMP采用的是同样的两步，不同的是，对辅助函数（Helper Function）内部进行了代码移动，即把norm函数放到循环之前计算。但并没有把norm函数搬到整个并行化之前，所以并行后每个核仍需要各自先算一遍norm，仍然不是最佳优化方案。

所以，问题出在主流编译器“先解决并行化，再扫描和优化”的顺序不合理。遇到可并行处理部分的关键字时，就把他们作为语法糖（syntactic suger)过早地打包，等Runtime库函数调用执行。等优化器进行分析和优化时，要么看不到（Cilk Plus/LLVM），要么只能在语法糖的包内进行局部优化（OpenMP），都不够彻底。 这种语法糖的做法也可以看做intrinsic funciton。

该问题在LLVM开发社区2017年1月也有一个较受关注的讨论“IR-层面的注释”：

解决办法-Tapir

麻省理工大学的计算机科学和人工智能实验室在LLVM开源编译器的基础上，进行修改，并开发了一个新的版本Tapir。 他们将并行部分的代码直接嵌入编译器的中间语言IR里，以便充分利用编译器后端对所有代码分析和优化，而不把并行代码作为语法糖那样下推到Runtime库函数。

这样做，编译器的代码转换处理并行部分可能出问题。之前也有开发者在现有的IR上拓展，但还没有获得成功，比如用内部函数（intrinsic functions)、或者建立一套完全不同的IR来描述带有并行的抽象语法树。

麻省理工学院的做法包括两大部分： 新增三个IR代码，并放弃全部并行，将程序流程转换成一种局部并行、总体串行的非对称结构。

三个IR更确切地表达分叉-汇合

这三个新增的LLVM中间代码IR是：detach, reattache和sync：

  1. detach和Cilk的”spawn”类似，用来开始分叉，从串行转为并行；
  2. reattache说明一个并行代码块里的语句执行完毕后，再执行哪一块代码。
  3. sync用来同步本部分的并行部分，等本部分的并行任务执行完毕之后，再往下走。

编译时，Cilk plus代码先通过修改过的前端PClang，产生带有三个新IR的中间代码（Tapir），再通过优化器进行优化(如LICM，重复表达式替换等高层优化），之后将Tapir编译成通用的LLVM中间代码IR（包括下推至Runtime函数调用等），然后像以前一样，再对LLVM IR进行分析和优化，最后转化成机器代码。

麻省理工学院优化LLVM IR，大大提高并行化的效率

感兴趣的朋友可以去Github下载，本文所引用的论文附录里有使用说明。

对称和非对称型控制流程图(Control Flow Graph)

Tapir的另一个重要思路，是放弃并行的最大化，仅在局部保证并行，而整体控制流保持串行。

让我们看一个典型的并行计算场景：计算菲波那切数列中的第n个元素的递归函数fib。

int fib(int n) {
if (n < 2) return n;
int x, y;
x = cilk_spawn fib(n - 1);
y = fib(n - 2);
cilk_sync;
return x + y;
}

x=fib(n-1)和y=fib(n-2)这两部分逻辑上可以并行执行，如A图，但Tapir采取的流程控制图如B图。

麻省理工学院优化LLVM IR，大大提高并行化的效率

对称和非对称型控制流程图

非对称意味着两个方面： 一是通过reattache指令，将det和cont这两块程序用reattach这条边连接起来，使得本来可以并行执行的det和cont两个指令块，先后串行，先跑det，再跑cont。

二是确保在并行程序块里的变量，不能被并行块之外的程序访问。 比如cont里的指令无法直接访问并行的det里的x0, 而要通过外部的虚拟寄存器x传递： x1=load x;

为什么这样做呢？ 原因之一是为了尽可能少地修改优化器里的80多个分析和优化扫描代码。这些长期积累的机制，是为非并行代码设计的。所以LLVM采用语法糖的办法先将并行代码按语法糖下推，可以方便地沿用串行的分析和优化器。而现在如果在IR里保留并行代码，不下推，必须保证新IR（Tapir)经过分析、优化以及代码转换后，每个代码块的执行结果不改变，且不带来额外的并行读写竞争(determinacy race)。

那么，一个很自然的想法，就是尽量保持程序的大块的串行顺序不变，仅将可以并行的部分，转化为局部并行。并行部分的数据放在局部寄存器里，外部串行指令不可以直接访问，而只能从内部传递给共享内存，以避免优化和代码转换带来额外的并行读写竞争。

对LLVM优化器的修改

即使这样，用于串行程序的分析、优化部分也需要少量修改，增加一些限制。比如，优化器可能将某些指令的执行前后顺序改变。如果将本来应该串行的变量赋值，移到并行部分，就有可能由于并行访问时间不同，产生该变量不确定（determinacy races)。

因此，Tapir对LLVM的分析部分进行了相应修改，在变量别名分析（alias analysis)部分，将detach/sync对应的指令块，作为函数处理，以免优化器错误地将串行部分的变量赋值移到并行部分里。而将reattach作为前后代码的分割边界，不允许优化器将后面的代码移到reatache之前，反之亦然。

另外，程序里占用时间最多的是循环，如何将一大堆指令流转简化为一两个嵌套的循环？ 支配分析（Dominator analysis）是必需的一步–逐一确定程序里每个节点的状态，由之前的哪些节点决定？ 对于每个指令而言，哪些变量的值是确定的？由于并行部分的不确定性，并行部分的寄存器值不可以作为确定值放在支配树里。

而Tapir的控制流程图里因为有了Continue这条边，可以完全沿用现在的算法，无需修改。 因为Continue将detach和reattach的指令块连起来，自然而然地形成两条通向reattache代码块的路径。 因此计算reattache代码块的支配节点可以完全沿用LLVM的串行分析器，像If语句分叉那样处理，而不会把并行部分误认为一定是支配树的一部分。

对于本文最开始举的归一化例子，因为将归一化的计算代码直接嵌入IR代码中，优化器中已有的LICM扫描能发现，并将Norm函数计算移到循环之外，从而缩短计算用时。不过，需要对LICM优化器做一个小小的修改。 LICM需要对循环结束之前的所有支配节点进行扫描。

但是如前文的“支配分析”里描述的，Continue这条边让并行部分的代码不属于支配节点，因此，对LICM优化的代码需要进行以下修改: 进行LICM扫描时，对并行循环按串行模式优化，也就是说，在寻找循环结束之前的支配节点时，忽略Continue这条边，这仅仅需要修改25行代码。

结论

同样用前文的AWS 18核平台，Intel Cilk Plus Runtime，重复试验，用Tapir代替Cilk Plus/LLVM进行编译:

  1. 未做并行处理：原程序运行时间：0.312秒；
  2. 并行处理，18核：将for换成cilk_for，用LLVM/Tapir编译，运行0.081秒；
  3. 并行处理，1核：运行0.321秒。

之所以这个并不复杂的想法一直没人去做，主要是人们担心需要对编译器的分析/优化部分做大量修改–LLVM里，有80多种不同的优化分析扫描，有多少需要修改？ 据Leiserson博士团队里的博士后Tao B. Schardl和计算机/物理双学位本科生William S. Moses说，“这证明了传统的想法完全错了。出乎意料的是，分析和优化的80多种扫描，并不需要全部改写。T.B.和Billy仅仅修改了4百多万行代码里的6千行。” 其中，900行用来定义这三个新IR，三千多行修改了Runtime的函数调用，而对中间阶段的分析和优化，仅仅改动了2千行左右。比如前文提到的归一化循环LICM优化，仅仅需要修改25行LLVM的代码。

后记

本文不是为了对比Tapir、OpenMP或Cilk Plus在并行开发上的孰优孰劣，而是介绍Tapir这样一个通过语言拓展和改造LLVM编译器来方便并行开发的做法。这篇《Embedding Fork-Join Parallelism into LLVM’s Intermediate Representation》论文对许多大型、复杂的软件系统开发者也许有所启发，比如在LLVM框架下如何考虑竞争、一致、安全、扩展、维护等方面。

当然，每个软件产品的开发背景不同，设计思路也大不一样。比如用某种GPU框架有针对性地加速时，考虑更多的可能是如何通过厂商提供的LLVM获得高效的PTX，来实现某些计算函数，以及高效的任务并行和数据交换。而一开始就构建在并行计算平台的业务开发，就无需过多考虑退化到单核和优化器的扩展性。

虽然Tapir还是个非常早期的尝试，只对80多种优化扫描中的一部分进行了深入的评估和修改，不过麻省理工电子工程和计算机科学系教授Charles E. Leiserson认为, 这种编译器“能比其他商用或开源的编译器，更好地对并行代码优化，而且能编译一些编译器无法编译的内容”。似乎只需要对已有优化和分析机制做少量修改，并可以方便地对并行代码进行更多优化，值得继续关注。

转自 http://www.infoq.com/cn/articles/optimization-of-mi-on-llvm-ir

相关推荐