On Recovering Multi-Dimensional Arrays in Polly

Tobias Grosser, Sebastian Pop, J Ramanujam, P Sadayappan

Research output: Contribution to conferencePaperpeer-review

Abstract / Description of output

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.
Original languageEnglish
Number of pages9
Publication statusPublished - 19 Jan 2015
EventFifth International Workshop on Polyhedral Compilation Techniques - Amsterdam, Netherlands
Duration: 19 Jan 201519 Jan 2015


WorkshopFifth International Workshop on Polyhedral Compilation Techniques
Abbreviated titleImpact 2015
Internet address


Dive into the research topics of 'On Recovering Multi-Dimensional Arrays in Polly'. Together they form a unique fingerprint.

Cite this