[SimplifyCFG] Don't create unnecessary PHIs
[oota-llvm.git] / docs / MIRLangRef.rst
1 ========================================
2 Machine IR (MIR) Format Reference Manual
3 ========================================
4
5 .. contents::
6    :local:
7
8 .. warning::
9   This is a work in progress.
10
11 Introduction
12 ============
13
14 This document is a reference manual for the Machine IR (MIR) serialization
15 format. MIR is a human readable serialization format that is used to represent
16 LLVM's :ref:`machine specific intermediate representation
17 <machine code representation>`.
18
19 The MIR serialization format is designed to be used for testing the code
20 generation passes in LLVM.
21
22 Overview
23 ========
24
25 The MIR serialization format uses a YAML container. YAML is a standard
26 data serialization language, and the full YAML language spec can be read at
27 `yaml.org
28 <http://www.yaml.org/spec/1.2/spec.html#Introduction>`_.
29
30 A MIR file is split up into a series of `YAML documents`_. The first document
31 can contain an optional embedded LLVM IR module, and the rest of the documents
32 contain the serialized machine functions.
33
34 .. _YAML documents: http://www.yaml.org/spec/1.2/spec.html#id2800132
35
36 MIR Testing Guide
37 =================
38
39 You can use the MIR format for testing in two different ways:
40
41 - You can write MIR tests that invoke a single code generation pass using the
42   ``run-pass`` option in llc.
43
44 - You can use llc's ``stop-after`` option with existing or new LLVM assembly
45   tests and check the MIR output of a specific code generation pass.
46
47 Testing Individual Code Generation Passes
48 -----------------------------------------
49
50 The ``run-pass`` option in llc allows you to create MIR tests that invoke
51 just a single code generation pass. When this option is used, llc will parse
52 an input MIR file, run the specified code generation pass, and print the
53 resulting MIR to the standard output stream.
54
55 You can generate an input MIR file for the test by using the ``stop-after``
56 option in llc. For example, if you would like to write a test for the
57 post register allocation pseudo instruction expansion pass, you can specify
58 the machine copy propagation pass in the ``stop-after`` option, as it runs
59 just before the pass that we are trying to test:
60
61    ``llc -stop-after machine-cp bug-trigger.ll > test.mir``
62
63 After generating the input MIR file, you'll have to add a run line that uses
64 the ``-run-pass`` option to it. In order to test the post register allocation
65 pseudo instruction expansion pass on X86-64, a run line like the one shown
66 below can be used:
67
68     ``# RUN: llc -run-pass postrapseudos -march=x86-64 %s -o /dev/null | FileCheck %s``
69
70 The MIR files are target dependent, so they have to be placed in the target
71 specific test directories. They also need to specify a target triple or a
72 target architecture either in the run line or in the embedded LLVM IR module.
73
74 Limitations
75 -----------
76
77 Currently the MIR format has several limitations in terms of which state it
78 can serialize:
79
80 - The target-specific state in the target-specific ``MachineFunctionInfo``
81   subclasses isn't serialized at the moment.
82
83 - The target-specific ``MachineConstantPoolValue`` subclasses (in the ARM and
84   SystemZ backends) aren't serialized at the moment.
85
86 - The ``MCSymbol`` machine operands are only printed, they can't be parsed.
87
88 - A lot of the state in ``MachineModuleInfo`` isn't serialized - only the CFI
89   instructions and the variable debug information from MMI is serialized right
90   now.
91
92 These limitations impose restrictions on what you can test with the MIR format.
93 For now, tests that would like to test some behaviour that depends on the state
94 of certain ``MCSymbol``  operands or the exception handling state in MMI, can't
95 use the MIR format. As well as that, tests that test some behaviour that
96 depends on the state of the target specific ``MachineFunctionInfo`` or
97 ``MachineConstantPoolValue`` subclasses can't use the MIR format at the moment.
98
99 High Level Structure
100 ====================
101
102 .. _embedded-module:
103
104 Embedded Module
105 ---------------
106
107 When the first YAML document contains a `YAML block literal string`_, the MIR
108 parser will treat this string as an LLVM assembly language string that
109 represents an embedded LLVM IR module.
110 Here is an example of a YAML document that contains an LLVM module:
111
112 .. code-block:: llvm
113
114      --- |
115        define i32 @inc(i32* %x) {
116        entry:
117          %0 = load i32, i32* %x
118          %1 = add i32 %0, 1
119          store i32 %1, i32* %x
120          ret i32 %1
121        }
122      ...
123
124 .. _YAML block literal string: http://www.yaml.org/spec/1.2/spec.html#id2795688
125
126 Machine Functions
127 -----------------
128
129 The remaining YAML documents contain the machine functions. This is an example
130 of such YAML document:
131
132 .. code-block:: llvm
133
134      ---
135      name:            inc
136      tracksRegLiveness: true
137      liveins:
138        - { reg: '%rdi' }
139      body: |
140        bb.0.entry:
141          liveins: %rdi
142
143          %eax = MOV32rm %rdi, 1, _, 0, _
144          %eax = INC32r killed %eax, implicit-def dead %eflags
145          MOV32mr killed %rdi, 1, _, 0, _, %eax
146          RETQ %eax
147      ...
148
149 The document above consists of attributes that represent the various
150 properties and data structures in a machine function.
151
152 The attribute ``name`` is required, and its value should be identical to the
153 name of a function that this machine function is based on.
154
155 The attribute ``body`` is a `YAML block literal string`_. Its value represents
156 the function's machine basic blocks and their machine instructions.
157
158 Machine Instructions Format Reference
159 =====================================
160
161 The machine basic blocks and their instructions are represented using a custom,
162 human readable serialization language. This language is used in the
163 `YAML block literal string`_ that corresponds to the machine function's body.
164
165 A source string that uses this language contains a list of machine basic
166 blocks, which are described in the section below.
167
168 Machine Basic Blocks
169 --------------------
170
171 A machine basic block is defined in a single block definition source construct
172 that contains the block's ID.
173 The example below defines two blocks that have an ID of zero and one:
174
175 .. code-block:: llvm
176
177     bb.0:
178       <instructions>
179     bb.1:
180       <instructions>
181
182 A machine basic block can also have a name. It should be specified after the ID
183 in the block's definition:
184
185 .. code-block:: llvm
186
187     bb.0.entry:       ; This block's name is "entry"
188        <instructions>
189
190 The block's name should be identical to the name of the IR block that this
191 machine block is based on.
192
193 Block References
194 ^^^^^^^^^^^^^^^^
195
196 The machine basic blocks are identified by their ID numbers. Individual
197 blocks are referenced using the following syntax:
198
199 .. code-block:: llvm
200
201     %bb.<id>[.<name>]
202
203 Examples:
204
205 .. code-block:: llvm
206
207     %bb.0
208     %bb.1.then
209
210 Successors
211 ^^^^^^^^^^
212
213 The machine basic block's successors have to be specified before any of the
214 instructions:
215
216 .. code-block:: llvm
217
218     bb.0.entry:
219       successors: %bb.1.then, %bb.2.else
220       <instructions>
221     bb.1.then:
222       <instructions>
223     bb.2.else:
224       <instructions>
225
226 The branch weights can be specified in brackets after the successor blocks.
227 The example below defines a block that has two successors with branch weights
228 of 32 and 16:
229
230 .. code-block:: llvm
231
232     bb.0.entry:
233       successors: %bb.1.then(32), %bb.2.else(16)
234
235 .. _bb-liveins:
236
237 Live In Registers
238 ^^^^^^^^^^^^^^^^^
239
240 The machine basic block's live in registers have to be specified before any of
241 the instructions:
242
243 .. code-block:: llvm
244
245     bb.0.entry:
246       liveins: %edi, %esi
247
248 The list of live in registers and successors can be empty. The language also
249 allows multiple live in register and successor lists - they are combined into
250 one list by the parser.
251
252 Miscellaneous Attributes
253 ^^^^^^^^^^^^^^^^^^^^^^^^
254
255 The attributes ``IsAddressTaken``, ``IsLandingPad`` and ``Alignment`` can be
256 specified in brackets after the block's definition:
257
258 .. code-block:: llvm
259
260     bb.0.entry (address-taken):
261       <instructions>
262     bb.2.else (align 4):
263       <instructions>
264     bb.3(landing-pad, align 4):
265       <instructions>
266
267 .. TODO: Describe the way the reference to an unnamed LLVM IR block can be
268    preserved.
269
270 Machine Instructions
271 --------------------
272
273 A machine instruction is composed of a name,
274 :ref:`machine operands <machine-operands>`,
275 :ref:`instruction flags <instruction-flags>`, and machine memory operands.
276
277 The instruction's name is usually specified before the operands. The example
278 below shows an instance of the X86 ``RETQ`` instruction with a single machine
279 operand:
280
281 .. code-block:: llvm
282
283     RETQ %eax
284
285 However, if the machine instruction has one or more explicitly defined register
286 operands, the instruction's name has to be specified after them. The example
287 below shows an instance of the AArch64 ``LDPXpost`` instruction with three
288 defined register operands:
289
290 .. code-block:: llvm
291
292     %sp, %fp, %lr = LDPXpost %sp, 2
293
294 The instruction names are serialized using the exact definitions from the
295 target's ``*InstrInfo.td`` files, and they are case sensitive. This means that
296 similar instruction names like ``TSTri`` and ``tSTRi`` represent different
297 machine instructions.
298
299 .. _instruction-flags:
300
301 Instruction Flags
302 ^^^^^^^^^^^^^^^^^
303
304 The flag ``frame-setup`` can be specified before the instruction's name:
305
306 .. code-block:: llvm
307
308     %fp = frame-setup ADDXri %sp, 0, 0
309
310 .. _registers:
311
312 Registers
313 ---------
314
315 Registers are one of the key primitives in the machine instructions
316 serialization language. They are primarly used in the
317 :ref:`register machine operands <register-operands>`,
318 but they can also be used in a number of other places, like the
319 :ref:`basic block's live in list <bb-liveins>`.
320
321 The physical registers are identified by their name. They use the following
322 syntax:
323
324 .. code-block:: llvm
325
326     %<name>
327
328 The example below shows three X86 physical registers:
329
330 .. code-block:: llvm
331
332     %eax
333     %r15
334     %eflags
335
336 The virtual registers are identified by their ID number. They use the following
337 syntax:
338
339 .. code-block:: llvm
340
341     %<id>
342
343 Example:
344
345 .. code-block:: llvm
346
347     %0
348
349 The null registers are represented using an underscore ('``_``'). They can also be
350 represented using a '``%noreg``' named register, although the former syntax
351 is preferred.
352
353 .. _machine-operands:
354
355 Machine Operands
356 ----------------
357
358 There are seventeen different kinds of machine operands, and all of them, except
359 the ``MCSymbol`` operand, can be serialized. The ``MCSymbol`` operands are
360 just printed out - they can't be parsed back yet.
361
362 Immediate Operands
363 ^^^^^^^^^^^^^^^^^^
364
365 The immediate machine operands are untyped, 64-bit signed integers. The
366 example below shows an instance of the X86 ``MOV32ri`` instruction that has an
367 immediate machine operand ``-42``:
368
369 .. code-block:: llvm
370
371     %eax = MOV32ri -42
372
373 .. TODO: Describe the CIMM (Rare) and FPIMM immediate operands.
374
375 .. _register-operands:
376
377 Register Operands
378 ^^^^^^^^^^^^^^^^^
379
380 The :ref:`register <registers>` primitive is used to represent the register
381 machine operands. The register operands can also have optional
382 :ref:`register flags <register-flags>`,
383 :ref:`a subregister index <subregister-indices>`,
384 and a reference to the tied register operand.
385 The full syntax of a register operand is shown below:
386
387 .. code-block:: llvm
388
389     [<flags>] <register> [ :<subregister-idx-name> ] [ (tied-def <tied-op>) ]
390
391 This example shows an instance of the X86 ``XOR32rr`` instruction that has
392 5 register operands with different register flags:
393
394 .. code-block:: llvm
395
396   dead %eax = XOR32rr undef %eax, undef %eax, implicit-def dead %eflags, implicit-def %al
397
398 .. _register-flags:
399
400 Register Flags
401 ~~~~~~~~~~~~~~
402
403 The table below shows all of the possible register flags along with the
404 corresponding internal ``llvm::RegState`` representation:
405
406 .. list-table::
407    :header-rows: 1
408
409    * - Flag
410      - Internal Value
411
412    * - ``implicit``
413      - ``RegState::Implicit``
414
415    * - ``implicit-def``
416      - ``RegState::ImplicitDefine``
417
418    * - ``def``
419      - ``RegState::Define``
420
421    * - ``dead``
422      - ``RegState::Dead``
423
424    * - ``killed``
425      - ``RegState::Kill``
426
427    * - ``undef``
428      - ``RegState::Undef``
429
430    * - ``internal``
431      - ``RegState::InternalRead``
432
433    * - ``early-clobber``
434      - ``RegState::EarlyClobber``
435
436    * - ``debug-use``
437      - ``RegState::Debug``
438
439 .. _subregister-indices:
440
441 Subregister Indices
442 ~~~~~~~~~~~~~~~~~~~
443
444 The register machine operands can reference a portion of a register by using
445 the subregister indices. The example below shows an instance of the ``COPY``
446 pseudo instruction that uses the X86 ``sub_8bit`` subregister index to copy 8
447 lower bits from the 32-bit virtual register 0 to the 8-bit virtual register 1:
448
449 .. code-block:: llvm
450
451     %1 = COPY %0:sub_8bit
452
453 The names of the subregister indices are target specific, and are typically
454 defined in the target's ``*RegisterInfo.td`` file.
455
456 Global Value Operands
457 ^^^^^^^^^^^^^^^^^^^^^
458
459 The global value machine operands reference the global values from the
460 :ref:`embedded LLVM IR module <embedded-module>`.
461 The example below shows an instance of the X86 ``MOV64rm`` instruction that has
462 a global value operand named ``G``:
463
464 .. code-block:: llvm
465
466     %rax = MOV64rm %rip, 1, _, @G, _
467
468 The named global values are represented using an identifier with the '@' prefix.
469 If the identifier doesn't match the regular expression
470 `[-a-zA-Z$._][-a-zA-Z$._0-9]*`, then this identifier must be quoted.
471
472 The unnamed global values are represented using an unsigned numeric value with
473 the '@' prefix, like in the following examples: ``@0``, ``@989``.
474
475 .. TODO: Describe the parsers default behaviour when optional YAML attributes
476    are missing.
477 .. TODO: Describe the syntax for the bundled instructions.
478 .. TODO: Describe the syntax for virtual register YAML definitions.
479 .. TODO: Describe the machine function's YAML flag attributes.
480 .. TODO: Describe the syntax for the external symbol and register
481    mask machine operands.
482 .. TODO: Describe the frame information YAML mapping.
483 .. TODO: Describe the syntax of the stack object machine operands and their
484    YAML definitions.
485 .. TODO: Describe the syntax of the constant pool machine operands and their
486    YAML definitions.
487 .. TODO: Describe the syntax of the jump table machine operands and their
488    YAML definitions.
489 .. TODO: Describe the syntax of the block address machine operands.
490 .. TODO: Describe the syntax of the CFI index machine operands.
491 .. TODO: Describe the syntax of the metadata machine operands, and the
492    instructions debug location attribute.
493 .. TODO: Describe the syntax of the target index machine operands.
494 .. TODO: Describe the syntax of the register live out machine operands.
495 .. TODO: Describe the syntax of the machine memory operands.