I was wondering, is there any way to express in the IR that an instruction/instruction sequence/basic block/region/function/module/whatever is an alternate version of another? e.g. let's keep things simple and say that I have an instruction I. An optimization pass reads it and could be able to produce one or more functionally-equivalent instructions I1, ..., In without being really able to ascertain which one is "best" w.r.t. the optimization goal. While this could be true even for a single, isolated, pass it's all the more true for chains of optimizations (i.e. 'which one of the alternate instructions will be the "best" after all other optimizations have run?'). 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? B.r., Carlo Alberto
On Nov 9, 2011, at 12:52 AM, cafxx wrote:> I was wondering, is there any way to express in the IR that an > instruction/instruction sequence/basic > block/region/function/module/whatever is an alternate version of > another?There is not a way to represent --- instruction I1 is an alternative for instruction I2 --- in LLVM IR. - Devang> e.g. let's keep things simple and say that I have an > instruction I. An optimization pass reads it and could be able to > produce one or more functionally-equivalent instructions I1, ..., In > without being really able to ascertain which one is "best" w.r.t. the > optimization goal. While this could be true even for a single, isolated, > pass it's all the more true for chains of optimizations (i.e. 'which one > of the alternate instructions will be the "best" after all other > optimizations have run?'). 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? > B.r., > Carlo Alberto > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Wed, 09 Nov 2011 09:27:30 -0800, Devang Patel wrote:> On Nov 9, 2011, at 12:52 AM, cafxx wrote: > >> I was wondering, is there any way to express in the IR that an >> instruction/instruction sequence/basic >> block/region/function/module/whatever is an alternate version of >> another? > > There is not a way to represent --- instruction I1 is an alternative > for instruction I2 --- in LLVM IR.Could there be any interest in this functionality? Do you think bending the meaning of existing constructs like select i1 undef, <ty> <val0>, <ty> <val1> (for instructions) or switch i1 undef, label <bb0>, i1 1, label <bb1> (for basic blocks) could be feasible/acceptable?
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