LLVM has gained much popularity in the programming languages and compiler industry from the time it is developed. Lots of researchers have used LLVM as frameworks for their researches and many languages have been ported to LLVM IR and interpreted, Just-in-Time compiled or statically compiled to native code. One of the current drawbacks of the LLVM JIT is the lack of an adaptive compilation System. All the non-adaptive bits are already there in LLVM: optimizing compiler with the different types of instruction selectors, register allocators, preRA schedulers, etc. and a full set of optimizations changeable at runtime. What’s left is a system that can keep track of and dynamically look-up the hotness of methods and re-compile with more expensive optimizations as the methods are executed over and over. This should improve program startup time and execution time and will bring great benefits to all ported languages that intend to use LLVM JIT as one of the execution methods
Currently, the LLVM JIT serves as a management layer for the executed LLVM IR, it manages the compiled code and calls the LLVM code generator to do the real work. There are levels of optimizations for the LLVM code generator, and depends on how much optimizations the code generator is asked to do, the time taken may vary significantly. The adaptive compilation mechanism should be able to detect when a method is getting hot, compiling or recompiling it using the appropriate optimization levels. Moreover, this should happen transparently to the running application. In order to keep track of how many times a JITed function is called. This involves inserting instrumentational code into the function’s LLVM bitcode before it is sent to the code generator. This code will increment a counter when the function is called. And when the counter reaches a threshold, the function gives control back to the LLVM JIT. Then the JIT will look at the hotness of all the methods and find the one that triggered the recompilation threshold. The JIT can then choose to raise the level of optimization based on the algorithm below or some other algorithms developed later.
IF (getCompilationCount(method) > 50 in the last 100 samples) = > Recompile at Aggressive
ELSE Recompile at the next optimization level.
Even though the invocation counting introduces a few lines of binary, but the advantages of adaptive optimization should far overweigh the extra few lines of binary introduced. Note the adaptive compilation framework I propose here is orthogonal to the LLVM profile-guided optimizations. The profile-guided optimization is a technique used to optimize code with some profiling or external information. But the adaptive compilation framework is concerned with level of optimizations instead of how the optimizations are to be performed.
This is a relatively small project and does not involve a lot of coding, but good portion of the time will be spent benchmarking, tuning and experimenting with different algorithms, i.e. what would be the algorithm to raise the compilation level when a method recompilation threshold is reached, can we make this algorithm adaptive too, etc. Therefore, my timeline for the project is as follow
Benchmarking the current LLVM JIT compiler, measuring compilation speed differences for different levels of compilation. This piece of information is required to understand why a heuristic will outperform others
Reading LLVM Execution Engine and Code Generator code. Design the LLVM adaptive compilation framework
Week 3 - 9
Implementing and testing the LLVM adaptive compilation framework. The general idea of the compilation framework is described in project outline
Week 10 - 13
Benchmarking, tuning and experimenting with different recompilation algorithms. Typically benchmarking test cases would be
Test and organize code. Documentation
My main goal at the end of the summer is to have an automated profiling and adaptive compilation framework for the LLVM. Even though the performance improvements are still unclear at this point, I believe that this adaptive compilation framework will definitely give noticeable performance benefits, as the current JIT compilation is either too simple to give a reasonably fast code or too expensive to apply to all functions.
I have some experience with the Java Just-In-Time compiler and some experience with LLVM. I have included my CV for your reference. I don’t have a specific mentor in mind, but I imagine that the existing mentors from LLVM would be extremely helpful.
Creative, quality-focused Computer Engineering student brings a strong blend of programming, design and analysis skills. Offers solid understanding of best practices at each stage of the software development lifecycle. Skilled at recognizing and resolving design flaws that have the potential to create downstream maintenance, scalability and functionality issues. Adept at optimizing complex system processes and dataflows, taking the initiative to identify and recommend design and coding modifications to improve overall system performance. Excels in dynamic, deadline-sensitive environments that demand resourcefulness, astute judgement, and self-motivated quick study talents.Utilizes excellent time management skills to balance a demanding academic course of studies with employment and volunteer pursuits, achieving excellent results in all endeavours.
Compiler Construction • Compiler Optimization • Computer Architecture • Bottleneck Analysis & Solutions
Coding & Debugging • Workload Prioritization • Team Collaboration & Leadership
Software Testing & Integration • Test-Driven Development
BACHELOR OF COMPUTER ENGINEERING
University of Toronto, Toronto, ON, Expected Completion 2011
Compiler**·** Operation Systems · Computer Architecture
Cisco Certified Networking Associate, July 2009
Java VIRTUAL MACHINE JIT Developer Aug 2010-May 2011
IBM, Toronto*, Canada*
- Working on the PowerPC code generator of IBM Just-in-Time compiler for Java Virtual Machine.
- Benchmarking Just-in-Time compiler performance, analyzing and fixing possible regressions.
- Triaging and fixing defects in the Just-in-Time compiler
- Acquiring hand-on experience with powerpc assembly and powerpc binary debugging with gdb and other related tools
Java VirTual Mahine Developer , Extreme Blue May 2010-Aug 2010
IBM, Ottawa*, Canada*
- Architected a multi-tenancy solution for IBM J9 Java Virtual Machine for hosting multiple applications within one Java Virtual Machine. Designed solutions to provide good tenant isolation and resource control for all tenants running in the same Java Virtual Machine.
- Worked on Java class libraries and different components of J9 Java Virtual Machine, including threading library, garbage collector, interpreter, etc.
Xin Tong page 2
Graphics Compiler Developer May 2009-May 2010
Qualcomm,San Diego, USA
- Recruited for an internship position with this multinational telecommunications company to work on their C++ compiler project.
- Developed a static verifier program which automatically generates and addsintermediate language code to test programs to make them self-verifying. Then the test programs are used to test the C++ compiler, ensuring that it can compile code correctly.
- Utilizes in-depth knowledge of LLVM systems and algorithms to generate elegant and robust code.
COMPILER OPTIMIZER IMPLEMENTATION (Dec. 2010 – Apr 2011) : Implemented a compiler optimizer on the SUIF framework. Implemented control flow analysis, data flow analysis, loop invariant code motion, global value numbering, loop unrolling and various other local optimizations.
GPU COMPILER IMPLEMENTATION (Sept. – Dec. 2010) : Implemented a GPU compiler that compiles a subset of the GLSL language to ARB language which then can be executed on GPU. Wrote the scanner and parser using Lex and Yacc and a code generator in a OOP fashion
Malloc Library Implementation (Oct.-Nov. 2008) : Leveraged solid understanding of best fit algorithm and linkedlist data structure to design a malloc library to perform dynamic memory allocation. Implemented the library with C programming language to ensure robust and clear coding for 1000 line codes. Optimized library on the code level to obtain a 6% increase of allocation throughput. Harnessed knowledge of trace files and drivers to test and evaluate the malloc library’s throughput and memory utilization.
C **·**C++ **·**Java
GDB · GCC
Elected Officer**,** Institute of Electrical & Electronics Engineers, University of Toronto Branch, Since May 2009
Member**,** Institute of Electrical & Electronics Engineers, Since 2007
Member**,** University of Toronto E-Sports Club**, 2007**
Member**,** University of Toronto Engineering Chinese Culture Club**, 2007**
Member**,** University of Toronto Robotics Club**, 2007**