Phase Directed Compiler Optimizations

Era Jain, Subhajit Roy

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

Abstract

Profile-guided optimizing compilers learn from representative executions of a program to 'tune' transformations so as to benefit frequent paths. However, these optimizations view the whole run of a program in a monolithic manner. It is known that a program execution proceeds in phases - each phase corresponding to an identifiable set of control-flow behaviors. This implies that not all control-flows are hot (i.e. executed with a high frequency) all the times. Hence, if a program can switch among a set of hot paths for guiding the optimizations in the different phases, the optimizations may yield powerful results. We propose an algorithm that optimizes the clones of a function according to the different phase behaviors exhibited by the function, and dispatches its calls to the (potentially) most beneficial clone at runtime. This makes it possible to use profile information at a finer granularity than existing approaches. We start off by identifying critical functions that exhibit a high differential in its control-flow profiles, thereby exhibiting widely varying phase behavior. For these critical functions, we compile specialized clones that are tuned for each distinct phase behavior. Finally, we build a phase predictor that, at run-time, predicts the phase that a yet-to-be-executed function invocation would evoke (when executed), and guides the function invocation to the respective clone of the function. We build the predictor by learning a classifier over features extracted from the state of the program with the distinct phases acting as class labels. We demonstrate our algorithm by building a concrete phase-directed optimizer for register allocation (pdra) within the PBQP-based register allocator in the LLVM compiler infrastructure. We compare our allocator against the base allocator and a profile-guided allocator (pgra) that uses the profile information in a monolithic manner without extracting phase information.

Original languageEnglish (US)
Title of host publicationProceedings - 23rd IEEE International Conference on High Performance Computing, HiPC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages270-279
Number of pages10
ISBN (Electronic)9781509054114
DOIs
StatePublished - Feb 1 2017
Event23rd IEEE International Conference on High Performance Computing, HiPC 2016 - Hyderabad, India
Duration: Dec 19 2016Dec 22 2016

Publication series

NameProceedings - 23rd IEEE International Conference on High Performance Computing, HiPC 2016

Conference

Conference23rd IEEE International Conference on High Performance Computing, HiPC 2016
CountryIndia
CityHyderabad
Period12/19/1612/22/16

Keywords

  • compiler optimizations
  • machine learning
  • register allocation

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Phase Directed Compiler Optimizations'. Together they form a unique fingerprint.

  • Cite this

    Jain, E., & Roy, S. (2017). Phase Directed Compiler Optimizations. In Proceedings - 23rd IEEE International Conference on High Performance Computing, HiPC 2016 (pp. 270-279). [7839692] (Proceedings - 23rd IEEE International Conference on High Performance Computing, HiPC 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HiPC.2016.039