麻省理工学院扩展LLVM IR使并行程序可得到更好的优化

Fork-join parallelism 是一种组织并行程序的方式，它特别适合于分而治之的算法，比如归并排序。 通过一组语言扩展，例如由 OpenMP （比如#pragma omp parallel和#pragma omp parallel等等）和 Cilk Plus（比如cilk_spawn 和 cilk_sync）提供的扩展，GCC和LLVM之类的主流编译器内均可支持fork-join parallelism。这些编译器前端处理这些语言扩展到“较低层”并行结构到更原始的表示，然后转化成IR。例如，以下代码片段使用Cilk cilk_for扩展使之可以并行运行该循环的每次迭代：

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

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

这种方式的其中一个缺点是，虽然编译器中端再也看不到循环了，但运行期调用是不透明的，它提取自己函数内的代码块传入库函数，该库函数处理大量生成的循环迭代并随后同步。这实际上妨碍了中端针对循环在IR层进行的各类优化，比如循环不变式代码调整、调度等。

Schardl、Moses和 Leierson的工作是通过一个扩展的IR直接将fork-join模型放入中端，这使之前需要由并行处理添加额外代码的代码可以应用所有各类优化策略了。这种方式本身并不新颖，几个特殊的IR已经特别设计以表示程序内的并行了，然而：

……在主流编译器中使用单独的IR一直以来都受非议，因为策划、开发和维护这个额外的IR到像编译器已有的串行IR同样的标准需要付出相当大的工作量。

关键是麻省理工学院的三位研究人员已经找到了扩展LLVM的IR的方法，即通过保留它们的串行语言去表示逻辑任务并行。他们新的IR被称为Tapir，代表并行任务不对称，这表示并行任务必须在执行流程能被同步之前率先完成，从而使LLVM之类的串行中端可以去高效地优化并行代码，这些研究人员们说。

Tapir通过增加三个新命令扩展LLVM的IR：detach、reattach和sync。虽然detach大致相当于像fork一样的抽象，但是reattach 和 sync所代表的与join稍有不同。由于目的在于实现可串行化这一需求，所以并行计算必须确保分离锁在分支续延之前执行完成。因此，虽然detach和reattach表示一个并行任务的开发和结束，但是同步任务的同步是在其并行上下文内发生的。

为了评估他们这些新方法的好处，麻省理工学院的研究员们比较了Cilk-enabled LLVM编译器和Tapir-enabled的LLVM编译器，用它们同时去编译一组20个Cilk程序的套件。

在这20个程度中的17个，使用新IR的编译器产出了更高效的软件，其中三分之一提升了10%到25%。而新编译器所产出的更低效率的软件，其下降幅度也仅低于2%。

在GitHub上可以获得Tapir，可运行以下命令进行构建：

git clone --recursive https://github.com/wsmoses/Tapir-Meta.git
cd Tapir-Meta/
./build.sh
source ./setup-env.sh

查看英文原文：MIT Extended LLVM IR to Enable Better Optimization of Parallel Programs