Optimizing LLVM Back-End: Global Instruction Selection

The LLVM compiler framework, popular for its versatility and optimization capabilities, constantly evolves to meet the demands of modern software development. One of the important phases in LLVM's backend is, instruction selection, which has seen significant advancements over the years.

This article explains Global Instruction Selection in LLVM, what problems it solves, and how it helps make compiling faster.

Introduction:

Instruction selection is a critical phase in the LLVM compiler's backend, responsible for translating LLVM-IR into lower-level Machine IR (MIR) suitable for the target architecture. Traditionally, LLVM implemented SelectionDAG and FastISel for this task, each with its strengths and limitations. However, conventional instruction selection techniques often operate within narrow scopes, focusing on individual statements or basic blocks that only achieve local code optimization. In contrast, global instruction selection, implemented in LLVM, takes a broader approach by optimizing entire functions in the form of Static Single Assignment (SSA) representation.

Instruction Selection Challenges: The traditional instruction selection methods in LLVM, namely SelectionDAG and FastISel, exhibit effectiveness alongside face performance bottlenecks and optimization constraints. Unfortunately, SelectionDAG, renowned for its power, consumes a significant portion of compilation time due to the complexity of legalizing operations and combining DAG nodes.

Conversely, FastISel prioritizes speed over optimization ability, limiting support to common data types that fit within a single machine register. FastISel does not handle 128-bit integers or structures and supports only a subset of frequently used LLVM-IR operations and intrinsics. When an unsupported LLVM-IR instruction is encountered, FastISel resorts to SelectionDAG for the remaining block. However, for function calls involving unsupported data types, parameters passed on the stack, or unimplemented intrinsics, only the impacted call instruction is processed by SelectionDAG

LLVM's Global Instruction Selection

The global instruction selection framework within LLVM offers a powerful set of tools and optimization modules to improve code generation efficiency. This framework directly translates LLVM-IR into machine instructions suitable for the target platform, bypassing the need for intermediate representations like the DAG used in SelectionDAGISel.

The primary objectives of global instruction selection are to overcome the limitations of DAG-based and fast instruction selection methods while addressing three main issues:

1. Compilation Performance: Traditional methods like SelectionDAGISel introduce additional overhead by using a new DAG intermediate representation, leading to slower compilation times. GlobalISel streamlines this process by directly generating target machine instructions from LLVM-IR operations, thus improving compilation speed.
2. Granularity Optimization: Unlike other methods that may miss out on optimization opportunities within basic blocks, GlobalISel operates on entire functions, retaining complete LLVM-IR information. This holistic approach allows for more thorough exploration of optimization possibilities across the entire codebase.
3. Modularity Enhancement: Existing methods like SelectionDAGISel and FastISel are standalone modules with limited code reuse and modularity. In contrast, GlobalISel is designed for code reuse, leveraging LLVM's compilation pipeline. It allows for better customization to meet the needs of different target platforms, fostering collaboration and flexibility.

The architecture of global instruction selection consists of four key modules:

• IRTranslator: This module converts LLVM-IR into Generic Machine IR (GMIR), a machine-independent representation.
• Legalizer: Responsible for ensuring compatibility with the target platform, the Legalizer converts operand types and operations to match the supported instructions.
• RegisterBankSelector: Allocates register banks for operands, optimizing register usage.
• InstructionSelector: Converts mixed machine instructions into target-specific machine instructions, completing the code generation process.

Despite these advancements, the quality of generated code using the basic instruction selection framework may still be suboptimal. To address this, global instruction selection offers a flexible combination of instructions that can be configured for specific target platforms, ensuring optional and cust omizable optimization.

Overall, the global instruction selection framework within LLVM represents a significant leap forward in code generation efficiency and optimization, promising better performance and adaptability for diverse target platforms.

Conclusion

The introduction of global-based instruction selection marks a significant leap forward in the LLVM compiler's capabilities. This method addresses key limitations seen in previous selection techniques. By directly supporting a wider range of data types and operations, it eliminates the constraints of fast instruction selection. Additionally, it effectively tackles the loss of global optimization opportunities that DAG-based selection methods often face, while also reducing the time it takes to compile.

Implemented on the Shenwei platform, the optimization brought about by LLVM's global instruction selection noticeably improves the efficiency of code generation processes. Though there's a slight increase in compilation time, the overall compilation cycle becomes more effective. With code quality being the same, there's a notable 8% boost in the quality of generated code.

However, it's important to note that the code quality still falls short compared to DAG-based selection methods. To address this, further exploration into how DAG-based instruction merging compares with global instruction selection is needed. By examining more examples of instruction merging, we hope to refine the compiler's performance and narrow the gap between these two methods.

In sum, global instruction selection within LLVM represents a significant step forward in optimizing code generation. While there's room for improvement, its potential to enhance both code quality and performance is clear. With ongoing research and tweaks, global instruction selection promises further advancements in compiler technology, making software development more efficient and accessible.

References:

• LLVM Project, “LLVM 17 documentation: Global instruction selection,”
• Research Paper Link