1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| ============================
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
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.
.. toctree::
:maxdepth: 1
GMIR
Pipeline
Porting
Resources
.. _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.
|