[LLVMdev] Alternate instruction sequences

[Gergö Barany]

On Wed, Nov 09, 2011 at 09:52:38 +0100, cafxx wrote:
> In this case, wouldn't it be interesting to 
> be able to insert into the IR all (or some of) the alternate versions, 
> mark them as such and defer the decision about which one will be used 
> after all optimizations have run?

If you're interested in this kind of thing, you might want to have a look at
these papers:

Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. 2009. Equality
saturation: a new approach to optimization. In Proceedings of the 36th
annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
(POPL '09). ACM, New York, NY, USA, 264-276. DOI=10.1145/1480881.1480915
http://doi.acm.org/10.1145/1480881.1480915

Michael Stepp, Ross Tate, and Sorin Lerner. 2011. Equality-based translation
validator for LLVM. In Proceedings of the 23rd international conference on
Computer aided verification (CAV'11), Ganesh Gopalakrishnan and Shaz Qadeer
(Eds.). Springer-Verlag, Berlin, Heidelberg, 737-742.
Doi: 10.1007/978-3-642-22110-1_59
http://dx.doi.org/10.1007/978-3-642-22110-1_59

The first one talks about such optimizations for Java bytecode, while the
second one is about translation validation for LLVM. However, they use the
same framework, so I'm guessing optimizations for LLVM should also be within
reach. Their framework builds a graph representing a large number of
alternate versions of the same program, and optimization is essentially the
task of selecting a "best" alternative.

-- 
Gergö Barany, research assistant                   gergo at complang.tuwien.ac.at
Institute of Computer Languages        http://www.complang.tuwien.ac.at/gergo/
Vienna University of Technology                         Tel: +43-1-58801-58522
Argentinierstrasse 8/E185, 1040 Wien, Austria           Fax: +43-1-58801-18598