Outperforming state-of-the-art compilers in Unison
Cutting edge technology
Unison, rethinks code generation using combinatorial optimization techniques. Unison is available on Github and is integrated with the regular LLVM toolchain.
Code generation in a compiler creates the assembly code to be executed on a specific processor. It is crucial for efficiency and state-of-the-art compilers such as GCC and LLVM to devote many person-years of development and maintenance to it. These compilers decompose code generation into multiple tasks (instruction selection, instruction scheduling, and register allocation) and solve each task in isolation with heuristic algorithms. While this approach is modular and speeds up compilation, code quality is sacrificed by it as the essential combinatorial inter dependencies between tasks are ignored.
Unison pursues a radically different route: it embraces and exploits the combinatorial, interdependent nature of code generation to drastically improve code quality. In Unison, the inter dependent code generation tasks are translated into a single combinatorial model that accurately reflects all inter dependencies. Solving the model with constraint programming, a modern combinatorial optimization technology, results in the desired high-quality assembly code. See Figure 1 for an example visualization of the Unison solver.
Benefits
Unison complements state-of-the-art compilers in that it can deliver optimal assembly code at the expense of higher compilation times. This ability makes Unison a powerful tool for both compiler users and developers. As a user you can trade compilation time for code quality beyond the usual -O{0,1,2,3,..} optimization levels. As a compiler developer you can identify improvement opportunities in the existing heuristic algorithms.
The project targets a wide array of hardware architectures, ranging from out-of-order, general-purpose to VLIW digital signal processors (DSPs). Recent experiments for Hexagon, a DSP ubiquitous in modern mobile platforms, show that Unison consistently generates more efficient code than LLVM, sometimes by almost 50%. Figure 2 shows the speedup of Unison over LLVM 3.8 for hundred functions from MediaBench and SPEC CPU 2006 applications (each bar corresponds to a function):
Shape the future with us
Compiler development is one of the greatest programming challenges there is. Join us shaping the future of this technology. Participation in the project and spreading the message is greatly welcome and encouraged.
Currently, Unison targets the Hexagon, ARM, and MIPS architectures. Ongoing work includes improving robustness and reducing compilation time by applying advanced constraint solving techniques, as well as introducing support for new architectures. Below is a video showing how Unison can improve the speed of the code generated by LLVM for Hexagon.
Unison is a joint research project involving researchers from RISE SICS and KTH Royal Institute of Technology in Stockholm, as well as engineers from Ericsson. Today Unison is a great bench mark and complement to Ericsson’s conventional compiler development and has potential to target many more use cases in the future.
Stay tuned, or even better, get your hands dirty!!
More information
- Visit the Project page
- Access Unison's Source code
Videos:
Further reading:
- Visit Unison's publications
