<div style="color: rgb(0, 0, 0); margin-top: 8px; margin-right: 8px; margin-bottom: 8px; margin-left: 8px; background-image: initial; background-attachment: initial; background-origin: initial; background-clip: initial; background-color: rgb(255, 255, 255); ">
<h1 style="font-size: 2em; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="color: windowtext; font-size: large; ">1.</span><span style="color: windowtext; "><span style="font-size: large; "><span>  </span>Summary</span><br>
</span></h1><p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="font-size: 12pt; line-height: 18px; "><span style="font-size: small; ">I will implement two optimizations in the LLVM compiler, both based on runtime profile information: an inlining mechanism that takes the call frequency into consideration, and a better basic block placement algorithm.</span></span></p>
<p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="font-size: 12pt; line-height: 18px; "><span style="font-size: small; "><br></span></span></p>
<h1 style="font-size: 2em; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="color: windowtext; "><span style="font-size: large; ">2. The project</span><br></span></h1><p class="MsoNormal" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; ">
<span style="font-size: small; "><span><span class="Apple-tab-span" style="white-space: pre; "> </span><span class="Apple-style-span" style="line-height: 14px; ">LLVM now includes an efficient framework [1] for instrumenting an application and collecting edge and path profile information. Profile-guided optimizations present an opportunity for improving the performance of the application in a significant way, but until now no real optimization was developed/adapted to take advantage of this profile information (there is a</span><i style="line-height: 14px; ">BasicBlockPlacement</i><span class="Apple-style-span" style="line-height: 14px; "> pass, but it can be considered naïve).</span></span></span></p>
<p class="MsoNormal" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="line-height: 14px; font-size: small; "><span class="Apple-tab-span" style="white-space: pre; ">     </span>The first part of my project consists in implementing a function inlining pass that takes advantage of function call frequency, if available. Function inlining is one of the most important optimizations nowadays, reducing call overhead and enhancing a series of classic optimizations that are usually inhibited by calls. Although it is desirable to inline as many of the calls as possible, a limit must be imposed, otherwise application performance might suffer as a result of excessive code size growth and instruction cache misses [2]. In taking these decisions the current heuristic can be improved by considering the number of times the function to be inlined was actually called:</span></p>
<p class="MsoNormal" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="line-height: 14px; font-size: small; ">  -</span><span class="Apple-style-span" style="font-size: small; "><span style="line-height: 14px; font-family: Wingdings; "><span><span style="font: normal normal normal 7pt/normal 'Times New Roman'; ">  </span></span></span><span style="line-height: 14px; ">A function that was not called at all, or was called below a certain threshold should not be inlined, or at least be penalized.</span></span></p>
<p class="MsoNormal" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span class="Apple-style-span" style="font-size: small; "><span style="line-height: 14px; ">  - </span></span><span class="Apple-style-span" style="line-height: 14px; font-size: small; ">A function that is called frequently should always be inlined, or at least get a bonus, so it has a higher chance of being inlined.</span></p>
<p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="line-height: 14px; font-size: small; ">I will use the algorithm presented in [3] because, according to the benchmarks presented in the paper, the performance improvement can be up to 57% compared to inlining without any profile information, all this with a maximum of 10% code size growth. The second reason is that the algorithm takes into consideration the cost of performing inlining at a call site, functionality which is already provided by the <i>InlineCost </i>analysis.<i></i></span></p>
<p class="MsoNormal" style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="line-height: 14px; font-size: small; "><span class="Apple-tab-span" style="white-space: pre; ">     </span>The algorithm will be implemented as a new optimization pass, which will perform the following sequence of operations:<br>
<br></span><span class="Apple-style-span" style="font-size: small; "><span style="line-height: 14px; "><span><span class="Apple-tab-span" style="white-space: pre; ">     </span>1. <span style="font: normal normal normal 7pt/normal 'Times New Roman'; "> </span></span></span><span style="line-height: 14px; ">Determine a maximum cost for the whole inlining process. This can be<i>S * 1.1</i>, where <i>S </i>is the estimated size of the application (this can be an estimate of the total number of instructions, the way<i>CodeMetrics::analyzeBasicBlock</i> does it). </span></span><span class="Apple-style-span" style="font-size: small; "><span class="Apple-style-span" style="line-height: 14px; ">Multiplying by</span><i style="line-height: 14px; "> 1.1</i><span class="Apple-style-span" style="line-height: 14px; "> means that a code growth of maximum 10% is allowed, which has been shown to be more than enough. If optimization for size is enabled we could allow a code growth of only 1%, which still provides most of the benefits.<br>
<br></span></span><span class="Apple-style-span" style="font-size: small; "><span style="line-height: 14px; "><span><span class="Apple-tab-span" style="white-space: pre; ">        </span>2.<span style="font: normal normal normal 7pt/normal 'Times New Roman'; ">      </span></span></span><span style="line-height: 14px; ">Determine the call sites, and for each one a <i>benefit/cost</i> ratio, where <i>benefit</i> is the number of times the calee was actually called, and <i>cost</i>is the estimated cost of the inlining, as computed by the <i>InlineCost </i>analysis. The<i> call site/ratio</i> pairs are then inserted into a max-heap, because they are needed by the algorithm in decreasing-ratio order, and also because the ratio of a call site may change due to an inlining decision, which can be implemented efficiently in a heap (decrease-key).<br>
<br></span></span><span class="Apple-style-span" style="font-size: small; "><span style="line-height: 14px; "><span><span class="Apple-tab-span" style="white-space: pre; ">        </span>3.<span style="font: normal normal normal 7pt/normal 'Times New Roman'; ">      </span></span></span><span style="line-height: 14px; ">Run the actual algorithm, which can be formulated as a knapsack-like problem: <span> </span>the call sites are chosen in a greedy fashion, based on the<i>benefit/cost</i> ratio, until the maximum cost is achieved (or no more call sites are available). After the calee is inlined, all call sites that may be affected by the inlining decision must be updated.</span></span></p>
<p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="line-height: 14px; font-size: small; ">The <i>benefit/cost ratio </i>formula<i> </i>most likely<i> </i>won’t be that simple, because it must also take into consideration attributes like <i>alwaysinline</i>,<i>noinline</i>, and <i>optsize</i>. Also, functions with an extremely high cost should not be inlined, even if they are called frequently. This will be fine-tuned in the later stages of the project.<br>
<br></span></p><p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="line-height: 14px; font-size: small; ">The second optimization I will implement is a better basic block placement algorithm compared to the current one. The algorithm will be <i>Algo2</i>from [4], with better results than <i>Algo1</i>, the one implemented now in the<i>BasicBlockPlacement </i>pass, according to the paper. Basic block placement using profile information is very helpful especially for control-intensive functions, and functions where many blocks are executed infrequently or not at all (debugging/error handling code, for example). Reordering the basic blocks helps reducing branch penalties, which is very important in today’s heavily pipelined CPUs. It also helps reducing instruction cache misses, because the instruction stream is denser and the unlikely code is moved to a “cold” place of the function. The performance improvements are between 2-15% for most applications.</span></p>
<p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="font-size: 12pt; line-height: 18px; "><span style="font-size: small; ">The basic idea of the algorithm is that it forms chains of basic blocks that should be placed as a group of straight-line code in a bottom-up fashion. After these chains are computed, the doubly-linked list of basic blocks is changed to reflect the order in the chains.</span><br>
<br></span></p><p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="font-size: 12pt; line-height: 18px; "> <br></span><span class="Apple-style-span" style="font-weight: bold; font-size: large; ">3.<span>  </span>Benefits for LLVM</span></p>
<p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span class="Apple-style-span" style="font-size: small; "><br></span></p><p class="MsoNormal" style="text-indent: 0.5in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; ">
<span class="Apple-style-span" style="font-size: small; ">- <span class="Apple-style-span" style="line-height: 14px; font-size: small; ">The optimizations I propose provide tangible performance benefits, unlike other profile guided optimizations that are worth performing only for a small number of applications, or may degrade performance if they introduced code growth that can’t be accounted for with more optimization opportunities (superblocks formation, for example).</span></span></p>
<p class="MsoNormal" style="text-indent: 0.5in; "><span class="Apple-style-span" style="font-size: small; font-family: Verdana, Arial, Helvetica, sans-serif; "><span class="Apple-style-span" style="line-height: 14px; font-size: small; ">- </span></span><span class="Apple-style-span" style="line-height: 14px; font-size: small; font-family: Verdana, Arial, Helvetica, sans-serif; ">Taking advantage of the many opportunities opened by profile-guided optimizations.</span></p>
<p class="MsoNormal" style="text-indent: 0.5in; "><span class="Apple-style-span" style="line-height: 14px; font-size: small; font-family: Verdana, Arial, Helvetica, sans-serif; ">- I</span><span style="font-size: 12pt; line-height: 18px; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="font-size: small; ">nspiring other developers to implement other profile-guided optimizations.</span></span></p>
<p class="MsoListParagraphCxSpLast" style="text-indent: -0.25in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span style="font-size: 12pt; line-height: 18px; "><span style="font-size: small; "><br>
</span></span></p><h1><span style="color: windowtext; "><span style="font-size: large; font-family: Verdana, Arial, Helvetica, sans-serif; ">4. Success criteria</span></span></h1><h1><span style="color: windowtext; "><span style="font-family: Verdana, Arial, Helvetica, sans-serif; "></span><span class="Apple-style-span" style="font-weight: normal;"><font class="Apple-style-span" size="2">- </font></span><span class="Apple-style-span" style="line-height: 14px; font-size: small; font-weight: normal; "><font class="Apple-style-span" face="Verdana, Arial, Helvetica, sans-serif">Implement both optimizations described above.</font></span></span></h1>
<h1 style="font-size: 2em; font-family: Verdana, Arial, Helvetica, sans-serif; "><span class="Apple-style-span" style="font-size: 10px; font-weight: normal; "><span class="Apple-style-span" style="line-height: 14px; font-size: small; ">- Pass test suite with both optimizations enabled.</span></span></h1>
<h1 style="font-size: 2em; font-family: Verdana, Arial, Helvetica, sans-serif; "><span class="Apple-style-span" style="font-size: 10px; font-weight: normal; "><span class="Apple-style-span" style="line-height: 14px; font-size: small; ">- </span></span><span class="Apple-style-span" style="line-height: 14px; font-size: small; font-weight: normal; ">Performance with profile-guided inlining enabled should exceed the one obtained with the standard inlining pas. </span></h1>
<p class="MsoListParagraphCxSpMiddle" style="text-indent: -0.25in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span class="Apple-style-span" style="font-size: small; "><span style="line-height: 14px; ">     - </span></span><span class="Apple-style-span" style="line-height: 18px; font-size: small; ">Performance with the new block placement algorithm should exceed the one obtained with the current placement algorithm.</span></p>
<p class="MsoListParagraphCxSpLast" style="text-indent: -0.25in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span><span style="font-size: small; line-height: 14px; "></span></span></p><h1 style="font-size: 2em; font-family: Verdana, Arial, Helvetica, sans-serif; ">
<span style="color: windowtext; "><span style="font-size: large; "><br></span></span></h1><h1 style="font-size: 2em; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="color: windowtext; "><span style="font-size: large; ">5. Road-map</span><br>
</span></h1><p class="MsoListParagraphCxSpFirst" style="text-indent: -0.25in; line-height: 18px; font-size: 12pt; "><span style="font-size: small; "><span style="line-height: 14px; "><font class="Apple-style-span" face="Verdana, Arial, Helvetica, sans-serif">     -</font><font class="Apple-style-span" face="Wingdings"> </font></span></span><span class="Apple-style-span" style="line-height: 14px; font-size: small; "><font class="Apple-style-span" face="Verdana, Arial, Helvetica, sans-serif">Week 1 – 6: I will implement the inlining optimization first, because it should bring greater benefits. First the cost limit and call sites are identified, then the actual implementation of the algorithm can be done.</font></span></p>
<p class="MsoListParagraphCxSpFirst" style="text-indent: -0.25in; line-height: 18px; font-size: 12pt; "><span class="Apple-style-span" style="line-height: 14px; font-size: small; "><font class="Apple-style-span" face="Verdana, Arial, Helvetica, sans-serif">     - </font></span><span class="Apple-style-span" style="line-height: 14px; font-size: small; font-family: Verdana, Arial, Helvetica, sans-serif; ">Week 7 – 9: Test the inlining optimization for correctness and performance improvements. I will adjust the heuristic in order to increase the performance gains and to take into consideration things like the <i>noinline</i> attribute and other heuristics.</span></p>
<p class="MsoListParagraphCxSpFirst" style="text-indent: -0.25in; line-height: 18px; font-size: 12pt; "><span class="Apple-style-span" style="line-height: 14px; font-size: small; font-family: Verdana, Arial, Helvetica, sans-serif; ">     - </span><span class="Apple-style-span" style="font-family: Verdana, Arial, Helvetica, sans-serif; line-height: 14px; font-size: small; ">Week 10-13: Implement the basic block positioning optimization and test for correctness and for any performance improvement. If all works well I will replace the current algorithm with the new one.</span></p>
<p class="MsoListParagraphCxSpLast" style="text-indent: -0.25in; line-height: 18px; font-size: 12pt; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="font-size: small; "><span style="line-height: 14px; font-family: Wingdings; "><span>§</span></span></span><span style="line-height: 14px; font-size: small; ">    -</span><span class="Apple-style-span" style="line-height: 14px; font-size: small; ">Week 14: At the end I will do some final tests, improve the formatting and readability of the code, and write documents describing the implementation.</span></p>
<p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "></p><p class="MsoListParagraphCxSpLast" style="text-indent: -0.25in; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; ">
<span><span style="font-size: small; line-height: 14px; "></span></span></p><h1 style="font-size: 2em; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="color: windowtext; "><span style="font-size: large; "><br>
</span></span></h1><h1 style="font-size: 2em; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="color: windowtext; "><span style="font-size: large; ">6. Biography</span><br></span></h1><p class="MsoNormal" style="text-indent: 0.5in; line-height: 18px; font-size: 12pt; font-family: Verdana, Arial, Helvetica, sans-serif; ">
<span style="line-height: 14px; font-size: small; ">I’m a 3^rd year Computer Science student from Romania, at the “Lucian Blaga” University. I’ve been always interested in low level programming, especially optimization, compilers and operating systems. The last 8 months I spent developing a fully functional compiler for the <i>C99</i> language (full language support – except complex numbers, but could be easily added). In its current status it’s capable of parsing and generating the intermediate code for <i>SqlLite3</i> and other open-source applications and libraries. The backend shares some design decisions with LLVM, like the use of SSA as the intermediate format and the high modularity. <span> </span>As it is now, it consists of about 90K lines of C++ code. While I didn’t write an optimization pass for LLVM yet, I’ve read a lot of its code and most of the documentation, and I can say I’m quite familiar with the way it works. Of course I will stop working on my compiler while I work for LLVM, there’s more than a year until I have my dissertation.</span></p>
<p class="MsoNormal" style="text-indent: 0.5in; line-height: 18px; font-size: 12pt; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="line-height: 14px; font-size: small; ">Last year I implemented a memory allocator optimized for multiprocessors. In most tests it is about 15% faster than the one included with Intel Thread Building Blocks, while using about half the memory compared to the ones that come with glibc/Visual C++. This was tested on a 4-core machine, and now I hope to get the chance to test it on the 48 core supercomputer at my university, and maybe publish a paper.</span></p>
<p class="MsoNormal" style="text-indent: 0.5in; line-height: 18px; font-size: 12pt; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="line-height: 14px; font-size: small; "></span><span class="Apple-style-span" style="line-height: 14px; font-size: small; ">In high school I implemented an application for the secure deletion of files (most notable is that it included a partial implementation of the NTFS file system). With this application I won the first price at a student competition at the university I’m attending now.</span></p>
<p class="MsoNormal" style="text-indent: 0.5in; line-height: 18px; font-size: 12pt; font-family: Verdana, Arial, Helvetica, sans-serif; "><span class="Apple-style-span" style="line-height: 14px; font-size: small; "><br> </span></p>
<p class="MsoNormal" style="font-size: small; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="line-height: 14px; font-size: small; "><i></i></span><span class="Apple-style-span" style="font-weight: bold; line-height: 14px; font-size: large; "><strong><br>
8. References</strong></span></p><p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "></p><h1 style="font-size: 12pt; line-height: 18px; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="color: windowtext; "></span></h1>
<p class="MsoNormal" style="line-height: 18px; font-size: 12pt; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="line-height: 14px; font-size: small; ">[1] Andreas Neustifte, <i>Efficient Profiling in the LLVM Compiler Infrastructure</i>, 2010</span></p>
<p class="MsoNormal" style="line-height: 18px; font-size: 12pt; font-family: Verdana, Arial, Helvetica, sans-serif; "><span style="line-height: 14px; font-size: small; "></span><span class="Apple-style-span" style="line-height: 14px; font-size: small; ">[2] Matthew Arnold, Stephen Fink, Vivek Sarkar, Peter F. Sweeney, <i>A Comparative Study of Static and Profile-Based Heuristics for Inlining</i>, 2000</span></p>
<p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span class="apple-style-span" style="line-height: 14px; font-size: small; "><span style="line-height: 14px; color: black; ">[3] Pohua P. Chang, Scott A. Mahlke, William Y. Chen, Wen-Mei W. Hwu,<i>Profile-guided Automatic Inline Expansion for C Programs</i>, 1992</span></span></p>
<p style="font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10px; "><span class="apple-style-span" style="line-height: 14px; font-size: small; "><span style="line-height: 14px; color: black; ">[4] Karl Pettis, Robert C. Hansen, <i>Profile Guided Code Positioning</i>, 1990</span></span></p>
</div>