============================
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.

.. contents::
   :local:
   :depth: 1

.. toctree::
   :hidden:

   GMIR
   GenericOpcode
   MIRPatterns
   Pipeline
   Porting
   Resources
   IRTranslator
   Legalizer
   RegBankSelect
   InstructionSelect
   KnownBits

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: :ref:`gmir`.

* **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 :ref:`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.

* :doc:`GMIR`
* :doc:`GenericOpcode`
* :doc:`MIRPatterns`
* :doc:`Pipeline`
* :doc:`Porting`
* :doc:`Resources`

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

* :doc:`IRTranslator`
* :doc:`Legalizer`
* :doc:`RegBankSelect`
* :doc:`InstructionSelect`
* :doc:`KnownBits`

.. _progress:

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
:ref:`gmir-gvregs` are stored in a separate table in ``MachineRegisterInfo``,
that is destroyed after :ref:`instructionselect`.

.. _progress-fastisel:

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 :ref:`milegalizer` queries.
We abandoned that for two reasons:
a) on IR inputs, we'd need to basically simulate the :ref:`irtranslator`;
b) to be robust against unforeseen failures and to enable iterative
improvements.
