Abstract
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 language | English |
---|---|
Title of host publication | Proceedings of the 29th ACM on International Conference on Supercomputing |
Publisher | ACM |
Pages | 351-360 |
Number of pages | 10 |
ISBN (Electronic) | 9781450335591 |
DOIs | |
Publication status | Published - 8 Jun 2015 |
Event | 2015 International Conference on Supercomputing - Newport Beach, United States Duration: 8 Jun 2015 → 11 Jun 2015 http://www.cs.ucr.edu/~ics15/ |
Publication series
Name | ICS |
---|
Conference
Conference | 2015 International Conference on Supercomputing |
---|---|
Abbreviated title | ICS 2015 |
Country/Territory | United States |
City | Newport Beach |
Period | 8/06/15 → 11/06/15 |
Internet address |