Difference between revisions of "Superoptimizing Compilers"

From Superoptimization
Jump to: navigation, search
Line 15: Line 15:
 
# Hand-calculate benefit from superoptimization, comparing the different techniques
 
# Hand-calculate benefit from superoptimization, comparing the different techniques
 
# Document the generalized process to demonstrate repeatability
 
# Document the generalized process to demonstrate repeatability
 +
 +
== Introduction ==
 +
 +
Superoptimization is an idea which produces perfectly optimal code, in place of the code we currently have generated by compilers. This is typically done via a bruteforce search of every possible instruction sequence, checking whether it performs the desired actions and accepting the sequence if it is the optimal one.
 +
 +
The problem is clearly very difficult, exploding in size as the length of the instruction sequence increases. However, superoptimization gaining traction as a method of optimizing programs. In this feasibility study we hope to find which techniques are extensible enough to bring out of the academic community to be using in a commercial setting. This means that the superoptimizer needs to be able to handle all the corner cases that may arise in production code. If it turns out that superoptimization is not currently feasibly, by the end of the project we will have a research roadmap describing what will need to be done next.
 +
 +
  
 
== Support ==
 
== Support ==

Revision as of 10:13, 2 July 2014

A proof of concept superoptimizer that considers all features of a modern processor.

Welcome

This Wiki is for a research project that is developing a proof of concept superoptimizer, as the basis of a future more complete implementation that can be integrated with existing compilers and used in production environments.

The initial research project will run from 02nd June to 1st October 2014 and is being undertaken by Embecosm.

Goals

The goals of the project can be summarised as:

  1. Identify code that can be superoptimized (for speed, size or energy) focusing on finding awkward constructs
  2. Design a peephole optimization to integrate a superoptimizer into GCC and/or LLVM
  3. Hand-calculate benefit from superoptimization, comparing the different techniques
  4. Document the generalized process to demonstrate repeatability

Introduction

Superoptimization is an idea which produces perfectly optimal code, in place of the code we currently have generated by compilers. This is typically done via a bruteforce search of every possible instruction sequence, checking whether it performs the desired actions and accepting the sequence if it is the optimal one.

The problem is clearly very difficult, exploding in size as the length of the instruction sequence increases. However, superoptimization gaining traction as a method of optimizing programs. In this feasibility study we hope to find which techniques are extensible enough to bring out of the academic community to be using in a commercial setting. This means that the superoptimizer needs to be able to handle all the corner cases that may arise in production code. If it turns out that superoptimization is not currently feasibly, by the end of the project we will have a research roadmap describing what will need to be done next.


Support

This research is supported by the UK Technology Strategy Board.

Contact

Any enquiries should be directed in the first instance to info@embecosm.com.