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 offset. For problems with parametric size, this offset 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 insufficient static information, the developed algorithm produces the necessary run-time conditions to validate the recovered multi-dimensional form. The access description obtained significantly simplifies 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.
|Number of pages||9|
|Publication status||Published - 19 Jan 2015|
|Event||Fifth International Workshop on Polyhedral Compilation Techniques - Amsterdam, Netherlands|
Duration: 19 Jan 2015 → 19 Jan 2015
|Workshop||Fifth International Workshop on Polyhedral Compilation Techniques|
|Abbreviated title||Impact 2015|
|Period||19/01/15 → 19/01/15|