[LLVMdev] GSoC 2011: Superoptimization for LLVM IR
regehr at cs.utah.edu
Thu Apr 7 08:09:40 PDT 2011
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.
More information about the llvm-dev