[LLVMdev] GSoC 2011: Superoptimization for LLVM IR

[John Regehr]

A bit of feedback on this proposal:

It worries me that you talk about "extending the number of 
transformations."  The point of a superoptimizer is that it has no 
specific model of transformations.  Rather, it is simply looking for cheap 
code fragments that are equivalent to expensive ones.

You have not specified how you will perform equivalence checking between 
code sequences.  The best answer that I know of is to use the technique 
from the Bansal and Aiken paper, which is to translate bitcode sequences 
into a SAT or SMT instance and just ask if they are equivalent functions.

You have not specified the cost model that you will use to assess the 
desirability of each potential transformation.  Simply replacing larger 
sequences with smaller ones is not necessarily a good idea since you may 
end up replacing a series of shift operations with a division. or 
something like that.

A linear sequence of LLVM instructions is perhaps not the best starting 
point.  A better primitive unit of code would be a subgraph of the PDG. 
This will ensure that the superoptimizer is looking at instructions that 
are semantically related.  Also, you will need to consider dependencies in 
any case to make this work, so you might as well do it from the outset.

John Regehr