多面体模型是编译器循环优化的未来吗？

相信很多人都听说过：程序80%的运行时间用来执行20%的代码。循环几乎占一般应用程序运行时间的绝大部分。优化程序中有关循环尤其是关键循环的代码将会给程序的性能带来很大的提升。而且这种循环优化是目标机器无关的，任何对循环的一点点优化都会在所有编译器支持的目标机上带来性能提升。所以编译器上的循环优化一直是研究的热点。

目前针对循环的变换可以分成以下几种loop interchange（循环交换)、loop peeling/splitting(循环分割)、loop fusion(循环合并)、loop fission(循环分裂)、loop unroll(循环分割)、loop unswitch、loop inversion、loop tiling、vectorization(自动向量化)、software pipeline(软流水)、loop parallelization(循环并行).其中，本博已经有一篇关于Open64自动向量化的文章。关于Open64的循环优化，也有一篇文章介绍《Open64课程-循环嵌套优化(LNO) 》。有感兴趣的可以点击查看。维基百科也有关于循环优化的介绍。等有机会本博会写文章一一介绍这些循环变换。

工业编译器内比较成熟的循环优化是传统的优化。Open64的循环优化就是这种传统优化，即依次完成上述循环变换中的一个或者几个。这种方式的优点是简单，易实现。缺点则是有些循环变换之间可能存在相互影响，造成循环变换的效果不理想，而且生成的代码并不高效。缺乏形式化的，统一的理论基础。

多面体模型(Polyhedral Framework)就是一种将循环映射到数学上的多面体模型中。在利用数学上已经非常完备和正确的多面体理论，做各种形式的变换。再将其重新映射会程序中循环的一种循环优化方式，它几乎覆盖了上面提到的所有循环变换。GCC，Open64都已经有了自己的多面体循环优化代码,分别是Graphite和WRaP-IT。GCC在4.5版本中已经包含了一部分多面体代码(GCC 4.5 Release Note)。LLVM 也有了将GCC多面体优化代码引入的计划。Open64的多面体优化代码一直没有进入官方代码库，现在需要修改才能编译运行。IBM XL C 编译器将在下一个版本中包含多面体优化。几乎主流的编译器都在做。

多面体模型相比其他的优点(摘自某牛人PPT)：

• 强大的自动并行化/数据局部性优化的工具
• 可以一步完成一系列比较复杂的循环体优化
• 可以做精确的数据依赖分析，即分析语句每一次执行之间的数据依赖关系
• 多面体几何模型的理论很完备，可以直接加以利用

有了这些优势，有多面体模型优化的编译器能从容的利用现代通用处理器中某些特性，如强大的并行性、依赖分析和局部性优化可以大大提升多核平台上的并行性，降低cache的缺失率。完备的理论也为编译器引入多面体模型做循环优化的正确性提供了保证。

那么如何把循环表示成多面体模型的形式？多面体模型在编译器中又是如何使用的呢？

如上图(摘自某牛人ppt)，每个for循环就相当于迭代空间中的一个纬度。每个点，就是语句3的一次迭代执行。上图就是一个二维多面体。通过这种机制，编译器就可以为每条语句建立相应的迭代空间。并通过左下的方式生成一个仿射函数表示一个多面体迭代空间。

多面体模型中的若干数学变换就可以对应循环中的若干变换，然后通过这些变换实现循环优化。另外，可以将一个多面体切割为多个多面体的形式，实现并行化。当然数据依赖也会在切割和变换的过程中做恒变换。这些都通过特定的约束来保证。这部分太复杂，而且我也不太懂，就对不住各位了。点到为止。

多面体循环优化在GCC中的阶段

GCC多面体循环优化的内部架构

上面两张图介绍了GCC中多面体循环优化在GCC编译流程中的位置，和内部架构。共七部分组成

• SCoP detection:静态控制部分(Static Control Parts)检测
• SCoPs:静态控制部分生成
• GPOLY constructions：为每个SCoP构建多面体中间表示。
• GPOLY：进行数据依赖分析和转换
• Legality Check Transformations：检测转换是否等价
• transformed GPOLY
• GLOOG：将GPOLY转换回GIMPLE

现阶段多面体模型用于循环优化还存在的不足：

• 健壮性！多面体模型现在虽然已经在各大编译器中都有涉及，但是因为都是刚刚起步，还需要一段时间的测试、验证和开发才能真正用于实际生产
• 性能还是大问题。据在IBM 参与开发多面体模型优化的牛人介绍，他们做出的实际编译器，编译测试结果在spec CPU 2006 标准性能测试集上只有两个例子有5%的性能提升。不过这只是他们刚刚把真个架构做出来时能拿到的性能。希望经过若干优化和调试后，能获得更多的性能提升。
• 效率问题也不小。虽然多面体模型能够胜任很多循环变换。但并不是每个变换都会带来性能提升，而且不同的变换组合所带来的性能提升也不确定，而且说不好会有性能下降。另外，一些有参数的循环变换，比如循环展开，要展开多少次合适？这些都需要在多面体模型中通过代价模型来描述和衡量，这样就会有个搜索空间的问题。这么多变换，这么多参数，虽然会有些经验可以降低复杂度，但搜索一个最佳或者稍好点的变换组合都将带来不小的开销。据上面的牛人介绍他们的架构做出来之后，编译时间增加了20%。
• 另外，有些使用多面体模型需要解决的问题现在还都是NP完全问题，即使有比较投机和经验主义的方法，但毕竟也会带来效率问题。比如前面提到的使用多面体分割来实现多核并行。这一刀切在多面体上，就需要保证切开的两个多面体之间数据依赖要尽可能的少，以便减少两个核之间的通信和同步开销，而且两个多面体要差不多大，以便做到负载均衡。这才是一刀切，对于双核而言。那四个核呢？8个核呢？众核呢？
• 理论太过高深。上面提到的牛人说，IBM这款编译器中的这个模块，大概有几十万行代码，代码量很大。很难理解。大部分做这个模块的人可能都还没有完全理解这个模型。这提高了入门门槛。

健壮性和性能，虽然我们可以慢慢的调出来。但编译的效率问题决定了这个机制也有很大的局限。

多面体模型会是循环优化未来吗？不好说！我期待肯定的答复。就像连续傅立叶变换把对时域信号带到了频域，但因为它是连续，而且全等的形式意味着有无穷大的频率波形。但后来又有了离散傅立叶变幻，快速傅立叶，离散小波，才有了今天丰富多彩的多媒体应用。多面体模型的现在和连续傅立叶的曾经差不多。。。。。。。

PS：以上内容有些出自今天听的一个小讲座以及讲座过程中诸位牛人的讨论。并非完全出自本人理解。特澄清。因为篇幅太大,除全文引用处给出注释外，没有一一详细指出。

参考

• http://en.wikipedia.org/wiki/Loop_optimization
• GRAPHITE Two Years After First Lessons Learned From Real-World Polyhedral Compilation，Konrad Trifunovic

相关文章:

• 前瞻-LLVM大事记(2004-2010)
• 期待未来-一张趣图
• Google的野心–Native Client+LLVM
• Open64课程-循环嵌套优化(LNO)
• 认识静态链接库
• 《编译点滴》恭祝各位龙年大吉
• 通用微处理中的SIMD指令扩展
• Open64课程-结语
• 说说静态单赋值（SSA,Static Single-Assignment)
• 计算机系统结构方向的顶尖会议