Improving compiler scalability: Optimizing large programs at small price

Sanyam Mehta, Pen-Chung Yew

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

6 Scopus citations


Compiler scalability is a well known problem: reasoning about the application of useful optimizations over large program scopes consumes too much time and memory during compilation. This problem is exacerbated in polyhedral compilers that use powerful yet costly integer programming algorithms to compose loop optimizations. As a result, the benefits that a polyhedral compiler has to offer to programs such as real scientific applications that contain sequences of loop nests, remain impractical for the common users. In this work, we address this scalability problem in polyhedral compilers. We identify three causes of unscalability, each of which stems from large number of statements and dependences in the program scope. We propose a one-shot solution to the problem by reducing the effective number of statements and dependences as seen by the compiler. We achieve this by representing a sequence of statements in a program by a single super-statement. This set of super-statements exposes the minimum sufficient constraints to the Integer Linear Programming (ILP) solver for finding correct optimizations. We implement our approach in the PLuTo polyhedral compiler and find that it condenses the program statements and program dependences by factors of 4.7x and 6.4x, respectively, averaged over 9 hot regions (ranging from 48 to 121 statements) in 5 real applications. As a result, the improvements in time and memory requirement for compilation are 268x and 20x, respectively, over the latest version of the PLuTo compiler. The final compile times are comparable to the Intel compiler while the performance is 1.92x better on average due to the latter's conservative approach to loop optimization.

Original languageEnglish (US)
Title of host publicationPLDI 2015 - Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation
EditorsSteve Blackburn, David Grove
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781450334686
StatePublished - Jun 3 2015
Event36th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2015 - Portland, United States
Duration: Jun 13 2015Jun 17 2015

Publication series

PublisherAssociation for Computing Machinery (ACM)
ISSN (Print)1523-2867


Other36th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2015
Country/TerritoryUnited States


  • Compiler scalability
  • O-molecule
  • Optimization
  • Polyhedral model
  • Statement condensation


Dive into the research topics of 'Improving compiler scalability: Optimizing large programs at small price'. Together they form a unique fingerprint.

Cite this