llvm dev - Dec 2009 - [LLVMdev] 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

On Dec 13, 2009, at 4:25 PM, John Regehr wrote:
> 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
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev