107 lines · plain
1============================2Global Instruction Selection3============================4 5.. warning::6 This document is a work in progress. It reflects the current state of the7 implementation, as well as open design and implementation issues.8 9.. contents::10 :local:11 :depth: 112 13Introduction14============15 16GlobalISel is a framework that provides a set of reusable passes and utilities17for instruction selection --- translation from LLVM IR to target-specific18Machine IR (MIR).19 20GlobalISel is intended to be a replacement for SelectionDAG and FastISel, to21solve three major problems:22 23* **Performance** --- SelectionDAG introduces a dedicated intermediate24 representation, which has a compile-time cost.25 26 GlobalISel directly operates on the post-isel representation used by the27 rest of the code generator, MIR.28 It does require extensions to that representation to support arbitrary29 incoming IR: :ref:`gmir`.30 31* **Granularity** --- SelectionDAG and FastISel operate on individual basic32 blocks, losing some global optimization opportunities.33 34 GlobalISel operates on the whole function.35 36* **Modularity** --- SelectionDAG and FastISel are radically different and share37 very little code.38 39 GlobalISel is built in a way that enables code reuse. For instance, both the40 optimized and fast selectors share the :ref:`pipeline`, and targets can41 configure that pipeline to better suit their needs.42 43Design and Implementation Reference44===================================45 46More information on the design and implementation of GlobalISel can be found in47the following sections.48 49.. toctree::50 :maxdepth: 151 52 GMIR53 GenericOpcode54 MIRPatterns55 Pipeline56 Porting57 Resources58 59More information on specific passes can be found in the following sections:60 61.. toctree::62 :maxdepth: 163 64 IRTranslator65 Legalizer66 RegBankSelect67 InstructionSelect68 KnownBits69 70.. _progress:71 72Progress and Future Work73========================74 75The initial goal is to replace FastISel on AArch64. The next step will be to76replace SelectionDAG as the optimized ISel.77 78``NOTE``:79While we iterate on GlobalISel, we strive to avoid affecting the performance of80SelectionDAG, FastISel, or the other MIR passes. For instance, the types of81:ref:`gmir-gvregs` are stored in a separate table in ``MachineRegisterInfo``,82that is destroyed after :ref:`instructionselect`.83 84.. _progress-fastisel:85 86FastISel Replacement87--------------------88 89For the initial FastISel replacement, we intend to fallback to SelectionDAG on90selection failures.91 92Currently, compile-time of the fast pipeline is within 1.5x of FastISel.93We're optimistic we can get to within 1.1/1.2x, but beating FastISel will be94challenging given the multi-pass approach.95Still, supporting all IR (via a complete legalizer) and avoiding the fallback96to SelectionDAG in the worst case should enable better amortized performance97than SelectionDAG+FastISel.98 99``NOTE``:100We considered never having a fallback to SelectionDAG, instead deciding early101whether a given function is supported by GlobalISel or not. The decision would102be based on :ref:`milegalizer` queries.103We abandoned that for two reasons:104a) on IR inputs, we'd need to basically simulate the :ref:`irtranslator`;105b) to be robust against unforeseen failures and to enable iterative106improvements.107