GLORE: generalized loop redundancy elimination upon LER-notation

This paper presents GLORE, a novel approach to enabling the detection and removal of large-scoped redundant computations in nested loops. GLORE works on LER-notation, a new representation of computations in both regular and irregular loops. Together with a set of novel algorithms, it makes GLORE able to systematically consider computation reordering at both the expression level and the loop level in a unified manner. GLORE shows an applicability much broader than prior methods have, and frequently lowers the computational complexities of some nested loops that are elusive to prior optimization techniques, producing significantly larger speedups.

本文介绍了GLORE，这是一种用于检测和消除嵌套循环中大规模冗余计算的新方法。GLORE基于LER表示法开展工作，LER表示法是一种对规则和不规则循环中的计算进行表示的新方式。结合一系列新颖的算法，GLORE能够以统一的方式，系统地在表达式层面和循环层面考虑计算重排序。GLORE的适用范围比先前的方法广泛得多，并且常常能降低一些嵌套循环的计算复杂度，而这些嵌套循环对于先前的优化技术来说难以处理，GLORE可带来显著得多的加速效果。