Phitchaya Phothilimthana and Aditya Thakur and Ras Bodik and Dinakar Dhurjati

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2015-14

April 10, 2015

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-14.pdf

A superoptimizer searches for an optimal implementation for a given input program in a target instruction set architecture (ISA). Despite its ability to generate optimal code, a superoptimizer is not commonly implemented for further optimizing code generated by a compiler. This is because building a superoptimizer for a new ISA requires a large amount of effort, and finding optimal code can be extremely slow if the search technique is inefficient.

We propose GreenThumb, an extensible framework for building superoptimizers. All that is required to extend GreenThumb to a new ISA is the implementation of an emulator for the new ISA. GreenThumb provides an efficient hybrid search technique that combines existing superoptimizer search techniques: symbolic search and mutation-based search. Additionally, we design a new correctness cost function (or fitness function), which is used in the mutation-based search, that leads to a more efficient search.

To illustrate the flexibility of the framework, we instantiate GreenThumb to two very different ISAs: ARM and GreenArrays. We evaluate the performance of the new hybrid search compared to the existing approaches in terms of speed and consistency of finding optimal solutions on a number of ARM and GreenArrays programs. We find that the hybrid search is the only search technique that finds an optimal program for all GreenArrays benchmarks, and the new cost function increases the number of runs in which the superoptimizer finds an optimal program by 20% on ARM benchmarks.

---

BibTeX citation:

@techreport{Phothilimthana:EECS-2015-14,
    Author= {Phothilimthana, Phitchaya and Thakur, Aditya and Bodik, Ras and Dhurjati, Dinakar},
    Title= {Superoptimizer Construction Framework with Efficient Hybrid Search},
    Year= {2015},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-14.html},
    Number= {UCB/EECS-2015-14},
    Abstract= {A superoptimizer searches for an optimal implementation for a given input program in a target instruction set architecture (ISA). Despite its ability to generate optimal code, a superoptimizer is not commonly implemented for further optimizing code generated by a compiler. This is because building a  superoptimizer for a new ISA requires a large amount of effort, and finding optimal code can be extremely slow if the search technique is inefficient.

We propose GreenThumb, an extensible framework for building superoptimizers. All that is required to extend GreenThumb to a new ISA is the implementation of an emulator for the new ISA.  GreenThumb provides an efficient hybrid search technique that combines existing superoptimizer search techniques: symbolic search and mutation-based search. 
Additionally, we design a new correctness cost function (or fitness function), which is used in the mutation-based search, that leads to a more efficient search.

To illustrate the flexibility of the framework, we instantiate GreenThumb to two very different ISAs: ARM and GreenArrays. We evaluate the performance of the new hybrid search compared to the existing approaches in terms of speed and consistency of finding optimal solutions on a number of ARM and GreenArrays programs. We find that the hybrid search is the only search technique that finds an optimal program for all GreenArrays benchmarks, and the new cost function increases the number of runs in which the superoptimizer finds an optimal program by 20% on ARM benchmarks.},
}

EndNote citation:

%0 Report
%A Phothilimthana, Phitchaya 
%A Thakur, Aditya 
%A Bodik, Ras 
%A Dhurjati, Dinakar 
%T Superoptimizer Construction Framework with Efficient Hybrid Search
%I EECS Department, University of California, Berkeley
%D 2015
%8 April 10
%@ UCB/EECS-2015-14
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-14.html
%F Phothilimthana:EECS-2015-14