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
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
|
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Generic Machine IR — 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 Opcodes" href="GenericOpcode.html" />
<link rel="prev" title="Global Instruction Selection" href="index.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="GenericOpcode.html" title="Generic Opcodes"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="index.html" title="Global Instruction Selection"
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="">Generic Machine IR</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/GMIR.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="generic-machine-ir">
<span id="gmir"></span><h1>Generic Machine IR<a class="headerlink" href="#generic-machine-ir" title="Permalink to this headline">¶</a></h1>
<div class="contents local topic" id="contents">
<ul class="simple">
<li><p><a class="reference internal" href="#generic-machine-instructions" id="id3">Generic Machine Instructions</a></p></li>
<li><p><a class="reference internal" href="#generic-virtual-registers" id="id4">Generic Virtual Registers</a></p></li>
<li><p><a class="reference internal" href="#register-bank" id="id5">Register Bank</a></p></li>
<li><p><a class="reference internal" href="#low-level-type" id="id6">Low Level Type</a></p></li>
<li><p><a class="reference internal" href="#generic-opcode-reference" id="id7">Generic Opcode Reference</a></p></li>
</ul>
</div>
<p>Generic MIR (gMIR) is an intermediate representation that shares the same data
structures as <a class="reference internal" href="../MIRLangRef.html"><span class="doc">MachineIR (MIR)</span></a> but has more relaxed
constraints. As the compilation pipeline proceeds, these constraints are
gradually tightened until gMIR has become MIR.</p>
<p>The rest of this document will assume that you are familiar with the concepts
in <a class="reference internal" href="../MIRLangRef.html"><span class="doc">MachineIR (MIR)</span></a> and will highlight the differences
between MIR and gMIR.</p>
<div class="section" id="generic-machine-instructions">
<span id="gmir-instructions"></span><h2><a class="toc-backref" href="#id3">Generic Machine Instructions</a><a class="headerlink" href="#generic-machine-instructions" title="Permalink to this headline">¶</a></h2>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>This section expands on <a class="reference internal" href="../MIRLangRef.html#mir-instructions"><span class="std std-ref">Machine Instructions</span></a> from the MIR Language
Reference.</p>
</div>
<p>Whereas MIR deals largely in Target Instructions and only has a small set of
target independent opcodes such as <code class="docutils literal notranslate"><span class="pre">COPY</span></code>, <code class="docutils literal notranslate"><span class="pre">PHI</span></code>, and <code class="docutils literal notranslate"><span class="pre">REG_SEQUENCE</span></code>,
gMIR defines a rich collection of <code class="docutils literal notranslate"><span class="pre">Generic</span> <span class="pre">Opcodes</span></code> which are target
independent and describe operations which are typically supported by targets.
One example is <code class="docutils literal notranslate"><span class="pre">G_ADD</span></code> which is the generic opcode for an integer addition.
More information on each of the generic opcodes can be found at
<a class="reference internal" href="GenericOpcode.html"><span class="doc">Generic Opcodes</span></a>.</p>
<p>The <code class="docutils literal notranslate"><span class="pre">MachineIRBuilder</span></code> class wraps the <code class="docutils literal notranslate"><span class="pre">MachineInstrBuilder</span></code> and provides
a convenient way to create these generic instructions.</p>
</div>
<div class="section" id="generic-virtual-registers">
<span id="gmir-gvregs"></span><h2><a class="toc-backref" href="#id4">Generic Virtual Registers</a><a class="headerlink" href="#generic-virtual-registers" title="Permalink to this headline">¶</a></h2>
<div class="admonition note">
<p class="admonition-title">Note</p>
<p>This section expands on <a class="reference internal" href="../MIRLangRef.html#mir-registers"><span class="std std-ref">Registers</span></a> from the MIR Language
Reference.</p>
</div>
<p>Generic virtual registers are like virtual registers but they are not assigned a
Register Class constraint. Instead, generic virtual registers have less strict
constraints starting with a <a class="reference internal" href="#gmir-llt"><span class="std std-ref">Low Level Type</span></a> and then further constrained to a
<a class="reference internal" href="#gmir-regbank"><span class="std std-ref">Register Bank</span></a>. Eventually they will be constrained to a register class
at which point they become normal virtual registers.</p>
<p>Generic virtual registers can be used with all the virtual register API’s
provided by <code class="docutils literal notranslate"><span class="pre">MachineRegisterInfo</span></code>. In particular, the def-use chain API’s can
be used without needing to distinguish them from non-generic virtual registers.</p>
<p>For simplicity, most generic instructions only accept virtual registers (both
generic and non-generic). There are some exceptions to this but in general:</p>
<ul class="simple">
<li><p>instead of immediates, they use a generic virtual register defined by an
instruction that materializes the immediate value (see
<a class="reference internal" href="IRTranslator.html#irtranslator-constants"><span class="std std-ref">Translation of Constants</span></a>). Typically this is a G_CONSTANT or a
G_FCONSTANT. One example of an exception to this rule is G_SEXT_INREG where
having an immediate is mandatory.</p></li>
<li><p>instead of physical register, they use a generic virtual register that is
either defined by a <code class="docutils literal notranslate"><span class="pre">COPY</span></code> from the physical register or used by a <code class="docutils literal notranslate"><span class="pre">COPY</span></code>
that defines the physical register.</p></li>
</ul>
<div class="admonition-historical-note admonition">
<p class="admonition-title">Historical Note</p>
<p>We started with an alternative representation, where MRI tracks a size for
each generic virtual register, and instructions have lists of types.
That had two flaws: the type and size are redundant, and there was no generic
way of getting a given operand’s type (as there was no 1:1 mapping between
instruction types and operands).
We considered putting the type in some variant of MCInstrDesc instead:
See <a class="reference external" href="https://llvm.org/PR26576">PR26576</a>: [GlobalISel] Generic MachineInstrs
need a type but this increases the memory footprint of the related objects</p>
</div>
</div>
<div class="section" id="register-bank">
<span id="gmir-regbank"></span><h2><a class="toc-backref" href="#id5">Register Bank</a><a class="headerlink" href="#register-bank" title="Permalink to this headline">¶</a></h2>
<p>A Register Bank is a set of register classes defined by the target. This
definition is rather loose so let’s talk about what they can achieve.</p>
<p>Suppose we have a processor that has two register files, A and B. These are
equal in every way and support the same instructions for the same cost. They’re
just physically stored apart and each instruction can only access registers from
A or B but never a mix of the two. If we want to perform an operation on data
that’s in split between the two register files, we must first copy all the data
into a single register file.</p>
<p>Given a processor like this, we would benefit from clustering related data
together into one register file so that we minimize the cost of copying data
back and forth to satisfy the (possibly conflicting) requirements of all the
instructions. Register Banks are a means to constrain the register allocator to
use a particular register file for a virtual register.</p>
<p>In practice, register files A and B are rarely equal. They can typically store
the same data but there’s usually some restrictions on what operations you can
do on each register file. A fairly common pattern is for one of them to be
accessible to integer operations and the other accessible to floating point
operations. To accommodate this, let’s rename A and B to GPR (general purpose
registers) and FPR (floating point registers).</p>
<p>We now have some additional constraints that limit us. An operation like G_FMUL
has to happen in FPR and G_ADD has to happen in GPR. However, even though this
prescribes a lot of the assignments we still have some freedom. A G_LOAD can
happen in both GPR and FPR, and which we want depends on who is going to consume
the loaded data. Similarly, G_FNEG can happen in both GPR and FPR. If we assign
it to FPR, then we’ll use floating point negation. However, if we assign it to
GPR then we can equivalently G_XOR the sign bit with 1 to invert it.</p>
<p>In summary, Register Banks are a means of disambiguating between seemingly
equivalent choices based on some analysis of the differences when each choice
is applied in a given context.</p>
<p>To give some concrete examples:</p>
<p>AArch64</p>
<blockquote>
<div><p>AArch64 has three main banks. GPR for integer operations, FPR for floating
point and also for the NEON vector instruction set. The third is CCR and
describes the condition code register used for predication.</p>
</div></blockquote>
<p>MIPS</p>
<blockquote>
<div><p>MIPS has five main banks of which many programs only really use one or two.
GPR is the general purpose bank for integer operations. FGR or CP1 is for
the floating point operations as well as the MSA vector instructions and a
few other application specific extensions. CP0 is for system registers and
few programs will use it. CP2 and CP3 are for any application specific
coprocessors that may be present in the chip. Arguably, there is also a sixth
for the LO and HI registers but these are only used for the result of a few
operations and it’s of questionable value to model distinctly from GPR.</p>
</div></blockquote>
<p>X86</p>
<blockquote>
<div><p>X86 can be seen as having 3 main banks: general-purpose, x87, and
vector (which could be further split into a bank per domain for single vs
double precision instructions). It also looks like there’s arguably a few
more potential banks such as one for the AVX512 Mask Registers.</p>
</div></blockquote>
<p>Register banks are described by a target-provided API,
<a class="reference internal" href="RegBankSelect.html#api-registerbankinfo"><span class="std std-ref">RegisterBankInfo</span></a>.</p>
</div>
<div class="section" id="low-level-type">
<span id="gmir-llt"></span><h2><a class="toc-backref" href="#id6">Low Level Type</a><a class="headerlink" href="#low-level-type" title="Permalink to this headline">¶</a></h2>
<p>Additionally, every generic virtual register has a type, represented by an
instance of the <code class="docutils literal notranslate"><span class="pre">LLT</span></code> class.</p>
<p>Like <code class="docutils literal notranslate"><span class="pre">EVT</span></code>/<code class="docutils literal notranslate"><span class="pre">MVT</span></code>/<code class="docutils literal notranslate"><span class="pre">Type</span></code>, it has no distinction between unsigned and signed
integer types. Furthermore, it also has no distinction between integer and
floating-point types: it mainly conveys absolutely necessary information, such
as size and number of vector lanes:</p>
<ul class="simple">
<li><p><code class="docutils literal notranslate"><span class="pre">sN</span></code> for scalars</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre">pN</span></code> for pointers</p></li>
<li><p><code class="docutils literal notranslate"><span class="pre"><N</span> <span class="pre">x</span> <span class="pre">sM></span></code> for vectors</p></li>
</ul>
<p><code class="docutils literal notranslate"><span class="pre">LLT</span></code> is intended to replace the usage of <code class="docutils literal notranslate"><span class="pre">EVT</span></code> in SelectionDAG.</p>
<p>Here are some LLT examples and their <code class="docutils literal notranslate"><span class="pre">EVT</span></code> and <code class="docutils literal notranslate"><span class="pre">Type</span></code> equivalents:</p>
<blockquote>
<div><table class="docutils align-default">
<colgroup>
<col style="width: 22%" />
<col style="width: 15%" />
<col style="width: 63%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>LLT</p></th>
<th class="head"><p>EVT</p></th>
<th class="head"><p>IR Type</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">s1</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i1</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i1</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">s8</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i8</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i8</span></code></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">s32</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i32</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i32</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">s32</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">f32</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">float</span></code></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">s17</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i17</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i17</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">s16</span></code></p></td>
<td><p>N/A</p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">{i8,</span> <span class="pre">i8}</span></code> <a class="footnote-reference brackets" href="#abi-dependent" id="id1">1</a></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">s32</span></code></p></td>
<td><p>N/A</p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">[4</span> <span class="pre">x</span> <span class="pre">i8]</span></code> <a class="footnote-reference brackets" href="#abi-dependent" id="id2">1</a></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">p0</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">iPTR</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i8*</span></code>, <code class="docutils literal notranslate"><span class="pre">i32*</span></code>, <code class="docutils literal notranslate"><span class="pre">%opaque*</span></code></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">p2</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">iPTR</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">i8</span> <span class="pre">addrspace(2)*</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre"><4</span> <span class="pre">x</span> <span class="pre">s32></span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">v4f32</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre"><4</span> <span class="pre">x</span> <span class="pre">float></span></code></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">s64</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">v1f64</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre"><1</span> <span class="pre">x</span> <span class="pre">double></span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre"><3</span> <span class="pre">x</span> <span class="pre">s32></span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre">v3i32</span></code></p></td>
<td><p><code class="docutils literal notranslate"><span class="pre"><3</span> <span class="pre">x</span> <span class="pre">i32></span></code></p></td>
</tr>
</tbody>
</table>
</div></blockquote>
<p>Rationale: instructions already encode a specific interpretation of types
(e.g., <code class="docutils literal notranslate"><span class="pre">add</span></code> vs. <code class="docutils literal notranslate"><span class="pre">fadd</span></code>, or <code class="docutils literal notranslate"><span class="pre">sdiv</span></code> vs. <code class="docutils literal notranslate"><span class="pre">udiv</span></code>). Also encoding that
information in the type system requires introducing bitcast with no real
advantage for the selector.</p>
<p>Pointer types are distinguished by address space. This matches IR, as opposed
to SelectionDAG where address space is an attribute on operations.
This representation better supports pointers having different sizes depending
on their addressspace.</p>
<div class="admonition note">
<p class="admonition-title">Note</p>
<div class="admonition caution">
<p class="admonition-title">Caution</p>
<p>Is this still true? I thought we’d removed the 1-element vector concept.
Hypothetically, it could be distinct from a scalar but I think we failed to
find a real occurrence.</p>
</div>
<p>Currently, LLT requires at least 2 elements in vectors, but some targets have
the concept of a ‘1-element vector’. Representing them as their underlying
scalar type is a nice simplification.</p>
</div>
<p class="rubric">Footnotes</p>
<dl class="footnote brackets">
<dt class="label" id="abi-dependent"><span class="brackets">1</span><span class="fn-backref">(<a href="#id1">1</a>,<a href="#id2">2</a>)</span></dt>
<dd><p>This mapping is ABI dependent. Here we’ve assumed no additional padding is required.</p>
</dd>
</dl>
</div>
<div class="section" id="generic-opcode-reference">
<h2><a class="toc-backref" href="#id7">Generic Opcode Reference</a><a class="headerlink" href="#generic-opcode-reference" title="Permalink to this headline">¶</a></h2>
<p>The Generic Opcodes that are available are described at <a class="reference internal" href="GenericOpcode.html"><span class="doc">Generic Opcodes</span></a>.</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="GenericOpcode.html" title="Generic Opcodes"
>next</a> |</li>
<li class="right" >
<a href="index.html" title="Global Instruction Selection"
>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="">Generic Machine IR</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>
|
