[LLVMdev] GSoC 2011: Superoptimization for LLVM IR

[Duncan Sands]

Hi Rafael,

> Methodology
>
> There is already a superoptimizer for LLVM in initial stages of development.
> The existing superoptimizer currently limits its search space to a few transfor-
> mations. This project will focus on improving this current superoptimizer by
> extending the number of transformations applied and thus greatly increasing
> the search space.

it would be great if you could extend my superoptimizer to do fully general
superoptimization.

> In order to test the superoptimizer efficiency, it will use LLVM bitcodes
> compiled from the entire LLVM test suite and SPEC to harvest possible code
> sequence optimizations. When successfully identified, these optimizations could
> be implemented directly as peephole optimizations for LLVM IR.

Right, this is exactly what has been done with the existing superoptimizer,
which, in spite of its simplicity, discovered a lot of commonly occurring
simplifications in SPEC, the LLVM testsuite and the Ada ACATS testsuite.  A
bunch of these were implemented in LLVM 2.9, mostly in InstructionSimplify.

> • 1st month, 1st week - Study the LLVM IR in order to establish a
> list of axioms, that is, valid transformations that determine the search
> algorithm capability. There is an important trade-off to investigate here,
> since using fewer transformations will lead to faster searches, but several
> good optimizations may be missed.

It sounds like you are planning to follow the approach of Joshi, Nelson and
Randall ("Denali: A Goal-directed Superoptimizer") in that you don't intend
to exhaustively enumerate all possible code sequences, and see if they are
the same as the original only better; but instead start from the original code
sequence and repeatedly apply transformations that change code to equivalent
code, looking to see if you can eventually get something better than the
original.  Is that right?

Ciao, Duncan.