The Program Repository (or Program Repo) is a research project studying the benefits of changing the build workflow to store object data in a database instead of object files. It aims to eliminate duplicated work from the compilation process, enable incremental compilation, and to minimize the work that must be performed by the linker. Here we present build times for self hosting LLVM with standard ELF object files and with a Program Repo. The Program Repo integrates into the compiler to improve middle- and back-end optimization time and should be complementary to C++ modules. The implementation in LLVM is illustrated in Figure 1. It consists of a couple of additional passes in the middle-end and a new ObjectWriter in the back-end.
Figure 1 - Implementation in LLVM
Method
To show the advantage of the Program Repository, I am going to compare the build times of the open source LLVM codebase using a Program Repository against the traditional method. The process for building LLVM with the Repo compiler is documented here.
This comparison was run with the following:
- Operating System: Ubuntu 18.04
- Processor: Intel Xeon E5-2683 v3
- Build Configuration: Release
- Git revision: 9f98c8694255
- Extra CMake flags: -DCMAKE_CXX_FLAGS=-ftime-trace
At the time of writing this blog, we do not yet have a Program Repo-aware linker. We use an intermediary program (repo2obj) to generate ELF object files from the Program Repo for linking. As such, this only measures the compile time benefits of the Program Repo.
We compared three full builds (ninja all):
- ELF as a baseline
- First run with Program Repo. This records objects into the repository and measures the overhead for a cold build.
- Second run with Program Repo after ninja clean. This builds using objects stored in the repository.
Results
Figure 2 shows the overall time taken to compile LLVM+Clang. This was measured by adding the -ftime-trace option for all files and summing their “ExecuteCompiler” time. Building with the Program Repo adds a small overhead (3%) for hashing objects and storing them to the database. Building with all objects in the Program Repo decreases time for a build with the Program Repo by 17%. Overall, 68% of the build time of LLVM+Clang is in front-end so the Program Repo is currently eliminating over half of the back-end time.
Figure 2 - Time to compile LLVM+Clang (all jobs)
Example
As an example of how this works, and the benefit, Figure 3 shows -ftime-trace output compiling X86ISelLowering.cpp for ELF file format (one of the longest files to compile in LLVM) and Figure 4 shows the equivalent trace using the Program Repo. The program repo compiler hashes each object in the pass “RepoMetadataGeneration” (marked 1 in Figure 4). A following pass “RepoPruning” prunes objects by marking them as “available externally” linkage type if they have already been compiled by the Program Repo. A later pass, “Eliminate Available Externally Globals” (marked 2 in Figure 4), removes functions which have been pruned earlier. Most of the remaining back-end time is spent in “CallGraph Pass Manager” (marked 3 in Figure 4) which is earlier in the optimization pipeline than “Eliminate Available Externally Globals”. This is a target for further performance improvement.
Figure 3 -ftime-trace for Building X86ISelLowering.cpp ELF format
Figure 4 -ftime-trace for Building X86ISelLowering.cpp ELF format with Program Repo (2nd run)
Conclusion and Future work
These are very early performance results which demonstrate the Program Repo building a working LLVM compiler with reduced compile times. Using the Program Repo reduces compiler back-end time by about half for a previously seen build. We believe that this could be improved further. In addition to improving compile time, the Program Repo is designed to move work from the linker to the compiler wherever possible, so it can be done in parallel or distributed. For example, string de-duplication can represent as much as 30% of a traditional linker’s execution time. With the Program Repo, this is done at compile-time, so we anticipate a Program Repo linker to be significantly faster than one consuming traditional object files
