[OCaml] Add Target and TargetMachine bindings to Llvm_target
[oota-llvm.git] / docs / CodeGenerator.rst
1 ==========================================
2 The LLVM Target-Independent Code Generator
3 ==========================================
4
5 .. role:: raw-html(raw)
6    :format: html
7
8 .. raw:: html
9
10   <style>
11     .unknown { background-color: #C0C0C0; text-align: center; }
12     .unknown:before { content: "?" }
13     .no { background-color: #C11B17 }
14     .no:before { content: "N" }
15     .partial { background-color: #F88017 }
16     .yes { background-color: #0F0; }
17     .yes:before { content: "Y" }
18     .na { background-color: #6666FF; }
19     .na:before { content: "N/A" }
20   </style>
21
22 .. contents::
23    :local:
24
25 .. warning::
26   This is a work in progress.
27
28 Introduction
29 ============
30
31 The LLVM target-independent code generator is a framework that provides a suite
32 of reusable components for translating the LLVM internal representation to the
33 machine code for a specified target---either in assembly form (suitable for a
34 static compiler) or in binary machine code format (usable for a JIT
35 compiler). The LLVM target-independent code generator consists of six main
36 components:
37
38 1. `Abstract target description`_ interfaces which capture important properties
39    about various aspects of the machine, independently of how they will be used.
40    These interfaces are defined in ``include/llvm/Target/``.
41
42 2. Classes used to represent the `code being generated`_ for a target.  These
43    classes are intended to be abstract enough to represent the machine code for
44    *any* target machine.  These classes are defined in
45    ``include/llvm/CodeGen/``. At this level, concepts like "constant pool
46    entries" and "jump tables" are explicitly exposed.
47
48 3. Classes and algorithms used to represent code as the object file level, the
49    `MC Layer`_.  These classes represent assembly level constructs like labels,
50    sections, and instructions.  At this level, concepts like "constant pool
51    entries" and "jump tables" don't exist.
52
53 4. `Target-independent algorithms`_ used to implement various phases of native
54    code generation (register allocation, scheduling, stack frame representation,
55    etc).  This code lives in ``lib/CodeGen/``.
56
57 5. `Implementations of the abstract target description interfaces`_ for
58    particular targets.  These machine descriptions make use of the components
59    provided by LLVM, and can optionally provide custom target-specific passes,
60    to build complete code generators for a specific target.  Target descriptions
61    live in ``lib/Target/``.
62
63 6. The target-independent JIT components.  The LLVM JIT is completely target
64    independent (it uses the ``TargetJITInfo`` structure to interface for
65    target-specific issues.  The code for the target-independent JIT lives in
66    ``lib/ExecutionEngine/JIT``.
67
68 Depending on which part of the code generator you are interested in working on,
69 different pieces of this will be useful to you.  In any case, you should be
70 familiar with the `target description`_ and `machine code representation`_
71 classes.  If you want to add a backend for a new target, you will need to
72 `implement the target description`_ classes for your new target and understand
73 the `LLVM code representation <LangRef.html>`_.  If you are interested in
74 implementing a new `code generation algorithm`_, it should only depend on the
75 target-description and machine code representation classes, ensuring that it is
76 portable.
77
78 Required components in the code generator
79 -----------------------------------------
80
81 The two pieces of the LLVM code generator are the high-level interface to the
82 code generator and the set of reusable components that can be used to build
83 target-specific backends.  The two most important interfaces (:raw-html:`<tt>`
84 `TargetMachine`_ :raw-html:`</tt>` and :raw-html:`<tt>` `DataLayout`_
85 :raw-html:`</tt>`) are the only ones that are required to be defined for a
86 backend to fit into the LLVM system, but the others must be defined if the
87 reusable code generator components are going to be used.
88
89 This design has two important implications.  The first is that LLVM can support
90 completely non-traditional code generation targets.  For example, the C backend
91 does not require register allocation, instruction selection, or any of the other
92 standard components provided by the system.  As such, it only implements these
93 two interfaces, and does its own thing. Note that C backend was removed from the
94 trunk since LLVM 3.1 release. Another example of a code generator like this is a
95 (purely hypothetical) backend that converts LLVM to the GCC RTL form and uses
96 GCC to emit machine code for a target.
97
98 This design also implies that it is possible to design and implement radically
99 different code generators in the LLVM system that do not make use of any of the
100 built-in components.  Doing so is not recommended at all, but could be required
101 for radically different targets that do not fit into the LLVM machine
102 description model: FPGAs for example.
103
104 .. _high-level design of the code generator:
105
106 The high-level design of the code generator
107 -------------------------------------------
108
109 The LLVM target-independent code generator is designed to support efficient and
110 quality code generation for standard register-based microprocessors.  Code
111 generation in this model is divided into the following stages:
112
113 1. `Instruction Selection`_ --- This phase determines an efficient way to
114    express the input LLVM code in the target instruction set.  This stage
115    produces the initial code for the program in the target instruction set, then
116    makes use of virtual registers in SSA form and physical registers that
117    represent any required register assignments due to target constraints or
118    calling conventions.  This step turns the LLVM code into a DAG of target
119    instructions.
120
121 2. `Scheduling and Formation`_ --- This phase takes the DAG of target
122    instructions produced by the instruction selection phase, determines an
123    ordering of the instructions, then emits the instructions as :raw-html:`<tt>`
124    `MachineInstr`_\s :raw-html:`</tt>` with that ordering.  Note that we
125    describe this in the `instruction selection section`_ because it operates on
126    a `SelectionDAG`_.
127
128 3. `SSA-based Machine Code Optimizations`_ --- This optional stage consists of a
129    series of machine-code optimizations that operate on the SSA-form produced by
130    the instruction selector.  Optimizations like modulo-scheduling or peephole
131    optimization work here.
132
133 4. `Register Allocation`_ --- The target code is transformed from an infinite
134    virtual register file in SSA form to the concrete register file used by the
135    target.  This phase introduces spill code and eliminates all virtual register
136    references from the program.
137
138 5. `Prolog/Epilog Code Insertion`_ --- Once the machine code has been generated
139    for the function and the amount of stack space required is known (used for
140    LLVM alloca's and spill slots), the prolog and epilog code for the function
141    can be inserted and "abstract stack location references" can be eliminated.
142    This stage is responsible for implementing optimizations like frame-pointer
143    elimination and stack packing.
144
145 6. `Late Machine Code Optimizations`_ --- Optimizations that operate on "final"
146    machine code can go here, such as spill code scheduling and peephole
147    optimizations.
148
149 7. `Code Emission`_ --- The final stage actually puts out the code for the
150    current function, either in the target assembler format or in machine
151    code.
152
153 The code generator is based on the assumption that the instruction selector will
154 use an optimal pattern matching selector to create high-quality sequences of
155 native instructions.  Alternative code generator designs based on pattern
156 expansion and aggressive iterative peephole optimization are much slower.  This
157 design permits efficient compilation (important for JIT environments) and
158 aggressive optimization (used when generating code offline) by allowing
159 components of varying levels of sophistication to be used for any step of
160 compilation.
161
162 In addition to these stages, target implementations can insert arbitrary
163 target-specific passes into the flow.  For example, the X86 target uses a
164 special pass to handle the 80x87 floating point stack architecture.  Other
165 targets with unusual requirements can be supported with custom passes as needed.
166
167 Using TableGen for target description
168 -------------------------------------
169
170 The target description classes require a detailed description of the target
171 architecture.  These target descriptions often have a large amount of common
172 information (e.g., an ``add`` instruction is almost identical to a ``sub``
173 instruction).  In order to allow the maximum amount of commonality to be
174 factored out, the LLVM code generator uses the
175 :doc:`TableGen <TableGenFundamentals>` tool to describe big chunks of the
176 target machine, which allows the use of domain-specific and target-specific
177 abstractions to reduce the amount of repetition.
178
179 As LLVM continues to be developed and refined, we plan to move more and more of
180 the target description to the ``.td`` form.  Doing so gives us a number of
181 advantages.  The most important is that it makes it easier to port LLVM because
182 it reduces the amount of C++ code that has to be written, and the surface area
183 of the code generator that needs to be understood before someone can get
184 something working.  Second, it makes it easier to change things. In particular,
185 if tables and other things are all emitted by ``tblgen``, we only need a change
186 in one place (``tblgen``) to update all of the targets to a new interface.
187
188 .. _Abstract target description:
189 .. _target description:
190
191 Target description classes
192 ==========================
193
194 The LLVM target description classes (located in the ``include/llvm/Target``
195 directory) provide an abstract description of the target machine independent of
196 any particular client.  These classes are designed to capture the *abstract*
197 properties of the target (such as the instructions and registers it has), and do
198 not incorporate any particular pieces of code generation algorithms.
199
200 All of the target description classes (except the :raw-html:`<tt>` `DataLayout`_
201 :raw-html:`</tt>` class) are designed to be subclassed by the concrete target
202 implementation, and have virtual methods implemented.  To get to these
203 implementations, the :raw-html:`<tt>` `TargetMachine`_ :raw-html:`</tt>` class
204 provides accessors that should be implemented by the target.
205
206 .. _TargetMachine:
207
208 The ``TargetMachine`` class
209 ---------------------------
210
211 The ``TargetMachine`` class provides virtual methods that are used to access the
212 target-specific implementations of the various target description classes via
213 the ``get*Info`` methods (``getInstrInfo``, ``getRegisterInfo``,
214 ``getFrameInfo``, etc.).  This class is designed to be specialized by a concrete
215 target implementation (e.g., ``X86TargetMachine``) which implements the various
216 virtual methods.  The only required target description class is the
217 :raw-html:`<tt>` `DataLayout`_ :raw-html:`</tt>` class, but if the code
218 generator components are to be used, the other interfaces should be implemented
219 as well.
220
221 .. _DataLayout:
222
223 The ``DataLayout`` class
224 ------------------------
225
226 The ``DataLayout`` class is the only required target description class, and it
227 is the only class that is not extensible (you cannot derive a new class from
228 it).  ``DataLayout`` specifies information about how the target lays out memory
229 for structures, the alignment requirements for various data types, the size of
230 pointers in the target, and whether the target is little-endian or
231 big-endian.
232
233 .. _TargetLowering:
234
235 The ``TargetLowering`` class
236 ----------------------------
237
238 The ``TargetLowering`` class is used by SelectionDAG based instruction selectors
239 primarily to describe how LLVM code should be lowered to SelectionDAG
240 operations.  Among other things, this class indicates:
241
242 * an initial register class to use for various ``ValueType``\s,
243
244 * which operations are natively supported by the target machine,
245
246 * the return type of ``setcc`` operations,
247
248 * the type to use for shift amounts, and
249
250 * various high-level characteristics, like whether it is profitable to turn
251   division by a constant into a multiplication sequence.
252
253 .. _TargetRegisterInfo:
254
255 The ``TargetRegisterInfo`` class
256 --------------------------------
257
258 The ``TargetRegisterInfo`` class is used to describe the register file of the
259 target and any interactions between the registers.
260
261 Registers are represented in the code generator by unsigned integers.  Physical
262 registers (those that actually exist in the target description) are unique
263 small numbers, and virtual registers are generally large.  Note that
264 register ``#0`` is reserved as a flag value.
265
266 Each register in the processor description has an associated
267 ``TargetRegisterDesc`` entry, which provides a textual name for the register
268 (used for assembly output and debugging dumps) and a set of aliases (used to
269 indicate whether one register overlaps with another).
270
271 In addition to the per-register description, the ``TargetRegisterInfo`` class
272 exposes a set of processor specific register classes (instances of the
273 ``TargetRegisterClass`` class).  Each register class contains sets of registers
274 that have the same properties (for example, they are all 32-bit integer
275 registers).  Each SSA virtual register created by the instruction selector has
276 an associated register class.  When the register allocator runs, it replaces
277 virtual registers with a physical register in the set.
278
279 The target-specific implementations of these classes is auto-generated from a
280 `TableGen <TableGenFundamentals.html>`_ description of the register file.
281
282 .. _TargetInstrInfo:
283
284 The ``TargetInstrInfo`` class
285 -----------------------------
286
287 The ``TargetInstrInfo`` class is used to describe the machine instructions
288 supported by the target.  Descriptions define things like the mnemonic for
289 the opcode, the number of operands, the list of implicit register uses and defs,
290 whether the instruction has certain target-independent properties (accesses
291 memory, is commutable, etc), and holds any target-specific flags.
292
293 The ``TargetFrameInfo`` class
294 -----------------------------
295
296 The ``TargetFrameInfo`` class is used to provide information about the stack
297 frame layout of the target. It holds the direction of stack growth, the known
298 stack alignment on entry to each function, and the offset to the local area.
299 The offset to the local area is the offset from the stack pointer on function
300 entry to the first location where function data (local variables, spill
301 locations) can be stored.
302
303 The ``TargetSubtarget`` class
304 -----------------------------
305
306 The ``TargetSubtarget`` class is used to provide information about the specific
307 chip set being targeted.  A sub-target informs code generation of which
308 instructions are supported, instruction latencies and instruction execution
309 itinerary; i.e., which processing units are used, in what order, and for how
310 long.
311
312 The ``TargetJITInfo`` class
313 ---------------------------
314
315 The ``TargetJITInfo`` class exposes an abstract interface used by the
316 Just-In-Time code generator to perform target-specific activities, such as
317 emitting stubs.  If a ``TargetMachine`` supports JIT code generation, it should
318 provide one of these objects through the ``getJITInfo`` method.
319
320 .. _code being generated:
321 .. _machine code representation:
322
323 Machine code description classes
324 ================================
325
326 At the high-level, LLVM code is translated to a machine specific representation
327 formed out of :raw-html:`<tt>` `MachineFunction`_ :raw-html:`</tt>`,
328 :raw-html:`<tt>` `MachineBasicBlock`_ :raw-html:`</tt>`, and :raw-html:`<tt>`
329 `MachineInstr`_ :raw-html:`</tt>` instances (defined in
330 ``include/llvm/CodeGen``).  This representation is completely target agnostic,
331 representing instructions in their most abstract form: an opcode and a series of
332 operands.  This representation is designed to support both an SSA representation
333 for machine code, as well as a register allocated, non-SSA form.
334
335 .. _MachineInstr:
336
337 The ``MachineInstr`` class
338 --------------------------
339
340 Target machine instructions are represented as instances of the ``MachineInstr``
341 class.  This class is an extremely abstract way of representing machine
342 instructions.  In particular, it only keeps track of an opcode number and a set
343 of operands.
344
345 The opcode number is a simple unsigned integer that only has meaning to a
346 specific backend.  All of the instructions for a target should be defined in the
347 ``*InstrInfo.td`` file for the target. The opcode enum values are auto-generated
348 from this description.  The ``MachineInstr`` class does not have any information
349 about how to interpret the instruction (i.e., what the semantics of the
350 instruction are); for that you must refer to the :raw-html:`<tt>`
351 `TargetInstrInfo`_ :raw-html:`</tt>` class.
352
353 The operands of a machine instruction can be of several different types: a
354 register reference, a constant integer, a basic block reference, etc.  In
355 addition, a machine operand should be marked as a def or a use of the value
356 (though only registers are allowed to be defs).
357
358 By convention, the LLVM code generator orders instruction operands so that all
359 register definitions come before the register uses, even on architectures that
360 are normally printed in other orders.  For example, the SPARC add instruction:
361 "``add %i1, %i2, %i3``" adds the "%i1", and "%i2" registers and stores the
362 result into the "%i3" register.  In the LLVM code generator, the operands should
363 be stored as "``%i3, %i1, %i2``": with the destination first.
364
365 Keeping destination (definition) operands at the beginning of the operand list
366 has several advantages.  In particular, the debugging printer will print the
367 instruction like this:
368
369 .. code-block:: llvm
370
371   %r3 = add %i1, %i2
372
373 Also if the first operand is a def, it is easier to `create instructions`_ whose
374 only def is the first operand.
375
376 .. _create instructions:
377
378 Using the ``MachineInstrBuilder.h`` functions
379 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
380
381 Machine instructions are created by using the ``BuildMI`` functions, located in
382 the ``include/llvm/CodeGen/MachineInstrBuilder.h`` file.  The ``BuildMI``
383 functions make it easy to build arbitrary machine instructions.  Usage of the
384 ``BuildMI`` functions look like this:
385
386 .. code-block:: c++
387
388   // Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
389   // instruction.  The '1' specifies how many operands will be added.
390   MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
391
392   // Create the same instr, but insert it at the end of a basic block.
393   MachineBasicBlock &MBB = ...
394   BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
395
396   // Create the same instr, but insert it before a specified iterator point.
397   MachineBasicBlock::iterator MBBI = ...
398   BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
399
400   // Create a 'cmp Reg, 0' instruction, no destination reg.
401   MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
402
403   // Create an 'sahf' instruction which takes no operands and stores nothing.
404   MI = BuildMI(X86::SAHF, 0);
405
406   // Create a self looping branch instruction.
407   BuildMI(MBB, X86::JNE, 1).addMBB(&MBB);
408
409 The key thing to remember with the ``BuildMI`` functions is that you have to
410 specify the number of operands that the machine instruction will take.  This
411 allows for efficient memory allocation.  You also need to specify if operands
412 default to be uses of values, not definitions.  If you need to add a definition
413 operand (other than the optional destination register), you must explicitly mark
414 it as such:
415
416 .. code-block:: c++
417
418   MI.addReg(Reg, RegState::Define);
419
420 Fixed (preassigned) registers
421 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
422
423 One important issue that the code generator needs to be aware of is the presence
424 of fixed registers.  In particular, there are often places in the instruction
425 stream where the register allocator *must* arrange for a particular value to be
426 in a particular register.  This can occur due to limitations of the instruction
427 set (e.g., the X86 can only do a 32-bit divide with the ``EAX``/``EDX``
428 registers), or external factors like calling conventions.  In any case, the
429 instruction selector should emit code that copies a virtual register into or out
430 of a physical register when needed.
431
432 For example, consider this simple LLVM example:
433
434 .. code-block:: llvm
435
436   define i32 @test(i32 %X, i32 %Y) {
437     %Z = udiv i32 %X, %Y
438     ret i32 %Z
439   }
440
441 The X86 instruction selector produces this machine code for the ``div`` and
442 ``ret`` (use "``llc X.bc -march=x86 -print-machineinstrs``" to get this):
443
444 .. code-block:: llvm
445
446   ;; Start of div
447   %EAX = mov %reg1024           ;; Copy X (in reg1024) into EAX
448   %reg1027 = sar %reg1024, 31
449   %EDX = mov %reg1027           ;; Sign extend X into EDX
450   idiv %reg1025                 ;; Divide by Y (in reg1025)
451   %reg1026 = mov %EAX           ;; Read the result (Z) out of EAX
452
453   ;; Start of ret
454   %EAX = mov %reg1026           ;; 32-bit return value goes in EAX
455   ret
456
457 By the end of code generation, the register allocator has coalesced the
458 registers and deleted the resultant identity moves producing the following
459 code:
460
461 .. code-block:: llvm
462
463   ;; X is in EAX, Y is in ECX
464   mov %EAX, %EDX
465   sar %EDX, 31
466   idiv %ECX
467   ret 
468
469 This approach is extremely general (if it can handle the X86 architecture, it
470 can handle anything!) and allows all of the target specific knowledge about the
471 instruction stream to be isolated in the instruction selector.  Note that
472 physical registers should have a short lifetime for good code generation, and
473 all physical registers are assumed dead on entry to and exit from basic blocks
474 (before register allocation).  Thus, if you need a value to be live across basic
475 block boundaries, it *must* live in a virtual register.
476
477 Call-clobbered registers
478 ^^^^^^^^^^^^^^^^^^^^^^^^
479
480 Some machine instructions, like calls, clobber a large number of physical
481 registers.  Rather than adding ``<def,dead>`` operands for all of them, it is
482 possible to use an ``MO_RegisterMask`` operand instead.  The register mask
483 operand holds a bit mask of preserved registers, and everything else is
484 considered to be clobbered by the instruction.
485
486 Machine code in SSA form
487 ^^^^^^^^^^^^^^^^^^^^^^^^
488
489 ``MachineInstr``'s are initially selected in SSA-form, and are maintained in
490 SSA-form until register allocation happens.  For the most part, this is
491 trivially simple since LLVM is already in SSA form; LLVM PHI nodes become
492 machine code PHI nodes, and virtual registers are only allowed to have a single
493 definition.
494
495 After register allocation, machine code is no longer in SSA-form because there
496 are no virtual registers left in the code.
497
498 .. _MachineBasicBlock:
499
500 The ``MachineBasicBlock`` class
501 -------------------------------
502
503 The ``MachineBasicBlock`` class contains a list of machine instructions
504 (:raw-html:`<tt>` `MachineInstr`_ :raw-html:`</tt>` instances).  It roughly
505 corresponds to the LLVM code input to the instruction selector, but there can be
506 a one-to-many mapping (i.e. one LLVM basic block can map to multiple machine
507 basic blocks). The ``MachineBasicBlock`` class has a "``getBasicBlock``" method,
508 which returns the LLVM basic block that it comes from.
509
510 .. _MachineFunction:
511
512 The ``MachineFunction`` class
513 -----------------------------
514
515 The ``MachineFunction`` class contains a list of machine basic blocks
516 (:raw-html:`<tt>` `MachineBasicBlock`_ :raw-html:`</tt>` instances).  It
517 corresponds one-to-one with the LLVM function input to the instruction selector.
518 In addition to a list of basic blocks, the ``MachineFunction`` contains a a
519 ``MachineConstantPool``, a ``MachineFrameInfo``, a ``MachineFunctionInfo``, and
520 a ``MachineRegisterInfo``.  See ``include/llvm/CodeGen/MachineFunction.h`` for
521 more information.
522
523 ``MachineInstr Bundles``
524 ------------------------
525
526 LLVM code generator can model sequences of instructions as MachineInstr
527 bundles. A MI bundle can model a VLIW group / pack which contains an arbitrary
528 number of parallel instructions. It can also be used to model a sequential list
529 of instructions (potentially with data dependencies) that cannot be legally
530 separated (e.g. ARM Thumb2 IT blocks).
531
532 Conceptually a MI bundle is a MI with a number of other MIs nested within:
533
534 ::
535
536   --------------
537   |   Bundle   | ---------
538   --------------          \
539          |           ----------------
540          |           |      MI      |
541          |           ----------------
542          |                   |
543          |           ----------------
544          |           |      MI      |
545          |           ----------------
546          |                   |
547          |           ----------------
548          |           |      MI      |
549          |           ----------------
550          |
551   --------------
552   |   Bundle   | --------
553   --------------         \
554          |           ----------------
555          |           |      MI      |
556          |           ----------------
557          |                   |
558          |           ----------------
559          |           |      MI      |
560          |           ----------------
561          |                   |
562          |                  ...
563          |
564   --------------
565   |   Bundle   | --------
566   --------------         \
567          |
568         ...
569
570 MI bundle support does not change the physical representations of
571 MachineBasicBlock and MachineInstr. All the MIs (including top level and nested
572 ones) are stored as sequential list of MIs. The "bundled" MIs are marked with
573 the 'InsideBundle' flag. A top level MI with the special BUNDLE opcode is used
574 to represent the start of a bundle. It's legal to mix BUNDLE MIs with indiviual
575 MIs that are not inside bundles nor represent bundles.
576
577 MachineInstr passes should operate on a MI bundle as a single unit. Member
578 methods have been taught to correctly handle bundles and MIs inside bundles.
579 The MachineBasicBlock iterator has been modified to skip over bundled MIs to
580 enforce the bundle-as-a-single-unit concept. An alternative iterator
581 instr_iterator has been added to MachineBasicBlock to allow passes to iterate
582 over all of the MIs in a MachineBasicBlock, including those which are nested
583 inside bundles. The top level BUNDLE instruction must have the correct set of
584 register MachineOperand's that represent the cumulative inputs and outputs of
585 the bundled MIs.
586
587 Packing / bundling of MachineInstr's should be done as part of the register
588 allocation super-pass. More specifically, the pass which determines what MIs
589 should be bundled together must be done after code generator exits SSA form
590 (i.e. after two-address pass, PHI elimination, and copy coalescing).  Bundles
591 should only be finalized (i.e. adding BUNDLE MIs and input and output register
592 MachineOperands) after virtual registers have been rewritten into physical
593 registers. This requirement eliminates the need to add virtual register operands
594 to BUNDLE instructions which would effectively double the virtual register def
595 and use lists.
596
597 .. _MC Layer:
598
599 The "MC" Layer
600 ==============
601
602 The MC Layer is used to represent and process code at the raw machine code
603 level, devoid of "high level" information like "constant pools", "jump tables",
604 "global variables" or anything like that.  At this level, LLVM handles things
605 like label names, machine instructions, and sections in the object file.  The
606 code in this layer is used for a number of important purposes: the tail end of
607 the code generator uses it to write a .s or .o file, and it is also used by the
608 llvm-mc tool to implement standalone machine code assemblers and disassemblers.
609
610 This section describes some of the important classes.  There are also a number
611 of important subsystems that interact at this layer, they are described later in
612 this manual.
613
614 .. _MCStreamer:
615
616 The ``MCStreamer`` API
617 ----------------------
618
619 MCStreamer is best thought of as an assembler API.  It is an abstract API which
620 is *implemented* in different ways (e.g. to output a .s file, output an ELF .o
621 file, etc) but whose API correspond directly to what you see in a .s file.
622 MCStreamer has one method per directive, such as EmitLabel, EmitSymbolAttribute,
623 SwitchSection, EmitValue (for .byte, .word), etc, which directly correspond to
624 assembly level directives.  It also has an EmitInstruction method, which is used
625 to output an MCInst to the streamer.
626
627 This API is most important for two clients: the llvm-mc stand-alone assembler is
628 effectively a parser that parses a line, then invokes a method on MCStreamer. In
629 the code generator, the `Code Emission`_ phase of the code generator lowers
630 higher level LLVM IR and Machine* constructs down to the MC layer, emitting
631 directives through MCStreamer.
632
633 On the implementation side of MCStreamer, there are two major implementations:
634 one for writing out a .s file (MCAsmStreamer), and one for writing out a .o
635 file (MCObjectStreamer).  MCAsmStreamer is a straight-forward implementation
636 that prints out a directive for each method (e.g. ``EmitValue -> .byte``), but
637 MCObjectStreamer implements a full assembler.
638
639 For target specific directives, the MCStreamer has a MCTargetStreamer instance.
640 Each target that needs it defines a class that inherits from it and is a lot
641 like MCStreamer itself: It has one method per directive and two classes that
642 inherit from it, a target object streamer and a target asm streamer. The target
643 asm streamer just prints it (``emitFnStart -> .fnstrart``), and the object
644 streamer implement the assembler logic for it.
645
646 To make llvm use these classes, the target initialization must call
647 TargetRegistry::RegisterAsmStreamer and TargetRegistry::RegisterMCObjectStreamer
648 passing callbacks that allocate the corresponding target streamer and pass it
649 to createAsmStreamer or to the appropriate object streamer constructor.
650
651 The ``MCContext`` class
652 -----------------------
653
654 The MCContext class is the owner of a variety of uniqued data structures at the
655 MC layer, including symbols, sections, etc.  As such, this is the class that you
656 interact with to create symbols and sections.  This class can not be subclassed.
657
658 The ``MCSymbol`` class
659 ----------------------
660
661 The MCSymbol class represents a symbol (aka label) in the assembly file.  There
662 are two interesting kinds of symbols: assembler temporary symbols, and normal
663 symbols.  Assembler temporary symbols are used and processed by the assembler
664 but are discarded when the object file is produced.  The distinction is usually
665 represented by adding a prefix to the label, for example "L" labels are
666 assembler temporary labels in MachO.
667
668 MCSymbols are created by MCContext and uniqued there.  This means that MCSymbols
669 can be compared for pointer equivalence to find out if they are the same symbol.
670 Note that pointer inequality does not guarantee the labels will end up at
671 different addresses though.  It's perfectly legal to output something like this
672 to the .s file:
673
674 ::
675
676   foo:
677   bar:
678     .byte 4
679
680 In this case, both the foo and bar symbols will have the same address.
681
682 The ``MCSection`` class
683 -----------------------
684
685 The ``MCSection`` class represents an object-file specific section. It is
686 subclassed by object file specific implementations (e.g. ``MCSectionMachO``,
687 ``MCSectionCOFF``, ``MCSectionELF``) and these are created and uniqued by
688 MCContext.  The MCStreamer has a notion of the current section, which can be
689 changed with the SwitchToSection method (which corresponds to a ".section"
690 directive in a .s file).
691
692 .. _MCInst:
693
694 The ``MCInst`` class
695 --------------------
696
697 The ``MCInst`` class is a target-independent representation of an instruction.
698 It is a simple class (much more so than `MachineInstr`_) that holds a
699 target-specific opcode and a vector of MCOperands.  MCOperand, in turn, is a
700 simple discriminated union of three cases: 1) a simple immediate, 2) a target
701 register ID, 3) a symbolic expression (e.g. "``Lfoo-Lbar+42``") as an MCExpr.
702
703 MCInst is the common currency used to represent machine instructions at the MC
704 layer.  It is the type used by the instruction encoder, the instruction printer,
705 and the type generated by the assembly parser and disassembler.
706
707 .. _Target-independent algorithms:
708 .. _code generation algorithm:
709
710 Target-independent code generation algorithms
711 =============================================
712
713 This section documents the phases described in the `high-level design of the
714 code generator`_.  It explains how they work and some of the rationale behind
715 their design.
716
717 .. _Instruction Selection:
718 .. _instruction selection section:
719
720 Instruction Selection
721 ---------------------
722
723 Instruction Selection is the process of translating LLVM code presented to the
724 code generator into target-specific machine instructions.  There are several
725 well-known ways to do this in the literature.  LLVM uses a SelectionDAG based
726 instruction selector.
727
728 Portions of the DAG instruction selector are generated from the target
729 description (``*.td``) files.  Our goal is for the entire instruction selector
730 to be generated from these ``.td`` files, though currently there are still
731 things that require custom C++ code.
732
733 .. _SelectionDAG:
734
735 Introduction to SelectionDAGs
736 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
737
738 The SelectionDAG provides an abstraction for code representation in a way that
739 is amenable to instruction selection using automatic techniques
740 (e.g. dynamic-programming based optimal pattern matching selectors). It is also
741 well-suited to other phases of code generation; in particular, instruction
742 scheduling (SelectionDAG's are very close to scheduling DAGs post-selection).
743 Additionally, the SelectionDAG provides a host representation where a large
744 variety of very-low-level (but target-independent) `optimizations`_ may be
745 performed; ones which require extensive information about the instructions
746 efficiently supported by the target.
747
748 The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
749 ``SDNode`` class.  The primary payload of the ``SDNode`` is its operation code
750 (Opcode) that indicates what operation the node performs and the operands to the
751 operation.  The various operation node types are described at the top of the
752 ``include/llvm/CodeGen/SelectionDAGNodes.h`` file.
753
754 Although most operations define a single value, each node in the graph may
755 define multiple values.  For example, a combined div/rem operation will define
756 both the dividend and the remainder. Many other situations require multiple
757 values as well.  Each node also has some number of operands, which are edges to
758 the node defining the used value.  Because nodes may define multiple values,
759 edges are represented by instances of the ``SDValue`` class, which is a
760 ``<SDNode, unsigned>`` pair, indicating the node and result value being used,
761 respectively.  Each value produced by an ``SDNode`` has an associated ``MVT``
762 (Machine Value Type) indicating what the type of the value is.
763
764 SelectionDAGs contain two different kinds of values: those that represent data
765 flow and those that represent control flow dependencies.  Data values are simple
766 edges with an integer or floating point value type.  Control edges are
767 represented as "chain" edges which are of type ``MVT::Other``.  These edges
768 provide an ordering between nodes that have side effects (such as loads, stores,
769 calls, returns, etc).  All nodes that have side effects should take a token
770 chain as input and produce a new one as output.  By convention, token chain
771 inputs are always operand #0, and chain results are always the last value
772 produced by an operation.
773
774 A SelectionDAG has designated "Entry" and "Root" nodes.  The Entry node is
775 always a marker node with an Opcode of ``ISD::EntryToken``.  The Root node is
776 the final side-effecting node in the token chain. For example, in a single basic
777 block function it would be the return node.
778
779 One important concept for SelectionDAGs is the notion of a "legal" vs.
780 "illegal" DAG.  A legal DAG for a target is one that only uses supported
781 operations and supported types.  On a 32-bit PowerPC, for example, a DAG with a
782 value of type i1, i8, i16, or i64 would be illegal, as would a DAG that uses a
783 SREM or UREM operation.  The `legalize types`_ and `legalize operations`_ phases
784 are responsible for turning an illegal DAG into a legal DAG.
785
786 .. _SelectionDAG-Process:
787
788 SelectionDAG Instruction Selection Process
789 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
790
791 SelectionDAG-based instruction selection consists of the following steps:
792
793 #. `Build initial DAG`_ --- This stage performs a simple translation from the
794    input LLVM code to an illegal SelectionDAG.
795
796 #. `Optimize SelectionDAG`_ --- This stage performs simple optimizations on the
797    SelectionDAG to simplify it, and recognize meta instructions (like rotates
798    and ``div``/``rem`` pairs) for targets that support these meta operations.
799    This makes the resultant code more efficient and the `select instructions
800    from DAG`_ phase (below) simpler.
801
802 #. `Legalize SelectionDAG Types`_ --- This stage transforms SelectionDAG nodes
803    to eliminate any types that are unsupported on the target.
804
805 #. `Optimize SelectionDAG`_ --- The SelectionDAG optimizer is run to clean up
806    redundancies exposed by type legalization.
807
808 #. `Legalize SelectionDAG Ops`_ --- This stage transforms SelectionDAG nodes to
809    eliminate any operations that are unsupported on the target.
810
811 #. `Optimize SelectionDAG`_ --- The SelectionDAG optimizer is run to eliminate
812    inefficiencies introduced by operation legalization.
813
814 #. `Select instructions from DAG`_ --- Finally, the target instruction selector
815    matches the DAG operations to target instructions.  This process translates
816    the target-independent input DAG into another DAG of target instructions.
817
818 #. `SelectionDAG Scheduling and Formation`_ --- The last phase assigns a linear
819    order to the instructions in the target-instruction DAG and emits them into
820    the MachineFunction being compiled.  This step uses traditional prepass
821    scheduling techniques.
822
823 After all of these steps are complete, the SelectionDAG is destroyed and the
824 rest of the code generation passes are run.
825
826 One great way to visualize what is going on here is to take advantage of a few
827 LLC command line options.  The following options pop up a window displaying the
828 SelectionDAG at specific times (if you only get errors printed to the console
829 while using this, you probably `need to configure your
830 system <ProgrammersManual.html#ViewGraph>`_ to add support for it).
831
832 * ``-view-dag-combine1-dags`` displays the DAG after being built, before the
833   first optimization pass.
834
835 * ``-view-legalize-dags`` displays the DAG before Legalization.
836
837 * ``-view-dag-combine2-dags`` displays the DAG before the second optimization
838   pass.
839
840 * ``-view-isel-dags`` displays the DAG before the Select phase.
841
842 * ``-view-sched-dags`` displays the DAG before Scheduling.
843
844 The ``-view-sunit-dags`` displays the Scheduler's dependency graph.  This graph
845 is based on the final SelectionDAG, with nodes that must be scheduled together
846 bundled into a single scheduling-unit node, and with immediate operands and
847 other nodes that aren't relevant for scheduling omitted.
848
849 .. _Build initial DAG:
850
851 Initial SelectionDAG Construction
852 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
853
854 The initial SelectionDAG is na\ :raw-html:`&iuml;`\ vely peephole expanded from
855 the LLVM input by the ``SelectionDAGBuilder`` class.  The intent of this pass
856 is to expose as much low-level, target-specific details to the SelectionDAG as
857 possible.  This pass is mostly hard-coded (e.g. an LLVM ``add`` turns into an
858 ``SDNode add`` while a ``getelementptr`` is expanded into the obvious
859 arithmetic). This pass requires target-specific hooks to lower calls, returns,
860 varargs, etc.  For these features, the :raw-html:`<tt>` `TargetLowering`_
861 :raw-html:`</tt>` interface is used.
862
863 .. _legalize types:
864 .. _Legalize SelectionDAG Types:
865 .. _Legalize SelectionDAG Ops:
866
867 SelectionDAG LegalizeTypes Phase
868 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
869
870 The Legalize phase is in charge of converting a DAG to only use the types that
871 are natively supported by the target.
872
873 There are two main ways of converting values of unsupported scalar types to
874 values of supported types: converting small types to larger types ("promoting"),
875 and breaking up large integer types into smaller ones ("expanding").  For
876 example, a target might require that all f32 values are promoted to f64 and that
877 all i1/i8/i16 values are promoted to i32.  The same target might require that
878 all i64 values be expanded into pairs of i32 values.  These changes can insert
879 sign and zero extensions as needed to make sure that the final code has the same
880 behavior as the input.
881
882 There are two main ways of converting values of unsupported vector types to
883 value of supported types: splitting vector types, multiple times if necessary,
884 until a legal type is found, and extending vector types by adding elements to
885 the end to round them out to legal types ("widening").  If a vector gets split
886 all the way down to single-element parts with no supported vector type being
887 found, the elements are converted to scalars ("scalarizing").
888
889 A target implementation tells the legalizer which types are supported (and which
890 register class to use for them) by calling the ``addRegisterClass`` method in
891 its ``TargetLowering`` constructor.
892
893 .. _legalize operations:
894 .. _Legalizer:
895
896 SelectionDAG Legalize Phase
897 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
898
899 The Legalize phase is in charge of converting a DAG to only use the operations
900 that are natively supported by the target.
901
902 Targets often have weird constraints, such as not supporting every operation on
903 every supported datatype (e.g. X86 does not support byte conditional moves and
904 PowerPC does not support sign-extending loads from a 16-bit memory location).
905 Legalize takes care of this by open-coding another sequence of operations to
906 emulate the operation ("expansion"), by promoting one type to a larger type that
907 supports the operation ("promotion"), or by using a target-specific hook to
908 implement the legalization ("custom").
909
910 A target implementation tells the legalizer which operations are not supported
911 (and which of the above three actions to take) by calling the
912 ``setOperationAction`` method in its ``TargetLowering`` constructor.
913
914 Prior to the existence of the Legalize passes, we required that every target
915 `selector`_ supported and handled every operator and type even if they are not
916 natively supported.  The introduction of the Legalize phases allows all of the
917 canonicalization patterns to be shared across targets, and makes it very easy to
918 optimize the canonicalized code because it is still in the form of a DAG.
919
920 .. _optimizations:
921 .. _Optimize SelectionDAG:
922 .. _selector:
923
924 SelectionDAG Optimization Phase: the DAG Combiner
925 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
926
927 The SelectionDAG optimization phase is run multiple times for code generation,
928 immediately after the DAG is built and once after each legalization.  The first
929 run of the pass allows the initial code to be cleaned up (e.g. performing
930 optimizations that depend on knowing that the operators have restricted type
931 inputs).  Subsequent runs of the pass clean up the messy code generated by the
932 Legalize passes, which allows Legalize to be very simple (it can focus on making
933 code legal instead of focusing on generating *good* and legal code).
934
935 One important class of optimizations performed is optimizing inserted sign and
936 zero extension instructions.  We currently use ad-hoc techniques, but could move
937 to more rigorous techniques in the future.  Here are some good papers on the
938 subject:
939
940 "`Widening integer arithmetic <http://www.eecs.harvard.edu/~nr/pubs/widen-abstract.html>`_" :raw-html:`<br>`
941 Kevin Redwine and Norman Ramsey :raw-html:`<br>`
942 International Conference on Compiler Construction (CC) 2004
943
944 "`Effective sign extension elimination <http://portal.acm.org/citation.cfm?doid=512529.512552>`_"  :raw-html:`<br>`
945 Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani :raw-html:`<br>`
946 Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
947 and Implementation.
948
949 .. _Select instructions from DAG:
950
951 SelectionDAG Select Phase
952 ^^^^^^^^^^^^^^^^^^^^^^^^^
953
954 The Select phase is the bulk of the target-specific code for instruction
955 selection.  This phase takes a legal SelectionDAG as input, pattern matches the
956 instructions supported by the target to this DAG, and produces a new DAG of
957 target code.  For example, consider the following LLVM fragment:
958
959 .. code-block:: llvm
960
961   %t1 = fadd float %W, %X
962   %t2 = fmul float %t1, %Y
963   %t3 = fadd float %t2, %Z
964
965 This LLVM code corresponds to a SelectionDAG that looks basically like this:
966
967 .. code-block:: llvm
968
969   (fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
970
971 If a target supports floating point multiply-and-add (FMA) operations, one of
972 the adds can be merged with the multiply.  On the PowerPC, for example, the
973 output of the instruction selector might look like this DAG:
974
975 ::
976
977   (FMADDS (FADDS W, X), Y, Z)
978
979 The ``FMADDS`` instruction is a ternary instruction that multiplies its first
980 two operands and adds the third (as single-precision floating-point numbers).
981 The ``FADDS`` instruction is a simple binary single-precision add instruction.
982 To perform this pattern match, the PowerPC backend includes the following
983 instruction definitions:
984
985 .. code-block:: text
986   :emphasize-lines: 4-5,9
987
988   def FMADDS : AForm_1<59, 29,
989                       (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
990                       "fmadds $FRT, $FRA, $FRC, $FRB",
991                       [(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),
992                                              F4RC:$FRB))]>;
993   def FADDS : AForm_2<59, 21,
994                       (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),
995                       "fadds $FRT, $FRA, $FRB",
996                       [(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))]>;
997
998 The highlighted portion of the instruction definitions indicates the pattern
999 used to match the instructions. The DAG operators (like ``fmul``/``fadd``)
1000 are defined in the ``include/llvm/Target/TargetSelectionDAG.td`` file.
1001 "``F4RC``" is the register class of the input and result values.
1002
1003 The TableGen DAG instruction selector generator reads the instruction patterns
1004 in the ``.td`` file and automatically builds parts of the pattern matching code
1005 for your target.  It has the following strengths:
1006
1007 * At compiler-compiler time, it analyzes your instruction patterns and tells you
1008   if your patterns make sense or not.
1009
1010 * It can handle arbitrary constraints on operands for the pattern match.  In
1011   particular, it is straight-forward to say things like "match any immediate
1012   that is a 13-bit sign-extended value".  For examples, see the ``immSExt16``
1013   and related ``tblgen`` classes in the PowerPC backend.
1014
1015 * It knows several important identities for the patterns defined.  For example,
1016   it knows that addition is commutative, so it allows the ``FMADDS`` pattern
1017   above to match "``(fadd X, (fmul Y, Z))``" as well as "``(fadd (fmul X, Y),
1018   Z)``", without the target author having to specially handle this case.
1019
1020 * It has a full-featured type-inferencing system.  In particular, you should
1021   rarely have to explicitly tell the system what type parts of your patterns
1022   are.  In the ``FMADDS`` case above, we didn't have to tell ``tblgen`` that all
1023   of the nodes in the pattern are of type 'f32'.  It was able to infer and
1024   propagate this knowledge from the fact that ``F4RC`` has type 'f32'.
1025
1026 * Targets can define their own (and rely on built-in) "pattern fragments".
1027   Pattern fragments are chunks of reusable patterns that get inlined into your
1028   patterns during compiler-compiler time.  For example, the integer "``(not
1029   x)``" operation is actually defined as a pattern fragment that expands as
1030   "``(xor x, -1)``", since the SelectionDAG does not have a native '``not``'
1031   operation.  Targets can define their own short-hand fragments as they see fit.
1032   See the definition of '``not``' and '``ineg``' for examples.
1033
1034 * In addition to instructions, targets can specify arbitrary patterns that map
1035   to one or more instructions using the 'Pat' class.  For example, the PowerPC
1036   has no way to load an arbitrary integer immediate into a register in one
1037   instruction. To tell tblgen how to do this, it defines:
1038
1039   ::
1040
1041     // Arbitrary immediate support.  Implement in terms of LIS/ORI.
1042     def : Pat<(i32 imm:$imm),
1043               (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;
1044
1045   If none of the single-instruction patterns for loading an immediate into a
1046   register match, this will be used.  This rule says "match an arbitrary i32
1047   immediate, turning it into an ``ORI`` ('or a 16-bit immediate') and an ``LIS``
1048   ('load 16-bit immediate, where the immediate is shifted to the left 16 bits')
1049   instruction".  To make this work, the ``LO16``/``HI16`` node transformations
1050   are used to manipulate the input immediate (in this case, take the high or low
1051   16-bits of the immediate).
1052
1053 * When using the 'Pat' class to map a pattern to an instruction that has one
1054   or more complex operands (like e.g. `X86 addressing mode`_), the pattern may
1055   either specify the operand as a whole using a ``ComplexPattern``, or else it
1056   may specify the components of the complex operand separately.  The latter is
1057   done e.g. for pre-increment instructions by the PowerPC back end:
1058
1059   ::
1060
1061     def STWU  : DForm_1<37, (outs ptr_rc:$ea_res), (ins GPRC:$rS, memri:$dst),
1062                     "stwu $rS, $dst", LdStStoreUpd, []>,
1063                     RegConstraint<"$dst.reg = $ea_res">, NoEncode<"$ea_res">;
1064
1065     def : Pat<(pre_store GPRC:$rS, ptr_rc:$ptrreg, iaddroff:$ptroff),
1066               (STWU GPRC:$rS, iaddroff:$ptroff, ptr_rc:$ptrreg)>;
1067
1068   Here, the pair of ``ptroff`` and ``ptrreg`` operands is matched onto the
1069   complex operand ``dst`` of class ``memri`` in the ``STWU`` instruction.
1070
1071 * While the system does automate a lot, it still allows you to write custom C++
1072   code to match special cases if there is something that is hard to
1073   express.
1074
1075 While it has many strengths, the system currently has some limitations,
1076 primarily because it is a work in progress and is not yet finished:
1077
1078 * Overall, there is no way to define or match SelectionDAG nodes that define
1079   multiple values (e.g. ``SMUL_LOHI``, ``LOAD``, ``CALL``, etc).  This is the
1080   biggest reason that you currently still *have to* write custom C++ code
1081   for your instruction selector.
1082
1083 * There is no great way to support matching complex addressing modes yet.  In
1084   the future, we will extend pattern fragments to allow them to define multiple
1085   values (e.g. the four operands of the `X86 addressing mode`_, which are
1086   currently matched with custom C++ code).  In addition, we'll extend fragments
1087   so that a fragment can match multiple different patterns.
1088
1089 * We don't automatically infer flags like ``isStore``/``isLoad`` yet.
1090
1091 * We don't automatically generate the set of supported registers and operations
1092   for the `Legalizer`_ yet.
1093
1094 * We don't have a way of tying in custom legalized nodes yet.
1095
1096 Despite these limitations, the instruction selector generator is still quite
1097 useful for most of the binary and logical operations in typical instruction
1098 sets.  If you run into any problems or can't figure out how to do something,
1099 please let Chris know!
1100
1101 .. _Scheduling and Formation:
1102 .. _SelectionDAG Scheduling and Formation:
1103
1104 SelectionDAG Scheduling and Formation Phase
1105 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1106
1107 The scheduling phase takes the DAG of target instructions from the selection
1108 phase and assigns an order.  The scheduler can pick an order depending on
1109 various constraints of the machines (i.e. order for minimal register pressure or
1110 try to cover instruction latencies).  Once an order is established, the DAG is
1111 converted to a list of :raw-html:`<tt>` `MachineInstr`_\s :raw-html:`</tt>` and
1112 the SelectionDAG is destroyed.
1113
1114 Note that this phase is logically separate from the instruction selection phase,
1115 but is tied to it closely in the code because it operates on SelectionDAGs.
1116
1117 Future directions for the SelectionDAG
1118 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1119
1120 #. Optional function-at-a-time selection.
1121
1122 #. Auto-generate entire selector from ``.td`` file.
1123
1124 .. _SSA-based Machine Code Optimizations:
1125
1126 SSA-based Machine Code Optimizations
1127 ------------------------------------
1128
1129 To Be Written
1130
1131 Live Intervals
1132 --------------
1133
1134 Live Intervals are the ranges (intervals) where a variable is *live*.  They are
1135 used by some `register allocator`_ passes to determine if two or more virtual
1136 registers which require the same physical register are live at the same point in
1137 the program (i.e., they conflict).  When this situation occurs, one virtual
1138 register must be *spilled*.
1139
1140 Live Variable Analysis
1141 ^^^^^^^^^^^^^^^^^^^^^^
1142
1143 The first step in determining the live intervals of variables is to calculate
1144 the set of registers that are immediately dead after the instruction (i.e., the
1145 instruction calculates the value, but it is never used) and the set of registers
1146 that are used by the instruction, but are never used after the instruction
1147 (i.e., they are killed). Live variable information is computed for
1148 each *virtual* register and *register allocatable* physical register
1149 in the function.  This is done in a very efficient manner because it uses SSA to
1150 sparsely compute lifetime information for virtual registers (which are in SSA
1151 form) and only has to track physical registers within a block.  Before register
1152 allocation, LLVM can assume that physical registers are only live within a
1153 single basic block.  This allows it to do a single, local analysis to resolve
1154 physical register lifetimes within each basic block. If a physical register is
1155 not register allocatable (e.g., a stack pointer or condition codes), it is not
1156 tracked.
1157
1158 Physical registers may be live in to or out of a function. Live in values are
1159 typically arguments in registers. Live out values are typically return values in
1160 registers. Live in values are marked as such, and are given a dummy "defining"
1161 instruction during live intervals analysis. If the last basic block of a
1162 function is a ``return``, then it's marked as using all live out values in the
1163 function.
1164
1165 ``PHI`` nodes need to be handled specially, because the calculation of the live
1166 variable information from a depth first traversal of the CFG of the function
1167 won't guarantee that a virtual register used by the ``PHI`` node is defined
1168 before it's used. When a ``PHI`` node is encountered, only the definition is
1169 handled, because the uses will be handled in other basic blocks.
1170
1171 For each ``PHI`` node of the current basic block, we simulate an assignment at
1172 the end of the current basic block and traverse the successor basic blocks. If a
1173 successor basic block has a ``PHI`` node and one of the ``PHI`` node's operands
1174 is coming from the current basic block, then the variable is marked as *alive*
1175 within the current basic block and all of its predecessor basic blocks, until
1176 the basic block with the defining instruction is encountered.
1177
1178 Live Intervals Analysis
1179 ^^^^^^^^^^^^^^^^^^^^^^^
1180
1181 We now have the information available to perform the live intervals analysis and
1182 build the live intervals themselves.  We start off by numbering the basic blocks
1183 and machine instructions.  We then handle the "live-in" values.  These are in
1184 physical registers, so the physical register is assumed to be killed by the end
1185 of the basic block.  Live intervals for virtual registers are computed for some
1186 ordering of the machine instructions ``[1, N]``.  A live interval is an interval
1187 ``[i, j)``, where ``1 >= i >= j > N``, for which a variable is live.
1188
1189 .. note::
1190   More to come...
1191
1192 .. _Register Allocation:
1193 .. _register allocator:
1194
1195 Register Allocation
1196 -------------------
1197
1198 The *Register Allocation problem* consists in mapping a program
1199 :raw-html:`<b><tt>` P\ :sub:`v`\ :raw-html:`</tt></b>`, that can use an unbounded
1200 number of virtual registers, to a program :raw-html:`<b><tt>` P\ :sub:`p`\
1201 :raw-html:`</tt></b>` that contains a finite (possibly small) number of physical
1202 registers. Each target architecture has a different number of physical
1203 registers. If the number of physical registers is not enough to accommodate all
1204 the virtual registers, some of them will have to be mapped into memory. These
1205 virtuals are called *spilled virtuals*.
1206
1207 How registers are represented in LLVM
1208 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1209
1210 In LLVM, physical registers are denoted by integer numbers that normally range
1211 from 1 to 1023. To see how this numbering is defined for a particular
1212 architecture, you can read the ``GenRegisterNames.inc`` file for that
1213 architecture. For instance, by inspecting
1214 ``lib/Target/X86/X86GenRegisterInfo.inc`` we see that the 32-bit register
1215 ``EAX`` is denoted by 43, and the MMX register ``MM0`` is mapped to 65.
1216
1217 Some architectures contain registers that share the same physical location. A
1218 notable example is the X86 platform. For instance, in the X86 architecture, the
1219 registers ``EAX``, ``AX`` and ``AL`` share the first eight bits. These physical
1220 registers are marked as *aliased* in LLVM. Given a particular architecture, you
1221 can check which registers are aliased by inspecting its ``RegisterInfo.td``
1222 file. Moreover, the class ``MCRegAliasIterator`` enumerates all the physical
1223 registers aliased to a register.
1224
1225 Physical registers, in LLVM, are grouped in *Register Classes*.  Elements in the
1226 same register class are functionally equivalent, and can be interchangeably
1227 used. Each virtual register can only be mapped to physical registers of a
1228 particular class. For instance, in the X86 architecture, some virtuals can only
1229 be allocated to 8 bit registers.  A register class is described by
1230 ``TargetRegisterClass`` objects.  To discover if a virtual register is
1231 compatible with a given physical, this code can be used:</p>
1232
1233 .. code-block:: c++
1234
1235   bool RegMapping_Fer::compatible_class(MachineFunction &mf,
1236                                         unsigned v_reg,
1237                                         unsigned p_reg) {
1238     assert(TargetRegisterInfo::isPhysicalRegister(p_reg) &&
1239            "Target register must be physical");
1240     const TargetRegisterClass *trc = mf.getRegInfo().getRegClass(v_reg);
1241     return trc->contains(p_reg);
1242   }
1243
1244 Sometimes, mostly for debugging purposes, it is useful to change the number of
1245 physical registers available in the target architecture. This must be done
1246 statically, inside the ``TargetRegsterInfo.td`` file. Just ``grep`` for
1247 ``RegisterClass``, the last parameter of which is a list of registers. Just
1248 commenting some out is one simple way to avoid them being used. A more polite
1249 way is to explicitly exclude some registers from the *allocation order*. See the
1250 definition of the ``GR8`` register class in
1251 ``lib/Target/X86/X86RegisterInfo.td`` for an example of this.
1252
1253 Virtual registers are also denoted by integer numbers. Contrary to physical
1254 registers, different virtual registers never share the same number. Whereas
1255 physical registers are statically defined in a ``TargetRegisterInfo.td`` file
1256 and cannot be created by the application developer, that is not the case with
1257 virtual registers. In order to create new virtual registers, use the method
1258 ``MachineRegisterInfo::createVirtualRegister()``. This method will return a new
1259 virtual register. Use an ``IndexedMap<Foo, VirtReg2IndexFunctor>`` to hold
1260 information per virtual register. If you need to enumerate all virtual
1261 registers, use the function ``TargetRegisterInfo::index2VirtReg()`` to find the
1262 virtual register numbers:
1263
1264 .. code-block:: c++
1265
1266     for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
1267       unsigned VirtReg = TargetRegisterInfo::index2VirtReg(i);
1268       stuff(VirtReg);
1269     }
1270
1271 Before register allocation, the operands of an instruction are mostly virtual
1272 registers, although physical registers may also be used. In order to check if a
1273 given machine operand is a register, use the boolean function
1274 ``MachineOperand::isRegister()``. To obtain the integer code of a register, use
1275 ``MachineOperand::getReg()``. An instruction may define or use a register. For
1276 instance, ``ADD reg:1026 := reg:1025 reg:1024`` defines the registers 1024, and
1277 uses registers 1025 and 1026. Given a register operand, the method
1278 ``MachineOperand::isUse()`` informs if that register is being used by the
1279 instruction. The method ``MachineOperand::isDef()`` informs if that registers is
1280 being defined.
1281
1282 We will call physical registers present in the LLVM bitcode before register
1283 allocation *pre-colored registers*. Pre-colored registers are used in many
1284 different situations, for instance, to pass parameters of functions calls, and
1285 to store results of particular instructions. There are two types of pre-colored
1286 registers: the ones *implicitly* defined, and those *explicitly*
1287 defined. Explicitly defined registers are normal operands, and can be accessed
1288 with ``MachineInstr::getOperand(int)::getReg()``.  In order to check which
1289 registers are implicitly defined by an instruction, use the
1290 ``TargetInstrInfo::get(opcode)::ImplicitDefs``, where ``opcode`` is the opcode
1291 of the target instruction. One important difference between explicit and
1292 implicit physical registers is that the latter are defined statically for each
1293 instruction, whereas the former may vary depending on the program being
1294 compiled. For example, an instruction that represents a function call will
1295 always implicitly define or use the same set of physical registers. To read the
1296 registers implicitly used by an instruction, use
1297 ``TargetInstrInfo::get(opcode)::ImplicitUses``. Pre-colored registers impose
1298 constraints on any register allocation algorithm. The register allocator must
1299 make sure that none of them are overwritten by the values of virtual registers
1300 while still alive.
1301
1302 Mapping virtual registers to physical registers
1303 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1304
1305 There are two ways to map virtual registers to physical registers (or to memory
1306 slots). The first way, that we will call *direct mapping*, is based on the use
1307 of methods of the classes ``TargetRegisterInfo``, and ``MachineOperand``. The
1308 second way, that we will call *indirect mapping*, relies on the ``VirtRegMap``
1309 class in order to insert loads and stores sending and getting values to and from
1310 memory.
1311
1312 The direct mapping provides more flexibility to the developer of the register
1313 allocator; however, it is more error prone, and demands more implementation
1314 work.  Basically, the programmer will have to specify where load and store
1315 instructions should be inserted in the target function being compiled in order
1316 to get and store values in memory. To assign a physical register to a virtual
1317 register present in a given operand, use ``MachineOperand::setReg(p_reg)``. To
1318 insert a store instruction, use ``TargetInstrInfo::storeRegToStackSlot(...)``,
1319 and to insert a load instruction, use ``TargetInstrInfo::loadRegFromStackSlot``.
1320
1321 The indirect mapping shields the application developer from the complexities of
1322 inserting load and store instructions. In order to map a virtual register to a
1323 physical one, use ``VirtRegMap::assignVirt2Phys(vreg, preg)``.  In order to map
1324 a certain virtual register to memory, use
1325 ``VirtRegMap::assignVirt2StackSlot(vreg)``. This method will return the stack
1326 slot where ``vreg``'s value will be located.  If it is necessary to map another
1327 virtual register to the same stack slot, use
1328 ``VirtRegMap::assignVirt2StackSlot(vreg, stack_location)``. One important point
1329 to consider when using the indirect mapping, is that even if a virtual register
1330 is mapped to memory, it still needs to be mapped to a physical register. This
1331 physical register is the location where the virtual register is supposed to be
1332 found before being stored or after being reloaded.
1333
1334 If the indirect strategy is used, after all the virtual registers have been
1335 mapped to physical registers or stack slots, it is necessary to use a spiller
1336 object to place load and store instructions in the code. Every virtual that has
1337 been mapped to a stack slot will be stored to memory after been defined and will
1338 be loaded before being used. The implementation of the spiller tries to recycle
1339 load/store instructions, avoiding unnecessary instructions. For an example of
1340 how to invoke the spiller, see ``RegAllocLinearScan::runOnMachineFunction`` in
1341 ``lib/CodeGen/RegAllocLinearScan.cpp``.
1342
1343 Handling two address instructions
1344 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1345
1346 With very rare exceptions (e.g., function calls), the LLVM machine code
1347 instructions are three address instructions. That is, each instruction is
1348 expected to define at most one register, and to use at most two registers.
1349 However, some architectures use two address instructions. In this case, the
1350 defined register is also one of the used register. For instance, an instruction
1351 such as ``ADD %EAX, %EBX``, in X86 is actually equivalent to ``%EAX = %EAX +
1352 %EBX``.
1353
1354 In order to produce correct code, LLVM must convert three address instructions
1355 that represent two address instructions into true two address instructions. LLVM
1356 provides the pass ``TwoAddressInstructionPass`` for this specific purpose. It
1357 must be run before register allocation takes place. After its execution, the
1358 resulting code may no longer be in SSA form. This happens, for instance, in
1359 situations where an instruction such as ``%a = ADD %b %c`` is converted to two
1360 instructions such as:
1361
1362 ::
1363
1364   %a = MOVE %b
1365   %a = ADD %a %c
1366
1367 Notice that, internally, the second instruction is represented as ``ADD
1368 %a[def/use] %c``. I.e., the register operand ``%a`` is both used and defined by
1369 the instruction.
1370
1371 The SSA deconstruction phase
1372 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1373
1374 An important transformation that happens during register allocation is called
1375 the *SSA Deconstruction Phase*. The SSA form simplifies many analyses that are
1376 performed on the control flow graph of programs. However, traditional
1377 instruction sets do not implement PHI instructions. Thus, in order to generate
1378 executable code, compilers must replace PHI instructions with other instructions
1379 that preserve their semantics.
1380
1381 There are many ways in which PHI instructions can safely be removed from the
1382 target code. The most traditional PHI deconstruction algorithm replaces PHI
1383 instructions with copy instructions. That is the strategy adopted by LLVM. The
1384 SSA deconstruction algorithm is implemented in
1385 ``lib/CodeGen/PHIElimination.cpp``. In order to invoke this pass, the identifier
1386 ``PHIEliminationID`` must be marked as required in the code of the register
1387 allocator.
1388
1389 Instruction folding
1390 ^^^^^^^^^^^^^^^^^^^
1391
1392 *Instruction folding* is an optimization performed during register allocation
1393 that removes unnecessary copy instructions. For instance, a sequence of
1394 instructions such as:
1395
1396 ::
1397
1398   %EBX = LOAD %mem_address
1399   %EAX = COPY %EBX
1400
1401 can be safely substituted by the single instruction:
1402
1403 ::
1404
1405   %EAX = LOAD %mem_address
1406
1407 Instructions can be folded with the
1408 ``TargetRegisterInfo::foldMemoryOperand(...)`` method. Care must be taken when
1409 folding instructions; a folded instruction can be quite different from the
1410 original instruction. See ``LiveIntervals::addIntervalsForSpills`` in
1411 ``lib/CodeGen/LiveIntervalAnalysis.cpp`` for an example of its use.
1412
1413 Built in register allocators
1414 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1415
1416 The LLVM infrastructure provides the application developer with three different
1417 register allocators:
1418
1419 * *Fast* --- This register allocator is the default for debug builds. It
1420   allocates registers on a basic block level, attempting to keep values in
1421   registers and reusing registers as appropriate.
1422
1423 * *Basic* --- This is an incremental approach to register allocation. Live
1424   ranges are assigned to registers one at a time in an order that is driven by
1425   heuristics. Since code can be rewritten on-the-fly during allocation, this
1426   framework allows interesting allocators to be developed as extensions. It is
1427   not itself a production register allocator but is a potentially useful
1428   stand-alone mode for triaging bugs and as a performance baseline.
1429
1430 * *Greedy* --- *The default allocator*. This is a highly tuned implementation of
1431   the *Basic* allocator that incorporates global live range splitting. This
1432   allocator works hard to minimize the cost of spill code.
1433
1434 * *PBQP* --- A Partitioned Boolean Quadratic Programming (PBQP) based register
1435   allocator. This allocator works by constructing a PBQP problem representing
1436   the register allocation problem under consideration, solving this using a PBQP
1437   solver, and mapping the solution back to a register assignment.
1438
1439 The type of register allocator used in ``llc`` can be chosen with the command
1440 line option ``-regalloc=...``:
1441
1442 .. code-block:: bash
1443
1444   $ llc -regalloc=linearscan file.bc -o ln.s
1445   $ llc -regalloc=fast file.bc -o fa.s
1446   $ llc -regalloc=pbqp file.bc -o pbqp.s
1447
1448 .. _Prolog/Epilog Code Insertion:
1449
1450 Prolog/Epilog Code Insertion
1451 ----------------------------
1452
1453 Compact Unwind
1454
1455 Throwing an exception requires *unwinding* out of a function. The information on
1456 how to unwind a given function is traditionally expressed in DWARF unwind
1457 (a.k.a. frame) info. But that format was originally developed for debuggers to
1458 backtrace, and each Frame Description Entry (FDE) requires ~20-30 bytes per
1459 function. There is also the cost of mapping from an address in a function to the
1460 corresponding FDE at runtime. An alternative unwind encoding is called *compact
1461 unwind* and requires just 4-bytes per function.
1462
1463 The compact unwind encoding is a 32-bit value, which is encoded in an
1464 architecture-specific way. It specifies which registers to restore and from
1465 where, and how to unwind out of the function. When the linker creates a final
1466 linked image, it will create a ``__TEXT,__unwind_info`` section. This section is
1467 a small and fast way for the runtime to access unwind info for any given
1468 function. If we emit compact unwind info for the function, that compact unwind
1469 info will be encoded in the ``__TEXT,__unwind_info`` section. If we emit DWARF
1470 unwind info, the ``__TEXT,__unwind_info`` section will contain the offset of the
1471 FDE in the ``__TEXT,__eh_frame`` section in the final linked image.
1472
1473 For X86, there are three modes for the compact unwind encoding:
1474
1475 *Function with a Frame Pointer (``EBP`` or ``RBP``)*
1476   ``EBP/RBP``-based frame, where ``EBP/RBP`` is pushed onto the stack
1477   immediately after the return address, then ``ESP/RSP`` is moved to
1478   ``EBP/RBP``. Thus to unwind, ``ESP/RSP`` is restored with the current
1479   ``EBP/RBP`` value, then ``EBP/RBP`` is restored by popping the stack, and the
1480   return is done by popping the stack once more into the PC. All non-volatile
1481   registers that need to be restored must have been saved in a small range on
1482   the stack that starts ``EBP-4`` to ``EBP-1020`` (``RBP-8`` to
1483   ``RBP-1020``). The offset (divided by 4 in 32-bit mode and 8 in 64-bit mode)
1484   is encoded in bits 16-23 (mask: ``0x00FF0000``).  The registers saved are
1485   encoded in bits 0-14 (mask: ``0x00007FFF``) as five 3-bit entries from the
1486   following table:
1487
1488     ==============  =============  ===============
1489     Compact Number  i386 Register  x86-64 Register
1490     ==============  =============  ===============
1491     1               ``EBX``        ``RBX``
1492     2               ``ECX``        ``R12``
1493     3               ``EDX``        ``R13``
1494     4               ``EDI``        ``R14``
1495     5               ``ESI``        ``R15``
1496     6               ``EBP``        ``RBP``
1497     ==============  =============  ===============
1498
1499 *Frameless with a Small Constant Stack Size (``EBP`` or ``RBP`` is not used as a frame pointer)*
1500   To return, a constant (encoded in the compact unwind encoding) is added to the
1501   ``ESP/RSP``.  Then the return is done by popping the stack into the PC. All
1502   non-volatile registers that need to be restored must have been saved on the
1503   stack immediately after the return address. The stack size (divided by 4 in
1504   32-bit mode and 8 in 64-bit mode) is encoded in bits 16-23 (mask:
1505   ``0x00FF0000``). There is a maximum stack size of 1024 bytes in 32-bit mode
1506   and 2048 in 64-bit mode. The number of registers saved is encoded in bits 9-12
1507   (mask: ``0x00001C00``). Bits 0-9 (mask: ``0x000003FF``) contain which
1508   registers were saved and their order. (See the
1509   ``encodeCompactUnwindRegistersWithoutFrame()`` function in
1510   ``lib/Target/X86FrameLowering.cpp`` for the encoding algorithm.)
1511
1512 *Frameless with a Large Constant Stack Size (``EBP`` or ``RBP`` is not used as a frame pointer)*
1513   This case is like the "Frameless with a Small Constant Stack Size" case, but
1514   the stack size is too large to encode in the compact unwind encoding. Instead
1515   it requires that the function contains "``subl $nnnnnn, %esp``" in its
1516   prolog. The compact encoding contains the offset to the ``$nnnnnn`` value in
1517   the function in bits 9-12 (mask: ``0x00001C00``).
1518
1519 .. _Late Machine Code Optimizations:
1520
1521 Late Machine Code Optimizations
1522 -------------------------------
1523
1524 .. note::
1525
1526   To Be Written
1527
1528 .. _Code Emission:
1529
1530 Code Emission
1531 -------------
1532
1533 The code emission step of code generation is responsible for lowering from the
1534 code generator abstractions (like `MachineFunction`_, `MachineInstr`_, etc) down
1535 to the abstractions used by the MC layer (`MCInst`_, `MCStreamer`_, etc).  This
1536 is done with a combination of several different classes: the (misnamed)
1537 target-independent AsmPrinter class, target-specific subclasses of AsmPrinter
1538 (such as SparcAsmPrinter), and the TargetLoweringObjectFile class.
1539
1540 Since the MC layer works at the level of abstraction of object files, it doesn't
1541 have a notion of functions, global variables etc.  Instead, it thinks about
1542 labels, directives, and instructions.  A key class used at this time is the
1543 MCStreamer class.  This is an abstract API that is implemented in different ways
1544 (e.g. to output a .s file, output an ELF .o file, etc) that is effectively an
1545 "assembler API".  MCStreamer has one method per directive, such as EmitLabel,
1546 EmitSymbolAttribute, SwitchSection, etc, which directly correspond to assembly
1547 level directives.
1548
1549 If you are interested in implementing a code generator for a target, there are
1550 three important things that you have to implement for your target:
1551
1552 #. First, you need a subclass of AsmPrinter for your target.  This class
1553    implements the general lowering process converting MachineFunction's into MC
1554    label constructs.  The AsmPrinter base class provides a number of useful
1555    methods and routines, and also allows you to override the lowering process in
1556    some important ways.  You should get much of the lowering for free if you are
1557    implementing an ELF, COFF, or MachO target, because the
1558    TargetLoweringObjectFile class implements much of the common logic.
1559
1560 #. Second, you need to implement an instruction printer for your target.  The
1561    instruction printer takes an `MCInst`_ and renders it to a raw_ostream as
1562    text.  Most of this is automatically generated from the .td file (when you
1563    specify something like "``add $dst, $src1, $src2``" in the instructions), but
1564    you need to implement routines to print operands.
1565
1566 #. Third, you need to implement code that lowers a `MachineInstr`_ to an MCInst,
1567    usually implemented in "<target>MCInstLower.cpp".  This lowering process is
1568    often target specific, and is responsible for turning jump table entries,
1569    constant pool indices, global variable addresses, etc into MCLabels as
1570    appropriate.  This translation layer is also responsible for expanding pseudo
1571    ops used by the code generator into the actual machine instructions they
1572    correspond to. The MCInsts that are generated by this are fed into the
1573    instruction printer or the encoder.
1574
1575 Finally, at your choosing, you can also implement an subclass of MCCodeEmitter
1576 which lowers MCInst's into machine code bytes and relocations.  This is
1577 important if you want to support direct .o file emission, or would like to
1578 implement an assembler for your target.
1579
1580 VLIW Packetizer
1581 ---------------
1582
1583 In a Very Long Instruction Word (VLIW) architecture, the compiler is responsible
1584 for mapping instructions to functional-units available on the architecture. To
1585 that end, the compiler creates groups of instructions called *packets* or
1586 *bundles*. The VLIW packetizer in LLVM is a target-independent mechanism to
1587 enable the packetization of machine instructions.
1588
1589 Mapping from instructions to functional units
1590 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1591
1592 Instructions in a VLIW target can typically be mapped to multiple functional
1593 units. During the process of packetizing, the compiler must be able to reason
1594 about whether an instruction can be added to a packet. This decision can be
1595 complex since the compiler has to examine all possible mappings of instructions
1596 to functional units. Therefore to alleviate compilation-time complexity, the
1597 VLIW packetizer parses the instruction classes of a target and generates tables
1598 at compiler build time. These tables can then be queried by the provided
1599 machine-independent API to determine if an instruction can be accommodated in a
1600 packet.
1601
1602 How the packetization tables are generated and used
1603 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1604
1605 The packetizer reads instruction classes from a target's itineraries and creates
1606 a deterministic finite automaton (DFA) to represent the state of a packet. A DFA
1607 consists of three major elements: inputs, states, and transitions. The set of
1608 inputs for the generated DFA represents the instruction being added to a
1609 packet. The states represent the possible consumption of functional units by
1610 instructions in a packet. In the DFA, transitions from one state to another
1611 occur on the addition of an instruction to an existing packet. If there is a
1612 legal mapping of functional units to instructions, then the DFA contains a
1613 corresponding transition. The absence of a transition indicates that a legal
1614 mapping does not exist and that the instruction cannot be added to the packet.
1615
1616 To generate tables for a VLIW target, add *Target*\ GenDFAPacketizer.inc as a
1617 target to the Makefile in the target directory. The exported API provides three
1618 functions: ``DFAPacketizer::clearResources()``,
1619 ``DFAPacketizer::reserveResources(MachineInstr *MI)``, and
1620 ``DFAPacketizer::canReserveResources(MachineInstr *MI)``. These functions allow
1621 a target packetizer to add an instruction to an existing packet and to check
1622 whether an instruction can be added to a packet. See
1623 ``llvm/CodeGen/DFAPacketizer.h`` for more information.
1624
1625 Implementing a Native Assembler
1626 ===============================
1627
1628 Though you're probably reading this because you want to write or maintain a
1629 compiler backend, LLVM also fully supports building a native assembler.
1630 We've tried hard to automate the generation of the assembler from the .td files
1631 (in particular the instruction syntax and encodings), which means that a large
1632 part of the manual and repetitive data entry can be factored and shared with the
1633 compiler.
1634
1635 Instruction Parsing
1636 -------------------
1637
1638 .. note::
1639
1640   To Be Written
1641
1642
1643 Instruction Alias Processing
1644 ----------------------------
1645
1646 Once the instruction is parsed, it enters the MatchInstructionImpl function.
1647 The MatchInstructionImpl function performs alias processing and then does actual
1648 matching.
1649
1650 Alias processing is the phase that canonicalizes different lexical forms of the
1651 same instructions down to one representation.  There are several different kinds
1652 of alias that are possible to implement and they are listed below in the order
1653 that they are processed (which is in order from simplest/weakest to most
1654 complex/powerful).  Generally you want to use the first alias mechanism that
1655 meets the needs of your instruction, because it will allow a more concise
1656 description.
1657
1658 Mnemonic Aliases
1659 ^^^^^^^^^^^^^^^^
1660
1661 The first phase of alias processing is simple instruction mnemonic remapping for
1662 classes of instructions which are allowed with two different mnemonics.  This
1663 phase is a simple and unconditionally remapping from one input mnemonic to one
1664 output mnemonic.  It isn't possible for this form of alias to look at the
1665 operands at all, so the remapping must apply for all forms of a given mnemonic.
1666 Mnemonic aliases are defined simply, for example X86 has:
1667
1668 ::
1669
1670   def : MnemonicAlias<"cbw",     "cbtw">;
1671   def : MnemonicAlias<"smovq",   "movsq">;
1672   def : MnemonicAlias<"fldcww",  "fldcw">;
1673   def : MnemonicAlias<"fucompi", "fucomip">;
1674   def : MnemonicAlias<"ud2a",    "ud2">;
1675
1676 ... and many others.  With a MnemonicAlias definition, the mnemonic is remapped
1677 simply and directly.  Though MnemonicAlias's can't look at any aspect of the
1678 instruction (such as the operands) they can depend on global modes (the same
1679 ones supported by the matcher), through a Requires clause:
1680
1681 ::
1682
1683   def : MnemonicAlias<"pushf", "pushfq">, Requires<[In64BitMode]>;
1684   def : MnemonicAlias<"pushf", "pushfl">, Requires<[In32BitMode]>;
1685
1686 In this example, the mnemonic gets mapped into different a new one depending on
1687 the current instruction set.
1688
1689 Instruction Aliases
1690 ^^^^^^^^^^^^^^^^^^^
1691
1692 The most general phase of alias processing occurs while matching is happening:
1693 it provides new forms for the matcher to match along with a specific instruction
1694 to generate.  An instruction alias has two parts: the string to match and the
1695 instruction to generate.  For example:
1696
1697 ::
1698
1699   def : InstAlias<"movsx $src, $dst", (MOVSX16rr8W GR16:$dst, GR8  :$src)>;
1700   def : InstAlias<"movsx $src, $dst", (MOVSX16rm8W GR16:$dst, i8mem:$src)>;
1701   def : InstAlias<"movsx $src, $dst", (MOVSX32rr8  GR32:$dst, GR8  :$src)>;
1702   def : InstAlias<"movsx $src, $dst", (MOVSX32rr16 GR32:$dst, GR16 :$src)>;
1703   def : InstAlias<"movsx $src, $dst", (MOVSX64rr8  GR64:$dst, GR8  :$src)>;
1704   def : InstAlias<"movsx $src, $dst", (MOVSX64rr16 GR64:$dst, GR16 :$src)>;
1705   def : InstAlias<"movsx $src, $dst", (MOVSX64rr32 GR64:$dst, GR32 :$src)>;
1706
1707 This shows a powerful example of the instruction aliases, matching the same
1708 mnemonic in multiple different ways depending on what operands are present in
1709 the assembly.  The result of instruction aliases can include operands in a
1710 different order than the destination instruction, and can use an input multiple
1711 times, for example:
1712
1713 ::
1714
1715   def : InstAlias<"clrb $reg", (XOR8rr  GR8 :$reg, GR8 :$reg)>;
1716   def : InstAlias<"clrw $reg", (XOR16rr GR16:$reg, GR16:$reg)>;
1717   def : InstAlias<"clrl $reg", (XOR32rr GR32:$reg, GR32:$reg)>;
1718   def : InstAlias<"clrq $reg", (XOR64rr GR64:$reg, GR64:$reg)>;
1719
1720 This example also shows that tied operands are only listed once.  In the X86
1721 backend, XOR8rr has two input GR8's and one output GR8 (where an input is tied
1722 to the output).  InstAliases take a flattened operand list without duplicates
1723 for tied operands.  The result of an instruction alias can also use immediates
1724 and fixed physical registers which are added as simple immediate operands in the
1725 result, for example:
1726
1727 ::
1728
1729   // Fixed Immediate operand.
1730   def : InstAlias<"aad", (AAD8i8 10)>;
1731
1732   // Fixed register operand.
1733   def : InstAlias<"fcomi", (COM_FIr ST1)>;
1734
1735   // Simple alias.
1736   def : InstAlias<"fcomi $reg", (COM_FIr RST:$reg)>;
1737
1738 Instruction aliases can also have a Requires clause to make them subtarget
1739 specific.
1740
1741 If the back-end supports it, the instruction printer can automatically emit the
1742 alias rather than what's being aliased. It typically leads to better, more
1743 readable code. If it's better to print out what's being aliased, then pass a '0'
1744 as the third parameter to the InstAlias definition.
1745
1746 Instruction Matching
1747 --------------------
1748
1749 .. note::
1750
1751   To Be Written
1752
1753 .. _Implementations of the abstract target description interfaces:
1754 .. _implement the target description:
1755
1756 Target-specific Implementation Notes
1757 ====================================
1758
1759 This section of the document explains features or design decisions that are
1760 specific to the code generator for a particular target.  First we start with a
1761 table that summarizes what features are supported by each target.
1762
1763 .. _target-feature-matrix:
1764
1765 Target Feature Matrix
1766 ---------------------
1767
1768 Note that this table does not include the C backend or Cpp backends, since they
1769 do not use the target independent code generator infrastructure.  It also
1770 doesn't list features that are not supported fully by any target yet.  It
1771 considers a feature to be supported if at least one subtarget supports it.  A
1772 feature being supported means that it is useful and works for most cases, it
1773 does not indicate that there are zero known bugs in the implementation.  Here is
1774 the key:
1775
1776 :raw-html:`<table border="1" cellspacing="0">`
1777 :raw-html:`<tr>`
1778 :raw-html:`<th>Unknown</th>`
1779 :raw-html:`<th>Not Applicable</th>`
1780 :raw-html:`<th>No support</th>`
1781 :raw-html:`<th>Partial Support</th>`
1782 :raw-html:`<th>Complete Support</th>`
1783 :raw-html:`</tr>`
1784 :raw-html:`<tr>`
1785 :raw-html:`<td class="unknown"></td>`
1786 :raw-html:`<td class="na"></td>`
1787 :raw-html:`<td class="no"></td>`
1788 :raw-html:`<td class="partial"></td>`
1789 :raw-html:`<td class="yes"></td>`
1790 :raw-html:`</tr>`
1791 :raw-html:`</table>`
1792
1793 Here is the table:
1794
1795 :raw-html:`<table width="689" border="1" cellspacing="0">`
1796 :raw-html:`<tr><td></td>`
1797 :raw-html:`<td colspan="13" align="center" style="background-color:#ffc">Target</td>`
1798 :raw-html:`</tr>`
1799 :raw-html:`<tr>`
1800 :raw-html:`<th>Feature</th>`
1801 :raw-html:`<th>ARM</th>`
1802 :raw-html:`<th>Hexagon</th>`
1803 :raw-html:`<th>MSP430</th>`
1804 :raw-html:`<th>Mips</th>`
1805 :raw-html:`<th>NVPTX</th>`
1806 :raw-html:`<th>PowerPC</th>`
1807 :raw-html:`<th>Sparc</th>`
1808 :raw-html:`<th>SystemZ</th>`
1809 :raw-html:`<th>X86</th>`
1810 :raw-html:`<th>XCore</th>`
1811 :raw-html:`</tr>`
1812
1813 :raw-html:`<tr>`
1814 :raw-html:`<td><a href="#feat_reliable">is generally reliable</a></td>`
1815 :raw-html:`<td class="yes"></td> <!-- ARM -->`
1816 :raw-html:`<td class="yes"></td> <!-- Hexagon -->`
1817 :raw-html:`<td class="unknown"></td> <!-- MSP430 -->`
1818 :raw-html:`<td class="yes"></td> <!-- Mips -->`
1819 :raw-html:`<td class="yes"></td> <!-- NVPTX -->`
1820 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
1821 :raw-html:`<td class="yes"></td> <!-- Sparc -->`
1822 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
1823 :raw-html:`<td class="yes"></td> <!-- X86 -->`
1824 :raw-html:`<td class="yes"></td> <!-- XCore -->`
1825 :raw-html:`</tr>`
1826
1827 :raw-html:`<tr>`
1828 :raw-html:`<td><a href="#feat_asmparser">assembly parser</a></td>`
1829 :raw-html:`<td class="no"></td> <!-- ARM -->`
1830 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
1831 :raw-html:`<td class="no"></td> <!-- MSP430 -->`
1832 :raw-html:`<td class="no"></td> <!-- Mips -->`
1833 :raw-html:`<td class="no"></td> <!-- NVPTX -->`
1834 :raw-html:`<td class="no"></td> <!-- PowerPC -->`
1835 :raw-html:`<td class="no"></td> <!-- Sparc -->`
1836 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
1837 :raw-html:`<td class="yes"></td> <!-- X86 -->`
1838 :raw-html:`<td class="no"></td> <!-- XCore -->`
1839 :raw-html:`</tr>`
1840
1841 :raw-html:`<tr>`
1842 :raw-html:`<td><a href="#feat_disassembler">disassembler</a></td>`
1843 :raw-html:`<td class="yes"></td> <!-- ARM -->`
1844 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
1845 :raw-html:`<td class="no"></td> <!-- MSP430 -->`
1846 :raw-html:`<td class="no"></td> <!-- Mips -->`
1847 :raw-html:`<td class="na"></td> <!-- NVPTX -->`
1848 :raw-html:`<td class="no"></td> <!-- PowerPC -->`
1849 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
1850 :raw-html:`<td class="no"></td> <!-- Sparc -->`
1851 :raw-html:`<td class="yes"></td> <!-- X86 -->`
1852 :raw-html:`<td class="yes"></td> <!-- XCore -->`
1853 :raw-html:`</tr>`
1854
1855 :raw-html:`<tr>`
1856 :raw-html:`<td><a href="#feat_inlineasm">inline asm</a></td>`
1857 :raw-html:`<td class="yes"></td> <!-- ARM -->`
1858 :raw-html:`<td class="yes"></td> <!-- Hexagon -->`
1859 :raw-html:`<td class="unknown"></td> <!-- MSP430 -->`
1860 :raw-html:`<td class="no"></td> <!-- Mips -->`
1861 :raw-html:`<td class="yes"></td> <!-- NVPTX -->`
1862 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
1863 :raw-html:`<td class="unknown"></td> <!-- Sparc -->`
1864 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
1865 :raw-html:`<td class="yes"></td> <!-- X86 -->`
1866 :raw-html:`<td class="yes"></td> <!-- XCore -->`
1867 :raw-html:`</tr>`
1868
1869 :raw-html:`<tr>`
1870 :raw-html:`<td><a href="#feat_jit">jit</a></td>`
1871 :raw-html:`<td class="partial"><a href="#feat_jit_arm">*</a></td> <!-- ARM -->`
1872 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
1873 :raw-html:`<td class="unknown"></td> <!-- MSP430 -->`
1874 :raw-html:`<td class="yes"></td> <!-- Mips -->`
1875 :raw-html:`<td class="na"></td> <!-- NVPTX -->`
1876 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
1877 :raw-html:`<td class="unknown"></td> <!-- Sparc -->`
1878 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
1879 :raw-html:`<td class="yes"></td> <!-- X86 -->`
1880 :raw-html:`<td class="no"></td> <!-- XCore -->`
1881 :raw-html:`</tr>`
1882
1883 :raw-html:`<tr>`
1884 :raw-html:`<td><a href="#feat_objectwrite">.o&nbsp;file writing</a></td>`
1885 :raw-html:`<td class="no"></td> <!-- ARM -->`
1886 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
1887 :raw-html:`<td class="no"></td> <!-- MSP430 -->`
1888 :raw-html:`<td class="no"></td> <!-- Mips -->`
1889 :raw-html:`<td class="na"></td> <!-- NVPTX -->`
1890 :raw-html:`<td class="no"></td> <!-- PowerPC -->`
1891 :raw-html:`<td class="no"></td> <!-- Sparc -->`
1892 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
1893 :raw-html:`<td class="yes"></td> <!-- X86 -->`
1894 :raw-html:`<td class="no"></td> <!-- XCore -->`
1895 :raw-html:`</tr>`
1896
1897 :raw-html:`<tr>`
1898 :raw-html:`<td><a hr:raw-html:`ef="#feat_tailcall">tail calls</a></td>`
1899 :raw-html:`<td class="yes"></td> <!-- ARM -->`
1900 :raw-html:`<td class="yes"></td> <!-- Hexagon -->`
1901 :raw-html:`<td class="unknown"></td> <!-- MSP430 -->`
1902 :raw-html:`<td class="no"></td> <!-- Mips -->`
1903 :raw-html:`<td class="no"></td> <!-- NVPTX -->`
1904 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
1905 :raw-html:`<td class="unknown"></td> <!-- Sparc -->`
1906 :raw-html:`<td class="no"></td> <!-- SystemZ -->`
1907 :raw-html:`<td class="yes"></td> <!-- X86 -->`
1908 :raw-html:`<td class="no"></td> <!-- XCore -->`
1909 :raw-html:`</tr>`
1910
1911 :raw-html:`<tr>`
1912 :raw-html:`<td><a href="#feat_segstacks">segmented stacks</a></td>`
1913 :raw-html:`<td class="no"></td> <!-- ARM -->`
1914 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
1915 :raw-html:`<td class="no"></td> <!-- MSP430 -->`
1916 :raw-html:`<td class="no"></td> <!-- Mips -->`
1917 :raw-html:`<td class="no"></td> <!-- NVPTX -->`
1918 :raw-html:`<td class="no"></td> <!-- PowerPC -->`
1919 :raw-html:`<td class="no"></td> <!-- Sparc -->`
1920 :raw-html:`<td class="no"></td> <!-- SystemZ -->`
1921 :raw-html:`<td class="partial"><a href="#feat_segstacks_x86">*</a></td> <!-- X86 -->`
1922 :raw-html:`<td class="no"></td> <!-- XCore -->`
1923 :raw-html:`</tr>`
1924
1925 :raw-html:`</table>`
1926
1927 .. _feat_reliable:
1928
1929 Is Generally Reliable
1930 ^^^^^^^^^^^^^^^^^^^^^
1931
1932 This box indicates whether the target is considered to be production quality.
1933 This indicates that the target has been used as a static compiler to compile
1934 large amounts of code by a variety of different people and is in continuous use.
1935
1936 .. _feat_asmparser:
1937
1938 Assembly Parser
1939 ^^^^^^^^^^^^^^^
1940
1941 This box indicates whether the target supports parsing target specific .s files
1942 by implementing the MCAsmParser interface.  This is required for llvm-mc to be
1943 able to act as a native assembler and is required for inline assembly support in
1944 the native .o file writer.
1945
1946 .. _feat_disassembler:
1947
1948 Disassembler
1949 ^^^^^^^^^^^^
1950
1951 This box indicates whether the target supports the MCDisassembler API for
1952 disassembling machine opcode bytes into MCInst's.
1953
1954 .. _feat_inlineasm:
1955
1956 Inline Asm
1957 ^^^^^^^^^^
1958
1959 This box indicates whether the target supports most popular inline assembly
1960 constraints and modifiers.
1961
1962 .. _feat_jit:
1963
1964 JIT Support
1965 ^^^^^^^^^^^
1966
1967 This box indicates whether the target supports the JIT compiler through the
1968 ExecutionEngine interface.
1969
1970 .. _feat_jit_arm:
1971
1972 The ARM backend has basic support for integer code in ARM codegen mode, but
1973 lacks NEON and full Thumb support.
1974
1975 .. _feat_objectwrite:
1976
1977 .o File Writing
1978 ^^^^^^^^^^^^^^^
1979
1980 This box indicates whether the target supports writing .o files (e.g. MachO,
1981 ELF, and/or COFF) files directly from the target.  Note that the target also
1982 must include an assembly parser and general inline assembly support for full
1983 inline assembly support in the .o writer.
1984
1985 Targets that don't support this feature can obviously still write out .o files,
1986 they just rely on having an external assembler to translate from a .s file to a
1987 .o file (as is the case for many C compilers).
1988
1989 .. _feat_tailcall:
1990
1991 Tail Calls
1992 ^^^^^^^^^^
1993
1994 This box indicates whether the target supports guaranteed tail calls.  These are
1995 calls marked "`tail <LangRef.html#i_call>`_" and use the fastcc calling
1996 convention.  Please see the `tail call section more more details`_.
1997
1998 .. _feat_segstacks:
1999
2000 Segmented Stacks
2001 ^^^^^^^^^^^^^^^^
2002
2003 This box indicates whether the target supports segmented stacks. This replaces
2004 the traditional large C stack with many linked segments. It is compatible with
2005 the `gcc implementation <http://gcc.gnu.org/wiki/SplitStacks>`_ used by the Go
2006 front end.
2007
2008 .. _feat_segstacks_x86:
2009
2010 Basic support exists on the X86 backend. Currently vararg doesn't work and the
2011 object files are not marked the way the gold linker expects, but simple Go
2012 programs can be built by dragonegg.
2013
2014 .. _tail call section more more details:
2015
2016 Tail call optimization
2017 ----------------------
2018
2019 Tail call optimization, callee reusing the stack of the caller, is currently
2020 supported on x86/x86-64 and PowerPC. It is performed if:
2021
2022 * Caller and callee have the calling convention ``fastcc``, ``cc 10`` (GHC
2023   calling convention) or ``cc 11`` (HiPE calling convention).
2024
2025 * The call is a tail call - in tail position (ret immediately follows call and
2026   ret uses value of call or is void).
2027
2028 * Option ``-tailcallopt`` is enabled.
2029
2030 * Platform specific constraints are met.
2031
2032 x86/x86-64 constraints:
2033
2034 * No variable argument lists are used.
2035
2036 * On x86-64 when generating GOT/PIC code only module-local calls (visibility =
2037   hidden or protected) are supported.
2038
2039 PowerPC constraints:
2040
2041 * No variable argument lists are used.
2042
2043 * No byval parameters are used.
2044
2045 * On ppc32/64 GOT/PIC only module-local calls (visibility = hidden or protected)
2046   are supported.
2047
2048 Example:
2049
2050 Call as ``llc -tailcallopt test.ll``.
2051
2052 .. code-block:: llvm
2053
2054   declare fastcc i32 @tailcallee(i32 inreg %a1, i32 inreg %a2, i32 %a3, i32 %a4)
2055
2056   define fastcc i32 @tailcaller(i32 %in1, i32 %in2) {
2057     %l1 = add i32 %in1, %in2
2058     %tmp = tail call fastcc i32 @tailcallee(i32 %in1 inreg, i32 %in2 inreg, i32 %in1, i32 %l1)
2059     ret i32 %tmp
2060   }
2061
2062 Implications of ``-tailcallopt``:
2063
2064 To support tail call optimization in situations where the callee has more
2065 arguments than the caller a 'callee pops arguments' convention is used. This
2066 currently causes each ``fastcc`` call that is not tail call optimized (because
2067 one or more of above constraints are not met) to be followed by a readjustment
2068 of the stack. So performance might be worse in such cases.
2069
2070 Sibling call optimization
2071 -------------------------
2072
2073 Sibling call optimization is a restricted form of tail call optimization.
2074 Unlike tail call optimization described in the previous section, it can be
2075 performed automatically on any tail calls when ``-tailcallopt`` option is not
2076 specified.
2077
2078 Sibling call optimization is currently performed on x86/x86-64 when the
2079 following constraints are met:
2080
2081 * Caller and callee have the same calling convention. It can be either ``c`` or
2082   ``fastcc``.
2083
2084 * The call is a tail call - in tail position (ret immediately follows call and
2085   ret uses value of call or is void).
2086
2087 * Caller and callee have matching return type or the callee result is not used.
2088
2089 * If any of the callee arguments are being passed in stack, they must be
2090   available in caller's own incoming argument stack and the frame offsets must
2091   be the same.
2092
2093 Example:
2094
2095 .. code-block:: llvm
2096
2097   declare i32 @bar(i32, i32)
2098
2099   define i32 @foo(i32 %a, i32 %b, i32 %c) {
2100   entry:
2101     %0 = tail call i32 @bar(i32 %a, i32 %b)
2102     ret i32 %0
2103   }
2104
2105 The X86 backend
2106 ---------------
2107
2108 The X86 code generator lives in the ``lib/Target/X86`` directory.  This code
2109 generator is capable of targeting a variety of x86-32 and x86-64 processors, and
2110 includes support for ISA extensions such as MMX and SSE.
2111
2112 X86 Target Triples supported
2113 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2114
2115 The following are the known target triples that are supported by the X86
2116 backend.  This is not an exhaustive list, and it would be useful to add those
2117 that people test.
2118
2119 * **i686-pc-linux-gnu** --- Linux
2120
2121 * **i386-unknown-freebsd5.3** --- FreeBSD 5.3
2122
2123 * **i686-pc-cygwin** --- Cygwin on Win32
2124
2125 * **i686-pc-mingw32** --- MingW on Win32
2126
2127 * **i386-pc-mingw32msvc** --- MingW crosscompiler on Linux
2128
2129 * **i686-apple-darwin*** --- Apple Darwin on X86
2130
2131 * **x86_64-unknown-linux-gnu** --- Linux
2132
2133 X86 Calling Conventions supported
2134 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2135
2136 The following target-specific calling conventions are known to backend:
2137
2138 * **x86_StdCall** --- stdcall calling convention seen on Microsoft Windows
2139   platform (CC ID = 64).
2140
2141 * **x86_FastCall** --- fastcall calling convention seen on Microsoft Windows
2142   platform (CC ID = 65).
2143
2144 * **x86_ThisCall** --- Similar to X86_StdCall. Passes first argument in ECX,
2145   others via stack. Callee is responsible for stack cleaning. This convention is
2146   used by MSVC by default for methods in its ABI (CC ID = 70).
2147
2148 .. _X86 addressing mode:
2149
2150 Representing X86 addressing modes in MachineInstrs
2151 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2152
2153 The x86 has a very flexible way of accessing memory.  It is capable of forming
2154 memory addresses of the following expression directly in integer instructions
2155 (which use ModR/M addressing):
2156
2157 ::
2158
2159   SegmentReg: Base + [1,2,4,8] * IndexReg + Disp32
2160
2161 In order to represent this, LLVM tracks no less than 5 operands for each memory
2162 operand of this form.  This means that the "load" form of '``mov``' has the
2163 following ``MachineOperand``\s in this order:
2164
2165 ::
2166
2167   Index:        0     |    1        2       3           4          5
2168   Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement Segment
2169   OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm  PhysReg
2170
2171 Stores, and all other instructions, treat the four memory operands in the same
2172 way and in the same order.  If the segment register is unspecified (regno = 0),
2173 then no segment override is generated.  "Lea" operations do not have a segment
2174 register specified, so they only have 4 operands for their memory reference.
2175
2176 X86 address spaces supported
2177 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
2178
2179 x86 has a feature which provides the ability to perform loads and stores to
2180 different address spaces via the x86 segment registers.  A segment override
2181 prefix byte on an instruction causes the instruction's memory access to go to
2182 the specified segment.  LLVM address space 0 is the default address space, which
2183 includes the stack, and any unqualified memory accesses in a program.  Address
2184 spaces 1-255 are currently reserved for user-defined code.  The GS-segment is
2185 represented by address space 256, while the FS-segment is represented by address
2186 space 257. Other x86 segments have yet to be allocated address space
2187 numbers.
2188
2189 While these address spaces may seem similar to TLS via the ``thread_local``
2190 keyword, and often use the same underlying hardware, there are some fundamental
2191 differences.
2192
2193 The ``thread_local`` keyword applies to global variables and specifies that they
2194 are to be allocated in thread-local memory. There are no type qualifiers
2195 involved, and these variables can be pointed to with normal pointers and
2196 accessed with normal loads and stores.  The ``thread_local`` keyword is
2197 target-independent at the LLVM IR level (though LLVM doesn't yet have
2198 implementations of it for some configurations)
2199
2200 Special address spaces, in contrast, apply to static types. Every load and store
2201 has a particular address space in its address operand type, and this is what
2202 determines which address space is accessed.  LLVM ignores these special address
2203 space qualifiers on global variables, and does not provide a way to directly
2204 allocate storage in them.  At the LLVM IR level, the behavior of these special
2205 address spaces depends in part on the underlying OS or runtime environment, and
2206 they are specific to x86 (and LLVM doesn't yet handle them correctly in some
2207 cases).
2208
2209 Some operating systems and runtime environments use (or may in the future use)
2210 the FS/GS-segment registers for various low-level purposes, so care should be
2211 taken when considering them.
2212
2213 Instruction naming
2214 ^^^^^^^^^^^^^^^^^^
2215
2216 An instruction name consists of the base name, a default operand size, and a a
2217 character per operand with an optional special size. For example:
2218
2219 ::
2220
2221   ADD8rr      -> add, 8-bit register, 8-bit register
2222   IMUL16rmi   -> imul, 16-bit register, 16-bit memory, 16-bit immediate
2223   IMUL16rmi8  -> imul, 16-bit register, 16-bit memory, 8-bit immediate
2224   MOVSX32rm16 -> movsx, 32-bit register, 16-bit memory
2225
2226 The PowerPC backend
2227 -------------------
2228
2229 The PowerPC code generator lives in the lib/Target/PowerPC directory.  The code
2230 generation is retargetable to several variations or *subtargets* of the PowerPC
2231 ISA; including ppc32, ppc64 and altivec.
2232
2233 LLVM PowerPC ABI
2234 ^^^^^^^^^^^^^^^^
2235
2236 LLVM follows the AIX PowerPC ABI, with two deviations. LLVM uses a PC relative
2237 (PIC) or static addressing for accessing global values, so no TOC (r2) is
2238 used. Second, r31 is used as a frame pointer to allow dynamic growth of a stack
2239 frame.  LLVM takes advantage of having no TOC to provide space to save the frame
2240 pointer in the PowerPC linkage area of the caller frame.  Other details of
2241 PowerPC ABI can be found at `PowerPC ABI
2242 <http://developer.apple.com/documentation/DeveloperTools/Conceptual/LowLevelABI/Articles/32bitPowerPC.html>`_\
2243 . Note: This link describes the 32 bit ABI.  The 64 bit ABI is similar except
2244 space for GPRs are 8 bytes wide (not 4) and r13 is reserved for system use.
2245
2246 Frame Layout
2247 ^^^^^^^^^^^^
2248
2249 The size of a PowerPC frame is usually fixed for the duration of a function's
2250 invocation.  Since the frame is fixed size, all references into the frame can be
2251 accessed via fixed offsets from the stack pointer.  The exception to this is
2252 when dynamic alloca or variable sized arrays are present, then a base pointer
2253 (r31) is used as a proxy for the stack pointer and stack pointer is free to grow
2254 or shrink.  A base pointer is also used if llvm-gcc is not passed the
2255 -fomit-frame-pointer flag. The stack pointer is always aligned to 16 bytes, so
2256 that space allocated for altivec vectors will be properly aligned.
2257
2258 An invocation frame is laid out as follows (low memory at top):
2259
2260 :raw-html:`<table border="1" cellspacing="0">`
2261 :raw-html:`<tr>`
2262 :raw-html:`<td>Linkage<br><br></td>`
2263 :raw-html:`</tr>`
2264 :raw-html:`<tr>`
2265 :raw-html:`<td>Parameter area<br><br></td>`
2266 :raw-html:`</tr>`
2267 :raw-html:`<tr>`
2268 :raw-html:`<td>Dynamic area<br><br></td>`
2269 :raw-html:`</tr>`
2270 :raw-html:`<tr>`
2271 :raw-html:`<td>Locals area<br><br></td>`
2272 :raw-html:`</tr>`
2273 :raw-html:`<tr>`
2274 :raw-html:`<td>Saved registers area<br><br></td>`
2275 :raw-html:`</tr>`
2276 :raw-html:`<tr style="border-style: none hidden none hidden;">`
2277 :raw-html:`<td><br></td>`
2278 :raw-html:`</tr>`
2279 :raw-html:`<tr>`
2280 :raw-html:`<td>Previous Frame<br><br></td>`
2281 :raw-html:`</tr>`
2282 :raw-html:`</table>`
2283
2284 The *linkage* area is used by a callee to save special registers prior to
2285 allocating its own frame.  Only three entries are relevant to LLVM. The first
2286 entry is the previous stack pointer (sp), aka link.  This allows probing tools
2287 like gdb or exception handlers to quickly scan the frames in the stack.  A
2288 function epilog can also use the link to pop the frame from the stack.  The
2289 third entry in the linkage area is used to save the return address from the lr
2290 register. Finally, as mentioned above, the last entry is used to save the
2291 previous frame pointer (r31.)  The entries in the linkage area are the size of a
2292 GPR, thus the linkage area is 24 bytes long in 32 bit mode and 48 bytes in 64
2293 bit mode.
2294
2295 32 bit linkage area:
2296
2297 :raw-html:`<table  border="1" cellspacing="0">`
2298 :raw-html:`<tr>`
2299 :raw-html:`<td>0</td>`
2300 :raw-html:`<td>Saved SP (r1)</td>`
2301 :raw-html:`</tr>`
2302 :raw-html:`<tr>`
2303 :raw-html:`<td>4</td>`
2304 :raw-html:`<td>Saved CR</td>`
2305 :raw-html:`</tr>`
2306 :raw-html:`<tr>`
2307 :raw-html:`<td>8</td>`
2308 :raw-html:`<td>Saved LR</td>`
2309 :raw-html:`</tr>`
2310 :raw-html:`<tr>`
2311 :raw-html:`<td>12</td>`
2312 :raw-html:`<td>Reserved</td>`
2313 :raw-html:`</tr>`
2314 :raw-html:`<tr>`
2315 :raw-html:`<td>16</td>`
2316 :raw-html:`<td>Reserved</td>`
2317 :raw-html:`</tr>`
2318 :raw-html:`<tr>`
2319 :raw-html:`<td>20</td>`
2320 :raw-html:`<td>Saved FP (r31)</td>`
2321 :raw-html:`</tr>`
2322 :raw-html:`</table>`
2323
2324 64 bit linkage area:
2325
2326 :raw-html:`<table border="1" cellspacing="0">`
2327 :raw-html:`<tr>`
2328 :raw-html:`<td>0</td>`
2329 :raw-html:`<td>Saved SP (r1)</td>`
2330 :raw-html:`</tr>`
2331 :raw-html:`<tr>`
2332 :raw-html:`<td>8</td>`
2333 :raw-html:`<td>Saved CR</td>`
2334 :raw-html:`</tr>`
2335 :raw-html:`<tr>`
2336 :raw-html:`<td>16</td>`
2337 :raw-html:`<td>Saved LR</td>`
2338 :raw-html:`</tr>`
2339 :raw-html:`<tr>`
2340 :raw-html:`<td>24</td>`
2341 :raw-html:`<td>Reserved</td>`
2342 :raw-html:`</tr>`
2343 :raw-html:`<tr>`
2344 :raw-html:`<td>32</td>`
2345 :raw-html:`<td>Reserved</td>`
2346 :raw-html:`</tr>`
2347 :raw-html:`<tr>`
2348 :raw-html:`<td>40</td>`
2349 :raw-html:`<td>Saved FP (r31)</td>`
2350 :raw-html:`</tr>`
2351 :raw-html:`</table>`
2352
2353 The *parameter area* is used to store arguments being passed to a callee
2354 function.  Following the PowerPC ABI, the first few arguments are actually
2355 passed in registers, with the space in the parameter area unused.  However, if
2356 there are not enough registers or the callee is a thunk or vararg function,
2357 these register arguments can be spilled into the parameter area.  Thus, the
2358 parameter area must be large enough to store all the parameters for the largest
2359 call sequence made by the caller.  The size must also be minimally large enough
2360 to spill registers r3-r10.  This allows callees blind to the call signature,
2361 such as thunks and vararg functions, enough space to cache the argument
2362 registers.  Therefore, the parameter area is minimally 32 bytes (64 bytes in 64
2363 bit mode.)  Also note that since the parameter area is a fixed offset from the
2364 top of the frame, that a callee can access its spilt arguments using fixed
2365 offsets from the stack pointer (or base pointer.)
2366
2367 Combining the information about the linkage, parameter areas and alignment. A
2368 stack frame is minimally 64 bytes in 32 bit mode and 128 bytes in 64 bit mode.
2369
2370 The *dynamic area* starts out as size zero.  If a function uses dynamic alloca
2371 then space is added to the stack, the linkage and parameter areas are shifted to
2372 top of stack, and the new space is available immediately below the linkage and
2373 parameter areas.  The cost of shifting the linkage and parameter areas is minor
2374 since only the link value needs to be copied.  The link value can be easily
2375 fetched by adding the original frame size to the base pointer.  Note that
2376 allocations in the dynamic space need to observe 16 byte alignment.
2377
2378 The *locals area* is where the llvm compiler reserves space for local variables.
2379
2380 The *saved registers area* is where the llvm compiler spills callee saved
2381 registers on entry to the callee.
2382
2383 Prolog/Epilog
2384 ^^^^^^^^^^^^^
2385
2386 The llvm prolog and epilog are the same as described in the PowerPC ABI, with
2387 the following exceptions.  Callee saved registers are spilled after the frame is
2388 created.  This allows the llvm epilog/prolog support to be common with other
2389 targets.  The base pointer callee saved register r31 is saved in the TOC slot of
2390 linkage area.  This simplifies allocation of space for the base pointer and
2391 makes it convenient to locate programatically and during debugging.
2392
2393 Dynamic Allocation
2394 ^^^^^^^^^^^^^^^^^^
2395
2396 .. note::
2397
2398   TODO - More to come.
2399
2400 The NVPTX backend
2401 -----------------
2402
2403 The NVPTX code generator under lib/Target/NVPTX is an open-source version of
2404 the NVIDIA NVPTX code generator for LLVM.  It is contributed by NVIDIA and is
2405 a port of the code generator used in the CUDA compiler (nvcc).  It targets the
2406 PTX 3.0/3.1 ISA and can target any compute capability greater than or equal to
2407 2.0 (Fermi).
2408
2409 This target is of production quality and should be completely compatible with
2410 the official NVIDIA toolchain.
2411
2412 Code Generator Options:
2413
2414 :raw-html:`<table border="1" cellspacing="0">`
2415 :raw-html:`<tr>`
2416 :raw-html:`<th>Option</th>`
2417 :raw-html:`<th>Description</th>`
2418 :raw-html:`</tr>`
2419 :raw-html:`<tr>`
2420 :raw-html:`<td>sm_20</td>`
2421 :raw-html:`<td align="left">Set shader model/compute capability to 2.0</td>`
2422 :raw-html:`</tr>`
2423 :raw-html:`<tr>`
2424 :raw-html:`<td>sm_21</td>`
2425 :raw-html:`<td align="left">Set shader model/compute capability to 2.1</td>`
2426 :raw-html:`</tr>`
2427 :raw-html:`<tr>`
2428 :raw-html:`<td>sm_30</td>`
2429 :raw-html:`<td align="left">Set shader model/compute capability to 3.0</td>`
2430 :raw-html:`</tr>`
2431 :raw-html:`<tr>`
2432 :raw-html:`<td>sm_35</td>`
2433 :raw-html:`<td align="left">Set shader model/compute capability to 3.5</td>`
2434 :raw-html:`</tr>`
2435 :raw-html:`<tr>`
2436 :raw-html:`<td>ptx30</td>`
2437 :raw-html:`<td align="left">Target PTX 3.0</td>`
2438 :raw-html:`</tr>`
2439 :raw-html:`<tr>`
2440 :raw-html:`<td>ptx31</td>`
2441 :raw-html:`<td align="left">Target PTX 3.1</td>`
2442 :raw-html:`</tr>`
2443 :raw-html:`</table>`
2444