麻省理工学院优化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 forfor (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次）上的运行结果如下： 未做并行处理：原程序运行时间：0.312秒； 并行处理，18核：将for换成cilk_for，用Cilk Plus/LLVM版，运行180.657秒； 并行处理，1核：运行2600秒！ 并行处理，18核：用OpenMP，LLVM4.0，运行0.205秒，好一些，但不明显； 这些主流编译器都支持分叉-汇合的并行机制，但对并行部分的代码的优化，为什么反而不如对串行部分做得好？哪里出了问题？ LLVM编译器 典型的LLVM编译器包括三大部分：前端（和实际编程语言相关），后端（和实际芯片或硬件平台相关）以及中间语言（Intermediate Representation）。下图分别是通用型、基于多核并行扩展Cilk Plus和基于 NVidia CUDA 的三种C语言编译器的LLVM结构。 以第一种通用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： detach和Cilk的"spawn"类似，用来开始分叉，从串行转为并行； reattache说明一个并行代码块里的语句执行完毕后，再执行哪一块代码。 sync用来同步本部分的并行部分，等本部分的并行任务执行完毕之后，再往下走。 编译时，Cilk plus代码先通过修改过的前端PClang，产生带有三个新IR的中间代码（Tapir），再通过优化器进行优化(如LICM，重复表达式替换等高层优化），之后将Tapir编译成通用的LLVM中间代码IR（包括下推至Runtime函数调用等），然后像以前一样，再对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图。 对称和非对称型控制流程图 非对称意味着两个方面： 一是通过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进行编译: 未做并行处理：原程序运行时间：0.312秒； 并行处理，18核：将for换成cilk_for，用LLVM/Tapir编译，运行0.081秒； 并行处理，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认为, 这种编译器“能比其他商用或开源的编译器，更好地对并行代码优化，而且能编译一些编译器无法编译的内容”。似乎只需要对已有优化和分析机制做少量修改，并可以方便地对并行代码进行更多优化，值得继续关注。 感谢麦克周对本文的审校。