Loop transformations such as tiling, parallelization or vectorization are essential tools in the quest for high-performance program execution. Precise data dependence analysis is required to determine whether the compiler can apply a transformation or not. In particular, current static analyses typically fail to provide precise enough dependence information when the code contains indirect memory accesses or polynomial subscript functions to index arrays. is leads to considering super uous may-dependences between instructions that prevent many loop transformations to be applied. In this work we present a new hybrid (static/dynamic) framework that allows to overcome several limitations of purely static dependence analyses: For a given loop transformation, we statically generate a test to be evaluated at runtime. is test allows to determine whether the transformation is valid, and if so triggers the execution of the transformed code, falling back to the original code otherwise. Such test, originally constructed as a loop-based code with O (n 2 ) iterations (n being the number of iterations of the original loop-nest), are reduced to a loop-free test of O (1) complexity thanks to a new quanti er elimination scheme that we introduce in this paper. e precision and low overhead of our method is demonstrated over 25 kernels. •Computing methodologies →Symbolic and algebraic algorithms; •So ware and its engineering →Compilers;
Very recently, Sampaio et al. REF suggested using a complex hybrid (static and dynamic) framework in order to overcome the limitations of purely static dependence-analysis techniques.
Simplification and runtime resolution of data dependence constraints for loop transformations
ICS '17
Computer Science