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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Global Instruction Selection — LLVM 13 documentation</title>
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../_static/llvm-theme.css" type="text/css" />
<script id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
<script src="../_static/jquery.js"></script>
<script src="../_static/underscore.js"></script>
<script src="../_static/doctools.js"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="Generic Machine IR" href="GMIR.html" />
<link rel="prev" title="The Often Misunderstood GEP Instruction" href="../GetElementPtr.html" />
<style type="text/css">
table.right { float: right; margin-left: 20px; }
table.right td { border: 1px solid #ccc; }
</style>
</head><body>
<div class="logo">
<a href="../index.html">
<img src="../_static/logo.png"
alt="LLVM Logo" width="250" height="88"/></a>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="GMIR.html" title="Generic Machine IR"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="../GetElementPtr.html" title="The Often Misunderstood GEP Instruction"
accesskey="P">previous</a> |</li>
<li><a href="https://llvm.org/">LLVM Home</a> | </li>
<li><a href="../index.html">Documentation</a>»</li>
<li class="nav-item nav-item-1"><a href="../Reference.html" accesskey="U">Reference</a> »</li>
<li class="nav-item nav-item-this"><a href="">Global Instruction Selection</a></li>
</ul>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3>Documentation</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/GettingStartedTutorials.html">Getting Started/Tutorials</a></li>
<li><a href="https://llvm.org/docs/UserGuides.html">User Guides</a></li>
<li><a href="https://llvm.org/docs/Reference.html">Reference</a></li>
</ul>
<h3>Getting Involved</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/Contributing.html">Contributing to LLVM</a></li>
<li><a href="https://llvm.org/docs/HowToSubmitABug.html">Submitting Bug Reports</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#mailing-lists">Mailing Lists</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#irc">IRC</a></li>
<li><a href="https://llvm.org/docs/GettingInvolved.html#meetups-and-social-events">Meetups and Social Events</a></li>
</ul>
<h3>Additional Links</h3>
<ul class="want-points">
<li><a href="https://llvm.org/docs/FAQ.html">FAQ</a></li>
<li><a href="https://llvm.org/docs/Lexicon.html">Glossary</a></li>
<li><a href="https://llvm.org/pubs">Publications</a></li>
<li><a href="https://github.com/llvm/llvm-project//">Github Repository</a></li>
</ul>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/GlobalISel/index.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="../search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" />
<input type="submit" value="Go" />
</form>
</div>
</div>
<script>$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="section" id="global-instruction-selection">
<h1>Global Instruction Selection<a class="headerlink" href="#global-instruction-selection" title="Permalink to this headline">¶</a></h1>
<div class="admonition warning">
<p class="admonition-title">Warning</p>
<p>This document is a work in progress. It reflects the current state of the
implementation, as well as open design and implementation issues.</p>
</div>
<div class="contents local topic" id="contents">
<ul class="simple">
<li><p><a class="reference internal" href="#introduction" id="id1">Introduction</a></p></li>
<li><p><a class="reference internal" href="#design-and-implementation-reference" id="id2">Design and Implementation Reference</a></p></li>
<li><p><a class="reference internal" href="#progress-and-future-work" id="id3">Progress and Future Work</a></p></li>
</ul>
</div>
<div class="section" id="introduction">
<h2><a class="toc-backref" href="#id1">Introduction</a><a class="headerlink" href="#introduction" title="Permalink to this headline">¶</a></h2>
<p>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).</p>
<p>GlobalISel is intended to be a replacement for SelectionDAG and FastISel, to
solve three major problems:</p>
<ul>
<li><p><strong>Performance</strong> — SelectionDAG introduces a dedicated intermediate
representation, which has a compile-time cost.</p>
<p>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: <a class="reference internal" href="GMIR.html#gmir"><span class="std std-ref">Generic Machine IR</span></a>.</p>
</li>
<li><p><strong>Granularity</strong> — SelectionDAG and FastISel operate on individual basic
blocks, losing some global optimization opportunities.</p>
<p>GlobalISel operates on the whole function.</p>
</li>
<li><p><strong>Modularity</strong> — SelectionDAG and FastISel are radically different and share
very little code.</p>
<p>GlobalISel is built in a way that enables code reuse. For instance, both the
optimized and fast selectors share the <a class="reference internal" href="Pipeline.html#pipeline"><span class="std std-ref">Core Pipeline</span></a>, and targets can
configure that pipeline to better suit their needs.</p>
</li>
</ul>
</div>
<div class="section" id="design-and-implementation-reference">
<h2><a class="toc-backref" href="#id2">Design and Implementation Reference</a><a class="headerlink" href="#design-and-implementation-reference" title="Permalink to this headline">¶</a></h2>
<p>More information on the design and implementation of GlobalISel can be found in
the following sections.</p>
<div class="toctree-wrapper compound">
<ul>
<li class="toctree-l1"><a class="reference internal" href="GMIR.html">Generic Machine IR</a></li>
<li class="toctree-l1"><a class="reference internal" href="GenericOpcode.html">Generic Opcodes</a></li>
<li class="toctree-l1"><a class="reference internal" href="Pipeline.html">Core Pipeline</a></li>
<li class="toctree-l1"><a class="reference internal" href="Porting.html">Porting GlobalISel to A New Target</a></li>
<li class="toctree-l1"><a class="reference internal" href="Porting.html#tutorials">Tutorials</a></li>
<li class="toctree-l1"><a class="reference internal" href="Resources.html">Resources</a></li>
</ul>
</div>
<p>More information on specific passes can be found in the following sections:</p>
<div class="toctree-wrapper compound">
<ul>
<li class="toctree-l1"><a class="reference internal" href="IRTranslator.html">IRTranslator</a></li>
<li class="toctree-l1"><a class="reference internal" href="Legalizer.html">Legalizer</a></li>
<li class="toctree-l1"><a class="reference internal" href="RegBankSelect.html">RegBankSelect</a></li>
<li class="toctree-l1"><a class="reference internal" href="InstructionSelect.html">InstructionSelect</a></li>
<li class="toctree-l1"><a class="reference internal" href="KnownBits.html">Known Bits Analysis</a></li>
</ul>
</div>
</div>
<div class="section" id="progress-and-future-work">
<span id="progress"></span><h2><a class="toc-backref" href="#id3">Progress and Future Work</a><a class="headerlink" href="#progress-and-future-work" title="Permalink to this headline">¶</a></h2>
<p>The initial goal is to replace FastISel on AArch64. The next step will be to
replace SelectionDAG as the optimized ISel.</p>
<p><code class="docutils literal notranslate"><span class="pre">NOTE</span></code>:
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
<a class="reference internal" href="GMIR.html#gmir-gvregs"><span class="std std-ref">Generic Virtual Registers</span></a> are stored in a separate table in <code class="docutils literal notranslate"><span class="pre">MachineRegisterInfo</span></code>,
that is destroyed after <a class="reference internal" href="InstructionSelect.html#instructionselect"><span class="std std-ref">InstructionSelect</span></a>.</p>
<div class="section" id="fastisel-replacement">
<span id="progress-fastisel"></span><h3>FastISel Replacement<a class="headerlink" href="#fastisel-replacement" title="Permalink to this headline">¶</a></h3>
<p>For the initial FastISel replacement, we intend to fallback to SelectionDAG on
selection failures.</p>
<p>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.</p>
<p><code class="docutils literal notranslate"><span class="pre">NOTE</span></code>:
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 <a class="reference internal" href="Legalizer.html#milegalizer"><span class="std std-ref">Legalizer</span></a> queries.
We abandoned that for two reasons:
a) on IR inputs, we’d need to basically simulate the <a class="reference internal" href="IRTranslator.html#irtranslator"><span class="std std-ref">IRTranslator</span></a>;
b) to be robust against unforeseen failures and to enable iterative
improvements.</p>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="GMIR.html" title="Generic Machine IR"
>next</a> |</li>
<li class="right" >
<a href="../GetElementPtr.html" title="The Often Misunderstood GEP Instruction"
>previous</a> |</li>
<li><a href="https://llvm.org/">LLVM Home</a> | </li>
<li><a href="../index.html">Documentation</a>»</li>
<li class="nav-item nav-item-1"><a href="../Reference.html" >Reference</a> »</li>
<li class="nav-item nav-item-this"><a href="">Global Instruction Selection</a></li>
</ul>
</div>
<div class="footer" role="contentinfo">
© Copyright 2003-2021, LLVM Project.
Last updated on 2021-09-18.
Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 3.5.4.
</div>
</body>
</html>
|
