Global Instruction Selection

Warning

This document is a work in progress. It reflects the current state of the implementation, as well as open design and implementation issues.

Introduction

GlobalISel is a framework that provides a set of reusable passes and utilities for instruction selection — translation from LLVM IR to target-specific Machine IR (MIR).

GlobalISel is intended to be a replacement for SelectionDAG and FastISel, to solve three major problems:

• Performance — SelectionDAG introduces a dedicated intermediate representation, which has a compile-time cost.

  GlobalISel directly operates on the post-isel representation used by the rest of the code generator, MIR. It does require extensions to that representation to support arbitrary incoming IR: Generic Machine IR.

• Granularity — SelectionDAG and FastISel operate on individual basic blocks, losing some global optimization opportunities.

  GlobalISel operates on the whole function.

• Modularity — SelectionDAG and FastISel are radically different and share very little code.

  GlobalISel is built in a way that enables code reuse. For instance, both the optimized and fast selectors share the Core Pipeline, and targets can configure that pipeline to better suit their needs.

Design and Implementation Reference

More information on the design and implementation of GlobalISel can be found in the following sections.

• Generic Machine IR
• Generic Opcodes
• Core Pipeline
• Porting GlobalISel to A New Target
• Tutorials
• Resources

More information on specific passes can be found in the following sections:

• IRTranslator
• Legalizer
• RegBankSelect
• InstructionSelect
• Known Bits Analysis

Progress and Future Work

The initial goal is to replace FastISel on AArch64. The next step will be to replace SelectionDAG as the optimized ISel.

NOTE: While we iterate on GlobalISel, we strive to avoid affecting the performance of SelectionDAG, FastISel, or the other MIR passes. For instance, the types of Generic Virtual Registers are stored in a separate table in MachineRegisterInfo, that is destroyed after InstructionSelect.

FastISel Replacement

For the initial FastISel replacement, we intend to fallback to SelectionDAG on selection failures.

Currently, compile-time of the fast pipeline is within 1.5x of FastISel. We’re optimistic we can get to within 1.1/1.2x, but beating FastISel will be challenging given the multi-pass approach. Still, supporting all IR (via a complete legalizer) and avoiding the fallback to SelectionDAG in the worst case should enable better amortized performance than SelectionDAG+FastISel.

NOTE: We considered never having a fallback to SelectionDAG, instead deciding early whether a given function is supported by GlobalISel or not. The decision would be based on Legalizer queries. We abandoned that for two reasons: a) on IR inputs, we’d need to basically simulate the IRTranslator; b) to be robust against unforeseen failures and to enable iterative improvements.