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