Outperforming state-of-the-art compilers in Unison | Ericsson Research Blog

Ericsson Research Blog

Research, insights and technology reflections

Outperforming state-of-the-art compilers in Unison

Do you want to improve the quality of your code? Unison is a new compiler with a radically new approach. It’s available open source and we’d love for you to get involved.

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.

Figure 1. The graph is a snapshot of the Unison solver visualizing the combinations of Hexagon assembly code instructions the solver considers generating for the factorial function.

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):

Figure 2. Each color corresponds to a different application in Mediabench or SPEC CPU 2006 and each bar corresponds to a function within that application.

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

Videos:

Further reading:

Fredrik Wickberg

Fredrik is working with product development within business area networks as Line Manager and responsible of kernel, programming model, build systems and compiler development for the baseband platform. Prior to his current undertakings he has eight years of experience in ASIC development in a range of positions. Fredrik holds a master of science degree in computer science majoring in system on chip (SOC).

Fredrik Wickberg

Mattias Eriksson

Mattias is a compiler developer at Ericsson. He is currently working on modernizing an in-house compiler used in the baseband application. He holds a PhD degree in computer science from Linköping University (2011).

Mattias Eriksson