Building a Polyhedral Representation from an Instrumented Execution: Making Dynamic Analyses of Nonaffine Programs Scalable
Building a Polyhedral Representation from an Instrumented Execution: Making Dynamic Analyses of Nonaffine Programs Scalable
复制标题
从仪表化执行构建多面体表示：使非仿射程序的动态分析可扩展
DOI：
10.1145/3363785
复制
发表时间：
2020
影响因子：
1.6
通讯作者：
Rastello, Fabrice
中科院分区：
文献类型：
--
作者：
Selva, Manuel;Gruber, Fabian;Sampaio, Diogo;Guillon, Christophe;Pouchet, Louis-Noël;Rastello, Fabrice
该多面体模型已成功地应用于生产编译器中。然而，只有非常有限的一类应用程序可以从中受益。最近的建议研究了如何使用运行时信息对不静态拟合模型的应用程序应用多面体优化。在这项工作中，我们朝这个方向又迈进了一步。我们提出了基于折叠的分析，从仪器程序执行的输出，建立一个紧凑的多面体表示。它能够准确地检测程序中的仿射依赖关系、固定步幅内存访问和归纳变量。它可以扩展到现实生活中的应用程序，这些应用程序通常包括一些非仿射的依赖关系和其他仿射代码中的访问。这是通过安全的细粒度多面体超逼近机制实现的。我们在整个Rodinia基准套件上评估我们的分析，从而能够准确地反馈复杂多面体转换的潜力。
The polyhedral model has been successfully used in production compilers. Nevertheless, only a very restricted class of applications can benefit from it. Recent proposals investigated how runtime information could be used to apply polyhedral optimization on applications that do not statically fit the model. In this work, we go one step further in that direction. We propose thefolding-based analysisthat, from the output of an instrumented program execution, builds a compact polyhedral representation. It is able to accurately detect affine dependencies, fixed-stride memory accesses, and induction variables in programs. It scales to real-life applications, which often include some nonaffine dependencies and accesses in otherwise affine code. This is enabled by a safe fine-grained polyhedral overapproximation mechanism. We evaluate our analysis on the entire Rodinia benchmark suite, enabling accurate feedback about the potential for complex polyhedral transformations.