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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
|
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Core Pipeline — 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="IRTranslator" href="IRTranslator.html" />
<link rel="prev" title="Generic Opcodes" href="GenericOpcode.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="IRTranslator.html" title="IRTranslator"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="GenericOpcode.html" title="Generic Opcodes"
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" >Reference</a> »</li>
<li class="nav-item nav-item-2"><a href="index.html" accesskey="U">Global Instruction Selection</a> »</li>
<li class="nav-item nav-item-this"><a href="">Core Pipeline</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/Pipeline.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="core-pipeline">
<span id="pipeline"></span><h1>Core Pipeline<a class="headerlink" href="#core-pipeline" title="Permalink to this headline">¶</a></h1>
<div class="toctree-wrapper compound">
</div>
<p>The core pipeline of GlobalISel is:</p>
<img alt="../_images/pipeline-overview.png" src="../_images/pipeline-overview.png" />
<p>The four passes shown in the diagram consist of:</p>
<p><a class="reference internal" href="IRTranslator.html"><span class="doc">IRTranslator</span></a></p>
<blockquote>
<div><p>Converts <a class="reference internal" href="../LangRef.html"><span class="doc">LLVM-IR</span></a> into <a class="reference internal" href="GMIR.html"><span class="doc">gMIR (Generic MIR)</span></a>.
This is largely a direct translation and has little target customization.
It’s somewhat analogous to SelectionDAGBuilder but builds a flavour of MIR
called gMIR instead of a specialized representation. gMIR uses exactly the
same data structures as MIR but has more relaxed constraints. For example,
a virtual register may be constrained to a particular type without also
constraining it to a specific register class.</p>
</div></blockquote>
<p><a class="reference internal" href="Legalizer.html"><span class="doc">Legalizer</span></a></p>
<blockquote>
<div><p>Replaces unsupported operations with supported ones. In other words, it shapes
the gMIR to suit what the backend can support. There is a very small set of
operations which targets are required to support but aside from that targets
can shape the MIR as they wish.</p>
</div></blockquote>
<p><a class="reference internal" href="RegBankSelect.html"><span class="doc">Register Bank Selector</span></a></p>
<blockquote>
<div><p>Binds virtual registers to register banks. This pass is intended to minimize
cross-register-bank copies by clustering portions of the MIR together.</p>
</div></blockquote>
<p><a class="reference internal" href="InstructionSelect.html"><span class="doc">Instruction Select</span></a></p>
<blockquote>
<div><p>Select target instructions using the gMIR. At this point, the gMIR has been
constrained enough that it becomes MIR.</p>
</div></blockquote>
<p>Although we tend to talk about them as distinct passes, it should be noted that
there’s a good deal of flexibility here and it’s ok for things to happen
earlier than described below. For example, it’s not unusual for the legalizer to
legalize an intrinsic directly to a target instruction. The concrete
requirement is that the following additional constraints are preserved after
each of these passes:</p>
<p>IRTranslator</p>
<blockquote>
<div><p>The representation must be gMIR, MIR, or a mixture of the two after this pass.
The majority will typically be gMIR to begin with but later passes will
gradually transition the gMIR to MIR.</p>
</div></blockquote>
<p>Legalizer</p>
<blockquote>
<div><p>No illegal operations must remain or be introduced after this pass.</p>
</div></blockquote>
<p>Register Bank Selector</p>
<blockquote>
<div><p>All virtual registers must have a register bank assigned after this pass.</p>
</div></blockquote>
<p>Instruction Select</p>
<blockquote>
<div><p>No gMIR must remain or be introduced after this pass. In other words, we must
have completed the conversion from gMIR to MIR.</p>
</div></blockquote>
<p>In addition to these passes, there are also some optional passes that perform
an optimization. The current optional passes are:</p>
<p>Combiner</p>
<blockquote>
<div><p>Replaces patterns of instructions with a better alternative. Typically, this
means improving run time performance by replacing instructions with faster
alternatives but Combiners can also focus on code size or other metrics.</p>
</div></blockquote>
<p>Additional passes such as these can be inserted to support higher optimization
levels or target specific needs. A likely pipeline is:</p>
<img alt="../_images/pipeline-overview-with-combiners.png" src="../_images/pipeline-overview-with-combiners.png" />
<p>Of course, combiners can be inserted in other places too. Also passes can be
replaced entirely so long as their task is complete as shown in this (more
customized) example pipeline.</p>
<img alt="../_images/pipeline-overview-customized.png" src="../_images/pipeline-overview-customized.png" />
<div class="section" id="machineverifier">
<span id="maintainability-verifier"></span><h2>MachineVerifier<a class="headerlink" href="#machineverifier" title="Permalink to this headline">¶</a></h2>
<p>The pass approach lets us use the <code class="docutils literal notranslate"><span class="pre">MachineVerifier</span></code> to enforce invariants
that are required beyond certain points of the pipeline. For example, a
function with the <code class="docutils literal notranslate"><span class="pre">legalized</span></code> property can have the <code class="docutils literal notranslate"><span class="pre">MachineVerifier</span></code>
enforce that no illegal instructions occur. Similarly, a
<code class="docutils literal notranslate"><span class="pre">regBankSelected</span></code> function may not have virtual registers without a register
bank assigned.</p>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>For layering reasons, <code class="docutils literal notranslate"><span class="pre">MachineVerifier</span></code> isn’t able to be the sole verifier
in GlobalISel. Currently some of the passes also perform verification while
we find a way to solve this problem.</p>
<p>The main issue is that GlobalISel is a separate library, so we can’t
directly reference it from CodeGen.</p>
</div>
</div>
<div class="section" id="testing">
<h2>Testing<a class="headerlink" href="#testing" title="Permalink to this headline">¶</a></h2>
<p>The ability to test GlobalISel is significantly improved over SelectionDAG.
SelectionDAG is something of a black box and there’s a lot going on inside it.
This makes it difficult to write a test that reliably tests a particular aspect
of its behaviour. For comparison, see the following diagram:</p>
<img alt="../_images/testing-pass-level.png" src="../_images/testing-pass-level.png" />
<p>Each of the grey boxes indicates an opportunity to serialize the current state
and test the behaviour between two points in the pipeline. The current state
can be serialized using <code class="docutils literal notranslate"><span class="pre">-stop-before</span></code> or <code class="docutils literal notranslate"><span class="pre">-stop-after</span></code> and loaded using
<code class="docutils literal notranslate"><span class="pre">-start-before</span></code>, <code class="docutils literal notranslate"><span class="pre">-start-after</span></code>, and <code class="docutils literal notranslate"><span class="pre">-run-pass</span></code>.</p>
<p>We can also go further still, as many of GlobalISel’s passes are readily unit
testable:</p>
<img alt="../_images/testing-unit-level.png" src="../_images/testing-unit-level.png" />
<p>It’s possible to create an imaginary target such as in <a class="reference external" href="https://github.com/llvm/llvm-project/blob/93b29d3882baf7df42e4e9bc26b977b00373ef56/llvm/unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp#L28-L57">LegalizerHelperTest.cpp</a>
and perform a single step of the algorithm and check the result. The MIR and
FileCheck directives can be embedded using strings so you still have access to
the convenience available in llvm-lit.</p>
</div>
<div class="section" id="debugging">
<h2>Debugging<a class="headerlink" href="#debugging" title="Permalink to this headline">¶</a></h2>
<p>One debugging technique that’s proven particularly valuable is to use the
BlockExtractor to extract basic blocks into new functions. This can be used
to track down correctness bugs and can also be used to track down performance
regressions. It can also be coupled with function attributes to disable
GlobalISel for one or more of the extracted functions.</p>
<img alt="../_images/block-extract.png" src="../_images/block-extract.png" />
<p>The command to do the extraction is:</p>
<div class="highlight-shell notranslate"><div class="highlight"><pre><span></span>./bin/llvm-extract -o - -S -b ‘foo:bb1<span class="p">;</span>bb4’ <input> > extracted.ll
</pre></div>
</div>
<p>This particular example extracts two basic blocks from a function named <code class="docutils literal notranslate"><span class="pre">foo</span></code>.
The new LLVM-IR can then be modified to add the <code class="docutils literal notranslate"><span class="pre">failedISel</span></code> attribute to the
extracted function containing bb4 to make that function use SelectionDAG.</p>
<p>This can prevent some optimizations as GlobalISel is generally able to work on a
single function at a time. This technique can be repeated for different
combinations of basic blocks until you have identified the critical blocks
involved in a bug.</p>
<p>Once the critical blocks have been identified, you can further increase the
resolution to the critical instructions by splitting the blocks like from:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>bb1:
... instructions group 1 ...
... instructions group 2 ...
</pre></div>
</div>
<p>into:</p>
<div class="highlight-none notranslate"><div class="highlight"><pre><span></span>bb1:
... instructions group 1 ...
br %bb2
bb2:
... instructions group 2 ...
</pre></div>
</div>
<p>and then repeating the process for the new blocks.</p>
<p>It’s also possible to use this technique in a mode where the main function
is compiled with GlobalISel and the extracted basic blocks are compiled with
SelectionDAG (or the other way around) to leverage the existing quality of
another code generator to track down bugs. This technique can also be used to
improve the similarity between fast and slow code when tracking down performance
regressions and help you zero in on a particular cause of the regression.</p>
</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="IRTranslator.html" title="IRTranslator"
>next</a> |</li>
<li class="right" >
<a href="GenericOpcode.html" title="Generic Opcodes"
>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-2"><a href="index.html" >Global Instruction Selection</a> »</li>
<li class="nav-item nav-item-this"><a href="">Core Pipeline</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>
|
