Global Instruction Selection

Warning

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

Introduction

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

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

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

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

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

GlobalISel operates on the whole function.

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

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

Design and Implementation Reference

More information on the design and implementation of GlobalISel can be found inthe 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 toreplace SelectionDAG as the optimized ISel.

NOTE:While we iterate on GlobalISel, we strive to avoid affecting the performance ofSelectionDAG, FastISel, or the other MIR passes. For instance, the types ofGeneric 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 onselection 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 bechallenging given the multi-pass approach.Still, supporting all IR (via a complete legalizer) and avoiding the fallbackto SelectionDAG in the worst case should enable better amortized performancethan SelectionDAG+FastISel.

NOTE:We considered never having a fallback to SelectionDAG, instead deciding earlywhether a given function is supported by GlobalISel or not. The decision wouldbe 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 iterativeimprovements.