[LLVMdev] project idea: llvm superoptimizer

[John Regehr]

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