On Recovering Multi-Dimensional Arrays in Polly
Tobias Grosser, Sebastian Pop, Jagannathan Ramanujam, Ponnuswamy Sadayappan · 2015
Although many programs use multi-dimensional arrays, the multi-dimensional view of data is often not directly visible in the internal representation used by LLVM. In many situations, the only information available is an array base pointer and a single dimensional oset. For problems with parametric size, this oset is usually a multivariate polynomial that cannot be analyzed with integer linear programming (ILP) solvers and consequently impedes the computation of precise data dependences. In this paper, we present an approach to recover the multidimensional nature of accesses to arrays of parametric size. In case of insucient static information, the developed algorithm produces the necessary run-time conditions to validate the recovered multi-dimensional form. The access description obtained signicantly simplies the dependence checks, making previously polynomial dependence problems precisely solvable by a linear solver. Our approach has been evaluated using a number of benchmarks from polybench (C99), boost::ublas (C++) and Julia.