<div>I am no llvm/compiler/optimization-expert and not able to mentor this project -<br></div><div>I just want to say that this sounds very interesting and I'm hoping that maybe someone</div><div>else could mentor it, or, at least, leave some useful comments, as it sounds like</div>
<div>something that could improve llvm a lot - doesn't it?</div><br><div class="gmail_quote">2011/4/6 Rafael Auler <span dir="ltr"><<a href="mailto:rafaelauler@gmail.com">rafaelauler@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div>Hello, </div><div><br></div><div>I want to present my project for GSoC 2011 for LLVM below. It would be very nice to hear suggestions and your opinion, thanks!</div><div><br></div><div>Superoptimization for LLVM IR</div>
<div><br></div><div>Objective</div><div><br></div><div>This project focuses on implementing superoptimization algorithms targeted at</div><div>the LLVM IR. The project uses arbitrary LLVM bitcode as a training set to</div>
<div>discover new peephole optimizations that can be later integrated into LLVM</div><div>instruction simplify phase or as a separate peephole optimization pass.</div><div><br></div><div>Motivation</div><div><br></div><div>
Code optimization is the task of using a faster sequence of instructions which</div><div>compute the same information, compared to a previous code sequence. The old</div><div>sequence may then be substituted by the new one, creating a faster program</div>
<div>with the same behavior. The problem of finding a code sequence that does some</div><div>computation in optimal time is undecidable and, in practice, optimizations are</div><div>discovered by humans using analytical reasoning. Finding new optimizations in</div>
<div>an automated fashion, using a search algorithm, is a different approach to the</div><div>problem and became known in literature as superoptimization, term coined by</div><div>Massalin [2].</div><div>Using computer-aided optimization discovery, different kind of optimizations</div>
<div>unnoticed by humans may be detected, specially those specific to the target</div><div>machine code [1]. This project will focus on implementing a superoptimizer</div><div>which will exhaustively investigate new optimizations for the LLVM IR. Using</div>
<div>this approach, I hope to greatly contribute to the current LLVM instruction</div><div>simplify phase, introducing new substitutions identified in this project.</div><div><br></div><div><br></div><div>Methodology</div>
<div><br></div><div>There is already a superoptimizer for LLVM in initial stages of development.</div><div>The existing superoptimizer currently limits its search space to a few transfor-</div><div>mations. This project will focus on improving this current superoptimizer by</div>
<div><div>extending the number of transformations applied and thus greatly increasing</div><div>the search space.</div><div><br></div><div>In order to test the superoptimizer efficiency, it will use LLVM bitcodes</div><div>
compiled from the entire LLVM test suite and SPEC to harvest possible code</div><div>sequence optimizations. When successfully identified, these optimizations could</div><div>be implemented directly as peephole optimizations for LLVM IR.</div>
<div><br></div><div>Timeline</div><div><br></div><div>This project is expected to last three months, as follows.</div><div><br></div><div>• 1st month, 1st week - Study the LLVM IR in order to establish a</div><div>list of axioms, that is, valid transformations that determine the search</div>
<div>algorithm capability. There is an important trade-off to investigate here,</div><div>since using fewer transformations will lead to faster searches, but several</div><div>good optimizations may be missed.</div><div>• 1st month, 2nd week - Thorough study of the current implemented</div>
<div>base and new algorithm design to support arbitrary transformations.</div><div>• 1st month, 3rd week until end of project - Implementation of the</div><div>search algorithm.</div><div>• 2nd month - Test phase begins. Test algorithm with simple transforma-</div>
<div>tions searching for optimized code sequences.</div><div>• 3rd month - Harvesting new optimizations and implementing fixes to</div><div>the search algorithm as more performance feedback from training data is</div><div>
received.</div><div><br></div><div>Biography</div><div><br></div><div>I am a Master student at the University of Campinas (UNICAMP), Brazil (time-</div><div>zone GMT -3). In my master thesis, I have already worked with superoptimiza-</div>
<div>tion theory and automatic code sequence searching. But instead of using it for</div><div>optimization purposes, I use this to automatically generate a LLVM backend</div><div>based on a machine description using the ArchC architecture description lan-</div>
<div>guage. The backend patterns are fixed and the implementation of the pattern</div><div>is inferred using a search algorithm similar to the one used on superoptimizers.</div><div>Thus, I have experience both on superoptimizer theory and LLVM code.</div>
<div><br></div><div><br></div><div>References</div><div><br></div><div>[1] Sorav Bansal and Alex Aiken. Automatic generation of peephole superopti-</div><div>mizers. SIGPLAN Not., 41:394–403, October 2006.</div></div><div>
<br></div><div><div>[2] Henry Massalin. Superoptimizer: a look at the smallest program. In</div><div>ASPLOS-II: Proceedings of the second international conference on Architec-</div><div>tual support for programming languages and operating systems, pages 122–</div>
<div>126, Los Alamitos, CA, USA, 1987. IEEE Computer Society Press.</div></div><div><br></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br>