project idea: llvm superoptimizer

Here's an idea for a research project that I thought I'd put out there since probably nobody in my group will have time to follow up on it.

It would be interesting to take ideas from this superoptimizer for x86:

   http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf
   http://theory.stanford.edu/~sbansal/superoptimizer.html

and adapt them to run on LLVM code.

It would seem that operating on LLVM code would save a lot of time because its semantics are much simpler than x86. The cost of operating on LLVM is that target-specific tricks would be missed.

The outcome would be a new LLVM pass that subsumes at least the instruction combiner, and probably a few other passes as well. Benefits would include not missing cases missed by the current combiner and also more easily adapting to changes in the LLVM IR.

All previous superoptimizers have worked on linear sequences of code. It would seem much better to operate on small subgraphs of the program dependency graph. I haven't worked out the details...

John Regehr

thanks, I added this to http://www.llvm.org/OpenProjects.html

-Chris