多面体模型代码生成算法研究

Code Generation Based on Polyhedra Model

编译器中的多面体模型优化框架通常会产生复杂的迭代域,从这些迭代域中生成代码的质量直接影响到优化的效果,现有的优化多基于重叠迭代空间分割,然而这种方法难以控制优化层次,容易为无利可图的变换生成体积膨胀的代码,反而会导致指令缓存命中率下降,影响代码的整体运行效率.针对该问题提出一种新的多面体扫描算法,基于严格数学理论对多面体约束条件进行变换,通过消除循环边界计算开销来执行优化,通过控制优化所涉及的嵌套深度以控制代码冗余度,从而可以在不造成代码体积膨胀的情况下进一步提高代码执行效率.通过仿真实验验证了算法的有效性.

The quality of the code generated from complex iteration spaces which are created by the loop transformation framework based on polyhedral model is crucial to the effect of the whole optimization work. The state-of-the-art optimizing methods usually use overlapping iteration space splitting technology, but it can hardly control the optimizing level, as a result it may generate inflated codes for some unworthy transformation, which may decrease the hit rate of the instruction cache and slow down the execution of the result codes. This paper presents a new polyhedral scanning algorithm which do transformations to the restrictions of the polyhedra models based on strict math theories. It can generate faster code by eliminating the overhead of loop bounds calculation. It can also avoid the code expansion by limiting the optimization range based on loop nesting depth. We compare with the CodeGen ＋ on three loop nest computations, demonstrating that this algorithm can generate better code as we expect.