Hybrid Optimizations: Which Optimization Algorithm to Use?

John Cavazos, J. Eliot B. Moss, Michael O'Boyle

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


We introduce a new class of compiler heuristics: hybrid optimizations. Hybrid optimizations choose dynamically at compile time which optimization algorithm to apply from a set of different algorithms that implement the same optimization. They use a heuristic to predict the most appropriate algorithm for each piece of code being optimized. Specifically, we construct a hybrid register allocator that chooses between linear scan and graph coloring register allocation. Linear scan is more efficient, but sometimes less effective; graph coloring is generally more expensive, but sometimes more effective. Our setting is Java JIT compilation, which makes optimization algorithm efficiency particularly important.

Our hybrid allocator decides, based on features of a method, which algorithm to apply to that method. We used supervised learning to induce the decision heuristic. We evalute our technique within Jikes RVM [1] and show on average it outperforms graph coloring by 9% and linear scan by 3% for a typical compilation scenario. To our knowledge, this is the first time anyone has used heuristics induced by machine learning to select between different optimization algorithms.
Original languageEnglish
Title of host publicationCompiler Construction
Subtitle of host publication15th International Conference, CC 2006, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006, Vienna, Austria, March 30-31, 2006. Proceedings
EditorsJohn Cavazos, J. Eliot B. Moss, Michael F. P. O’Boyle
PublisherSpringer Berlin Heidelberg
Number of pages15
ISBN (Electronic)978-3-540-33051-6
ISBN (Print)978-3-540-33050-9
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Hybrid Optimizations: Which Optimization Algorithm to Use?'. Together they form a unique fingerprint.

Cite this