Optimistic Delinearization of Parametrically Sized Arrays

Tobias Grosser, J. Ramanujam, Louis-Noel Pouchet, Ponnuswamy Sadayappan, Sebastian Pop

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A number of legacy codes make use of linearized array references (i.e., references to one-dimensional arrays) to encode accesses to multi-dimensional arrays. This is also true of a number of optimized libraries and the well-known LLVM intermediate representation, which linearize array accesses. In many cases, the only information available is an array base pointer and a single dimensional offset. For problems with parametric array extents, this offset is usually a multivariate polynomial. Compiler analyses such as data dependence analysis are impeded because the standard formulations with integer linear programming (ILP) solvers cannot be used. In this paper, we present an approach to delinearization, i.e., recovering the multi-dimensional nature of accesses to arrays of parametric size. In case of insufficient static information, the developed algorithm produces run-time conditions to validate the recovered multi-dimensional form. The obtained access description enhances the precision of data dependence analysis. Experimental evaluation in the context of the LLVM/Polly system using a number of benchmarks reveals significant performance benefits due to increased precision of dependence analysis and enhanced optimization opportunities that are exploited by the compiler after delinearization.
Original languageEnglish
Title of host publicationProceedings of the 29th ACM on International Conference on Supercomputing
Number of pages10
ISBN (Electronic)9781450335591
Publication statusPublished - 8 Jun 2015
Event2015 International Conference on Supercomputing - Newport Beach, United States
Duration: 8 Jun 201511 Jun 2015

Publication series



Conference2015 International Conference on Supercomputing
Abbreviated titleICS 2015
Country/TerritoryUnited States
CityNewport Beach
Internet address


Dive into the research topics of 'Optimistic Delinearization of Parametrically Sized Arrays'. Together they form a unique fingerprint.

Cite this