brintos / llvm-project-archived public Read only

1==========================================2The LLVM Target-Independent Code Generator3==========================================4 5.. role:: raw-html(raw)6   :format: html7 8.. raw:: html9 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 28Introduction29============30 31The LLVM target-independent code generator is a framework that provides a suite32of reusable components for translating the LLVM internal representation to the33machine code for a specified target---either in assembly form (suitable for a34static compiler) or in binary machine code format (usable for a JIT35compiler). The LLVM target-independent code generator consists of six main36components:37 381. `Abstract target description`_ interfaces which capture important properties39   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.  These43   classes are intended to be abstract enough to represent the machine code for44   *any* target machine.  These classes are defined in45   ``include/llvm/CodeGen/``. At this level, concepts like "constant pool46   entries" and "jump tables" are explicitly exposed.47 483. Classes and algorithms used to represent code at the object file level, the49   `MC Layer`_.  These classes represent assembly level constructs like labels,50   sections, and instructions.  At this level, concepts like "constant pool51   entries" and "jump tables" don't exist.52 534. `Target-independent algorithms`_ used to implement various phases of native54   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`_ for58   particular targets.  These machine descriptions make use of the components59   provided by LLVM, and can optionally provide custom target-specific passes,60   to build complete code generators for a specific target.  Target descriptions61   live in ``lib/Target/``.62 636. The target-independent JIT components.  The LLVM JIT is completely target64   independent (it uses the ``TargetJITInfo`` structure to interface for65   target-specific issues.  The code for the target-independent JIT lives in66   ``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 be70familiar with the `target description`_ and `machine code representation`_71classes.  If you want to add a backend for a new target, you will need to72`implement the target description`_ classes for your new target and understand73the :doc:`LLVM code representation <LangRef>`.  If you are interested in74implementing a new `code generation algorithm`_, it should only depend on the75target-description and machine code representation classes, ensuring that it is76portable.77 78Required components in the code generator79-----------------------------------------80 81The two pieces of the LLVM code generator are the high-level interface to the82code generator and the set of reusable components that can be used to build83target-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 a86backend to fit into the LLVM system, but the others must be defined if the87reusable code generator components are going to be used.88 89This design has two important implications.  The first is that LLVM can support90completely non-traditional code generation targets.  For example, the C backend91does not require register allocation, instruction selection, or any of the other92standard components provided by the system.  As such, it only implements these93two interfaces, and does its own thing. Note that the C backend was removed from the94trunk in the LLVM 3.1 release. Another example of a code generator like this is a95(purely hypothetical) backend that converts LLVM to the GCC RTL form and uses96GCC to emit machine code for a target.97 98This design also implies that it is possible to design and implement radically99different code generators in the LLVM system that do not make use of any of the100built-in components.  Doing so is not recommended at all, but could be required101for radically different targets that do not fit into the LLVM machine102description model: FPGAs for example.103 104.. _high-level design of the code generator:105 106The high-level design of the code generator107-------------------------------------------108 109The LLVM target-independent code generator is designed to support efficient and110quality code generation for standard register-based microprocessors.  Code111generation in this model is divided into the following stages:112 1131. `Instruction Selection`_ --- This phase determines an efficient way to114   express the input LLVM code in the target instruction set.  This stage115   produces the initial code for the program in the target instruction set, then116   makes use of virtual registers in SSA form and physical registers that117   represent any required register assignments due to target constraints or118   calling conventions.  This step turns the LLVM code into a DAG of target119   instructions.120 1212. `Scheduling and Formation`_ --- This phase takes the DAG of target122   instructions produced by the instruction selection phase, determines an123   ordering of the instructions, then emits the instructions as :raw-html:`<tt>`124   `MachineInstr`_\s :raw-html:`</tt>` with that ordering.  Note that we125   describe this in the `instruction selection section`_ because it operates on126   a `SelectionDAG`_.127 1283. `SSA-based Machine Code Optimizations`_ --- This optional stage consists of a129   series of machine-code optimizations that operate on the SSA-form produced by130   the instruction selector.  Optimizations like modulo-scheduling or peephole131   optimization work here.132 1334. `Register Allocation`_ --- The target code is transformed from an infinite134   virtual register file in SSA form to the concrete register file used by the135   target.  This phase introduces spill code and eliminates all virtual register136   references from the program.137 1385. `Prolog/Epilog Code Insertion`_ --- Once the machine code has been generated139   for the function and the amount of stack space required is known (used for140   LLVM alloca's and spill slots), the prolog and epilog code for the function141   can be inserted and "abstract stack location references" can be eliminated.142   This stage is responsible for implementing optimizations like frame-pointer143   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 peephole147   optimizations.148 1497. `Code Emission`_ --- The final stage actually puts out the code for the150   current function, either in the target assembler format or in machine151   code.152 153The code generator is based on the assumption that the instruction selector will154use an optimal pattern matching selector to create high-quality sequences of155native instructions.  Alternative code generator designs based on pattern156expansion and aggressive iterative peephole optimization are much slower.  This157design permits efficient compilation (important for JIT environments) and158aggressive optimization (used when generating code offline) by allowing159components of varying levels of sophistication to be used for any step of160compilation.161 162In addition to these stages, target implementations can insert arbitrary163target-specific passes into the flow.  For example, the X86 target uses a164special pass to handle the 80x87 floating point stack architecture.  Other165targets with unusual requirements can be supported with custom passes as needed.166 167Using TableGen for target description168-------------------------------------169 170The target description classes require a detailed description of the target171architecture.  These target descriptions often have a large amount of common172information (e.g., an ``add`` instruction is almost identical to a ``sub``173instruction).  In order to allow the maximum amount of commonality to be174factored out, the LLVM code generator uses the175:doc:`TableGen/index` tool to describe big chunks of the176target machine, which allows the use of domain-specific and target-specific177abstractions to reduce the amount of repetition.178 179As LLVM continues to be developed and refined, we plan to move more and more of180the target description to the ``.td`` form.  Doing so gives us a number of181advantages.  The most important is that it makes it easier to port LLVM because182it reduces the amount of C++ code that has to be written, and the surface area183of the code generator that needs to be understood before someone can get184something 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 change186in one place (``tblgen``) to update all of the targets to a new interface.187 188.. _Abstract target description:189.. _target description:190 191Target description classes192==========================193 194The LLVM target description classes (located in the ``include/llvm/Target``195directory) provide an abstract description of the target machine independent of196any particular client.  These classes are designed to capture the *abstract*197properties of the target (such as the instructions and registers it has), and do198not 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 target202implementation, and have virtual methods implemented.  To get to these203implementations, the :raw-html:`<tt>` `TargetMachine`_ :raw-html:`</tt>` class204provides accessors that should be implemented by the target.205 206.. _TargetMachine:207 208The ``TargetMachine`` class209---------------------------210 211The ``TargetMachine`` class provides virtual methods that are used to access the212target-specific implementations of the various target description classes via213the ``get*Info`` methods (``getInstrInfo``, ``getRegisterInfo``,214``getFrameInfo``, etc.).  This class is designed to be specialized by a concrete215target implementation (e.g., ``X86TargetMachine``) which implements the various216virtual methods.  The only required target description class is the217:raw-html:`<tt>` `DataLayout`_ :raw-html:`</tt>` class, but if the code218generator components are to be used, the other interfaces should be implemented219as well.220 221.. _DataLayout:222 223The ``DataLayout`` class224------------------------225 226The ``DataLayout`` class is the only required target description class, and it227is the only class that is not extensible (you cannot derive a new class from228it).  ``DataLayout`` specifies information about how the target lays out memory229for structures, the alignment requirements for various data types, the size of230pointers in the target, and whether the target is little-endian or231big-endian.232 233.. _TargetLowering:234 235The ``TargetLowering`` class236----------------------------237 238The ``TargetLowering`` class is used by SelectionDAG based instruction selectors239primarily to describe how LLVM code should be lowered to SelectionDAG240operations.  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, and249 250* various high-level characteristics, like whether it is profitable to turn251  division by a constant into a multiplication sequence.252 253.. _TargetRegisterInfo:254 255The ``TargetRegisterInfo`` class256--------------------------------257 258The ``TargetRegisterInfo`` class is used to describe the register file of the259target and any interactions between the registers.260 261Registers are represented in the code generator by unsigned integers.  Physical262registers (those that actually exist in the target description) are unique263small numbers, and virtual registers are generally large.  Note that264register ``#0`` is reserved as a flag value.265 266Each register in the processor description has an associated267``TargetRegisterDesc`` entry, which provides a textual name for the register268(used for assembly output and debugging dumps) and a set of aliases (used to269indicate whether one register overlaps with another).270 271In addition to the per-register description, the ``TargetRegisterInfo`` class272exposes a set of processor-specific register classes (instances of the273``TargetRegisterClass`` class).  Each register class contains sets of registers274that have the same properties (for example, they are all 32-bit integer275registers).  Each SSA virtual register created by the instruction selector has276an associated register class.  When the register allocator runs, it replaces277virtual registers with a physical register in the set.278 279The target-specific implementations of these classes is auto-generated from a280:doc:`TableGen/index` description of the register file.281 282.. _TargetInstrInfo:283 284The ``TargetInstrInfo`` class285-----------------------------286 287The ``TargetInstrInfo`` class is used to describe the machine instructions288supported by the target.  Descriptions define things like the mnemonic for289the opcode, the number of operands, the list of implicit register uses and defs,290whether the instruction has certain target-independent properties (accesses291memory, is commutable, etc), and holds any target-specific flags.292 293The ``TargetFrameLowering`` class294---------------------------------295 296The ``TargetFrameLowering`` class is used to provide information about the stack297frame layout of the target. It holds the direction of stack growth, the known298stack 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 function300entry to the first location where function data (local variables, spill301locations) can be stored.302 303The ``TargetSubtarget`` class304-----------------------------305 306The ``TargetSubtarget`` class is used to provide information about the specific307chip set being targeted.  A sub-target informs code generation of which308instructions are supported, instruction latencies and instruction execution309itinerary; i.e., which processing units are used, in what order, and for how310long.311 312The ``TargetJITInfo`` class313---------------------------314 315The ``TargetJITInfo`` class exposes an abstract interface used by the316Just-In-Time code generator to perform target-specific activities, such as317emitting stubs.  If a ``TargetMachine`` supports JIT code generation, it should318provide one of these objects through the ``getJITInfo`` method.319 320.. _code being generated:321.. _machine code representation:322 323Machine code description classes324================================325 326At the high-level, LLVM code is translated to a machine-specific representation327formed 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 in330``include/llvm/CodeGen``).  This representation is completely target agnostic,331representing instructions in their most abstract form: an opcode and a series of332operands.  This representation is designed to support both an SSA representation333for machine code, as well as a register allocated, non-SSA form.334 335.. _MachineInstr:336 337The ``MachineInstr`` class338--------------------------339 340Target machine instructions are represented as instances of the ``MachineInstr``341class.  This class is an extremely abstract way of representing machine342instructions.  In particular, it only keeps track of an opcode number and a set343of operands.344 345The opcode number is a simple unsigned integer that only has meaning to a346specific backend.  All of the instructions for a target should be defined in the347``*InstrInfo.td`` file for the target. The opcode enum values are auto-generated348from this description.  The ``MachineInstr`` class does not have any information349about how to interpret the instruction (i.e., what the semantics of the350instruction 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: a354register reference, a constant integer, a basic block reference, etc.  In355addition, a machine operand should be marked as a def or a use of the value356(though only registers are allowed to be defs).357 358By convention, the LLVM code generator orders instruction operands so that all359register definitions come before the register uses, even on architectures that360are normally printed in other orders.  For example, the SPARC add instruction:361"``add %i1, %i2, %i3``" adds the "%i1", and "%i2" registers and stores the362result into the "%i3" register.  In the LLVM code generator, the operands should363be stored as "``%i3, %i1, %i2``": with the destination first.364 365Keeping destination (definition) operands at the beginning of the operand list366has several advantages.  In particular, the debugging printer will print the367instruction like this:368 369.. code-block:: llvm370 371  %r3 = add %i1, %i2372 373Also if the first operand is a def, it is easier to `create instructions`_ whose374only def is the first operand.375 376.. _create instructions:377 378Using the ``MachineInstrBuilder.h`` functions379^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^380 381Machine instructions are created by using the ``BuildMI`` functions, located in382the ``include/llvm/CodeGen/MachineInstrBuilder.h`` file.  The ``BuildMI``383functions make it easy to build arbitrary machine instructions.  Usage of the384``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 destination409register), you must explicitly mark it as such:410 411.. code-block:: c++412 413  MI.addReg(Reg, RegState::Define);414 415Fixed (preassigned) registers416^^^^^^^^^^^^^^^^^^^^^^^^^^^^^417 418One important issue that the code generator needs to be aware of is the presence419of fixed registers.  In particular, there are often places in the instruction420stream where the register allocator *must* arrange for a particular value to be421in a particular register.  This can occur due to limitations of the instruction422set (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, the424instruction selector should emit code that copies a virtual register into or out425of a physical register when needed.426 427For example, consider this simple LLVM example:428 429.. code-block:: llvm430 431  define i32 @test(i32 %X, i32 %Y) {432    %Z = sdiv i32 %X, %Y433    ret i32 %Z434  }435 436The X86 instruction selector might produce this machine code for the ``div`` and437``ret``:438 439.. code-block:: text440 441  ;; Start of div442  %EAX = mov %reg1024           ;; Copy X (in reg1024) into EAX443  %reg1027 = sar %reg1024, 31444  %EDX = mov %reg1027           ;; Sign extend X into EDX445  idiv %reg1025                 ;; Divide by Y (in reg1025)446  %reg1026 = mov %EAX           ;; Read the result (Z) out of EAX447 448  ;; Start of ret449  %EAX = mov %reg1026           ;; 32-bit return value goes in EAX450  ret451 452By the end of code generation, the register allocator would coalesce the453registers and delete the resultant identity moves producing the following454code:455 456.. code-block:: text457 458  ;; X is in EAX, Y is in ECX459  mov %EAX, %EDX460  sar %EDX, 31461  idiv %ECX462  ret463 464This approach is extremely general (if it can handle the X86 architecture, it465can handle anything!) and allows all of the target-specific knowledge about the466instruction stream to be isolated in the instruction selector.  Note that467physical registers should have a short lifetime for good code generation, and468all physical registers are assumed dead on entry to and exit from basic blocks469(before register allocation).  Thus, if you need a value to be live across basic470block boundaries, it *must* live in a virtual register.471 472Call-clobbered registers473^^^^^^^^^^^^^^^^^^^^^^^^474 475Some machine instructions, like calls, clobber a large number of physical476registers.  Rather than adding ``<def,dead>`` operands for all of them, it is477possible to use an ``MO_RegisterMask`` operand instead.  The register mask478operand holds a bit mask of preserved registers, and everything else is479considered to be clobbered by the instruction.480 481Machine code in SSA form482^^^^^^^^^^^^^^^^^^^^^^^^483 484``MachineInstr``'s are initially selected in SSA-form, and are maintained in485SSA-form until register allocation happens.  For the most part, this is486trivially simple since LLVM is already in SSA form; LLVM PHI nodes become487machine code PHI nodes, and virtual registers are only allowed to have a single488definition.489 490After register allocation, machine code is no longer in SSA-form because there491are no virtual registers left in the code.492 493.. _MachineBasicBlock:494 495The ``MachineBasicBlock`` class496-------------------------------497 498The ``MachineBasicBlock`` class contains a list of machine instructions499(:raw-html:`<tt>` `MachineInstr`_ :raw-html:`</tt>` instances).  It roughly500corresponds to the LLVM code input to the instruction selector, but there can be501a one-to-many mapping (i.e., one LLVM basic block can map to multiple machine502basic blocks). The ``MachineBasicBlock`` class has a "``getBasicBlock``" method,503which returns the LLVM basic block that it comes from.504 505.. _MachineFunction:506 507The ``MachineFunction`` class508-----------------------------509 510The ``MachineFunction`` class contains a list of machine basic blocks511(:raw-html:`<tt>` `MachineBasicBlock`_ :raw-html:`</tt>` instances).  It512corresponds one-to-one with the LLVM function input to the instruction selector.513In addition to a list of basic blocks, the ``MachineFunction`` contains a514``MachineConstantPool``, a ``MachineFrameInfo``, a ``MachineFunctionInfo``, and515a ``MachineRegisterInfo``.  See ``include/llvm/CodeGen/MachineFunction.h`` for516more information.517 518``MachineInstr Bundles``519------------------------520 521LLVM code generator can model sequences of instructions as MachineInstr522bundles. A MI bundle can model a VLIW group / pack which contains an arbitrary523number of parallel instructions. It can also be used to model a sequential list524of instructions (potentially with data dependencies) that cannot be legally525separated (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 of566MachineBasicBlock and MachineInstr. All the MIs (including top level and nested567ones) are stored as sequential list of MIs. The "bundled" MIs are marked with568the 'InsideBundle' flag. A top-level MI with the special BUNDLE opcode is used569to represent the start of a bundle. It's legal to mix BUNDLE MIs with individual570MIs that are not inside bundles nor represent bundles.571 572MachineInstr passes should operate on a MI bundle as a single unit. Member573methods have been taught to correctly handle bundles and MIs inside bundles.574The MachineBasicBlock iterator has been modified to skip over bundled MIs to575enforce the bundle-as-a-single-unit concept. An alternative iterator576instr_iterator has been added to MachineBasicBlock to allow passes to iterate577over all of the MIs in a MachineBasicBlock, including those which are nested578inside bundles. The top-level BUNDLE instruction must have the correct set of579register MachineOperand's that represent the cumulative inputs and outputs of580the bundled MIs.581 582Packing / bundling of MachineInstrs for VLIW architectures should583generally be done as part of the register allocation super-pass. More584specifically, the pass which determines what MIs should be bundled585together should be done after code generator exits SSA form586(i.e., after two-address pass, PHI elimination, and copy coalescing).587Such bundles should be finalized (i.e., adding BUNDLE MIs and input and588output register MachineOperands) after virtual registers have been589rewritten into physical registers. This eliminates the need to add590virtual register operands to BUNDLE instructions which would591effectively double the virtual register def and use lists. Bundles may592use virtual registers and be formed in SSA form, but may not be593appropriate for all use cases.594 595.. _MC Layer:596 597The "MC" Layer598==============599 600The MC Layer is used to represent and process code at the raw machine code601level, devoid of "high level" information like "constant pools", "jump tables",602"global variables" or anything like that.  At this level, LLVM handles things603like label names, machine instructions, and sections in the object file.  The604code in this layer is used for a number of important purposes: the tail end of605the code generator uses it to write a ``.s`` or ``.o`` file, and it is also used by the606llvm-mc tool to implement standalone machine code assemblers and disassemblers.607 608This section describes some of the important classes.  There are also a number609of important subsystems that interact at this layer, they are described later in610this manual.611 612.. _MCStreamer:613 614The ``MCStreamer`` API615----------------------616 617MCStreamer is best thought of as an assembler API.  It is an abstract API which618is *implemented* in different ways (e.g., to output a ``.s`` file, output an ELF ``.o``619file, etc) but whose API corresponds directly to what you see in a ``.s`` file.620MCStreamer has one method per directive, such as EmitLabel, EmitSymbolAttribute,621switchSection, emitValue (for .byte, .word), etc, which directly correspond to622assembly level directives.  It also has an EmitInstruction method, which is used623to output an MCInst to the streamer.624 625This API is most important for two clients: the llvm-mc stand-alone assembler is626effectively a parser that parses a line, then invokes a method on MCStreamer. In627the code generator, the `Code Emission`_ phase of the code generator lowers628higher level LLVM IR and Machine* constructs down to the MC layer, emitting629directives through MCStreamer.630 631On the implementation side of MCStreamer, there are two major implementations:632one for writing out a ``.s`` file (MCAsmStreamer), and one for writing out a ``.o``633file (MCObjectStreamer).  MCAsmStreamer is a straightforward implementation634that prints out a directive for each method (e.g., ``EmitValue -> .byte``), but635MCObjectStreamer implements a full assembler.636 637For target-specific directives, the MCStreamer has a MCTargetStreamer instance.638Each target that needs it defines a class that inherits from it and is a lot639like MCStreamer itself: It has one method per directive and two classes that640inherit from it, a target object streamer and a target asm streamer. The target641asm streamer just prints it (``emitFnStart -> .fnstart``), and the object642streamer implements the assembler logic for it.643 644To make llvm use these classes, the target initialization must call645TargetRegistry::RegisterAsmStreamer and TargetRegistry::RegisterMCObjectStreamer646passing callbacks that allocate the corresponding target streamer and pass it647to createAsmStreamer or to the appropriate object streamer constructor.648 649The ``MCContext`` class650-----------------------651 652The MCContext class is the owner of a variety of uniqued data structures at the653MC layer, including symbols, sections, etc.  As such, this is the class that you654interact with to create symbols and sections.  This class can not be subclassed.655 656The ``MCSymbol`` class657----------------------658 659The MCSymbol class represents a symbol (aka label) in the assembly file.  There660are two interesting kinds of symbols: assembler temporary symbols, and normal661symbols.  Assembler temporary symbols are used and processed by the assembler662but are discarded when the object file is produced.  The distinction is usually663represented by adding a prefix to the label, for example "L" labels are664assembler temporary labels in MachO.665 666MCSymbols are created by MCContext and uniqued there.  This means that MCSymbols667can be compared for pointer equivalence to find out if they are the same symbol.668Note that pointer inequality does not guarantee the labels will end up at669different addresses though.  It's perfectly legal to output something like this670to the ``.s`` file:671 672::673 674  foo:675  bar:676    .byte 4677 678In this case, both the foo and bar symbols will have the same address.679 680The ``MCSection`` class681-----------------------682 683The ``MCSection`` class represents an object-file specific section. It is684subclassed by object file specific implementations (e.g., ``MCSectionMachO``,685``MCSectionCOFF``, ``MCSectionELF``) and these are created and uniqued by686MCContext.  The MCStreamer has a notion of the current section, which can be687changed with the SwitchToSection method (which corresponds to a ".section"688directive in a ``.s`` file).689 690.. _MCInst:691 692The ``MCInst`` class693--------------------694 695The ``MCInst`` class is a target-independent representation of an instruction.696It is a simple class (much more so than `MachineInstr`_) that holds a697target-specific opcode and a vector of MCOperands.  MCOperand, in turn, is a698simple discriminated union of three cases: 1) a simple immediate, 2) a target699register ID, 3) a symbolic expression (e.g., "``Lfoo-Lbar+42``") as an MCExpr.700 701MCInst is the common currency used to represent machine instructions at the MC702layer.  It is the type used by the instruction encoder, the instruction printer,703and the type generated by the assembly parser and disassembler.704 705.. _ObjectFormats:706 707Object File Format708------------------709 710The MC layer's object writers support a variety of object formats. Because of711target-specific aspects of object formats each target only supports a subset of712the formats supported by the MC layer. Most targets support emitting ELF713objects. Other vendor-specific objects are generally supported only on targets714that are supported by that vendor (i.e., MachO is only supported on targets715supported by Darwin, and XCOFF is only supported on targets that support AIX).716Additionally some targets have their own object formats (i.e., DirectX, SPIR-V717and WebAssembly).718 719The table below captures a snapshot of object file support in LLVM:720 721  .. table:: Object File Formats722 723     ================== ========================================================724     Format              Supported Targets725     ================== ========================================================726     ``COFF``            AArch64, ARM, X86727     ``DXContainer``     DirectX728     ``ELF``             AArch64, AMDGPU, ARM, AVR, BPF, CSKY, Hexagon, Lanai, LoongArch, M86k, MSP430, MIPS, PowerPC, RISCV, SPARC, SystemZ, VE, X86729     ``GOFF``            SystemZ730     ``MachO``           AArch64, ARM, X86731     ``SPIR-V``          SPIRV732     ``WASM``            WebAssembly733     ``XCOFF``           PowerPC734     ================== ========================================================735 736.. _Target-independent algorithms:737.. _code generation algorithm:738 739Target-independent code generation algorithms740=============================================741 742This section documents the phases described in the `high-level design of the743code generator`_.  It explains how they work and some of the rationale behind744their design.745 746.. _Instruction Selection:747.. _instruction selection section:748 749Instruction Selection750---------------------751 752Instruction Selection is the process of translating LLVM code presented to the753code generator into target-specific machine instructions.  There are several754well-known ways to do this in the literature.  LLVM uses a SelectionDAG based755instruction selector.756 757Portions of the DAG instruction selector are generated from the target758description (``*.td``) files.  Our goal is for the entire instruction selector759to be generated from these ``.td`` files, though currently there are still760things that require custom C++ code.761 762`GlobalISel <https://llvm.org/docs/GlobalISel/index.html>`_ is another763instruction selection framework.764 765.. _SelectionDAG:766 767Introduction to SelectionDAGs768^^^^^^^^^^^^^^^^^^^^^^^^^^^^^769 770The SelectionDAG provides an abstraction for code representation in a way that771is amenable to instruction selection using automatic techniques772(e.g., dynamic-programming based optimal pattern matching selectors). It is also773well-suited to other phases of code generation; in particular, instruction774scheduling (SelectionDAG's are very close to scheduling DAGs post-selection).775Additionally, the SelectionDAG provides a host representation where a large776variety of very-low-level (but target-independent) `optimizations`_ may be777performed; ones which require extensive information about the instructions778efficiently supported by the target.779 780The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the781``SDNode`` class.  The primary payload of the ``SDNode`` is its operation code782(Opcode) that indicates what operation the node performs and the operands to the783operation.  The various operation node types are described at the top of the784``include/llvm/CodeGen/ISDOpcodes.h`` file.785 786Although most operations define a single value, each node in the graph may787define multiple values.  For example, a combined div/rem operation will define788both the dividend and the remainder. Many other situations require multiple789values as well.  Each node also has some number of operands, which are edges to790the node defining the used value.  Because nodes may define multiple values,791edges are represented by instances of the ``SDValue`` class, which is a792``<SDNode, unsigned>`` pair, indicating the node and result value being used,793respectively.  Each value produced by an ``SDNode`` has an associated ``MVT``794(Machine Value Type) indicating what the type of the value is.795 796SelectionDAGs contain two different kinds of values: those that represent data797flow and those that represent control flow dependencies.  Data values are simple798edges with an integer or floating point value type.  Control edges are799represented as "chain" edges which are of type ``MVT::Other``.  These edges800provide an ordering between nodes that have side effects (such as loads, stores,801calls, returns, etc).  All nodes that have side effects should take a token802chain as input and produce a new one as output.  By convention, token chain803inputs are always operand #0, and chain results are always the last value804produced by an operation. However, after instruction selection, the805machine nodes have their chain after the instruction's operands, and806may be followed by glue nodes.807 808A SelectionDAG has designated "Entry" and "Root" nodes.  The Entry node is809always a marker node with an Opcode of ``ISD::EntryToken``.  The Root node is810the final side-effecting node in the token chain. For example, in a single basic811block function it would be the return node.812 813One important concept for SelectionDAGs is the notion of a "legal" vs.814"illegal" DAG.  A legal DAG for a target is one that only uses supported815operations and supported types.  On a 32-bit PowerPC, for example, a DAG with a816value of type i1, i8, i16, or i64 would be illegal, as would a DAG that uses a817SREM or UREM operation.  The `legalize types`_ and `legalize operations`_ phases818are responsible for turning an illegal DAG into a legal DAG.819 820.. _SelectionDAG-Process:821 822SelectionDAG Instruction Selection Process823^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^824 825SelectionDAG-based instruction selection consists of the following steps:826 827#. `Build initial DAG`_ --- This stage performs a simple translation from the828   input LLVM code to an illegal SelectionDAG.829 830#. `Optimize SelectionDAG`_ --- This stage performs simple optimizations on the831   SelectionDAG to simplify it, and recognize meta instructions (like rotates832   and ``div``/``rem`` pairs) for targets that support these meta operations.833   This makes the resultant code more efficient and the `select instructions834   from DAG`_ phase (below) simpler.835 836#. `Legalize SelectionDAG Types`_ --- This stage transforms SelectionDAG nodes837   to eliminate any types that are unsupported on the target.838 839#. `Optimize SelectionDAG`_ --- The SelectionDAG optimizer is run to clean up840   redundancies exposed by type legalization.841 842#. `Legalize SelectionDAG Ops`_ --- This stage transforms SelectionDAG nodes to843   eliminate any operations that are unsupported on the target.844 845#. `Optimize SelectionDAG`_ --- The SelectionDAG optimizer is run to eliminate846   inefficiencies introduced by operation legalization.847 848#. `Select instructions from DAG`_ --- Finally, the target instruction selector849   matches the DAG operations to target instructions.  This process translates850   the target-independent input DAG into another DAG of target instructions.851 852#. `SelectionDAG Scheduling and Formation`_ --- The last phase assigns a linear853   order to the instructions in the target-instruction DAG and emits them into854   the MachineFunction being compiled.  This step uses traditional prepass855   scheduling techniques.856 857After all of these steps are complete, the SelectionDAG is destroyed and the858rest of the code generation passes are run.859 860One of the most common ways to debug these steps is using ``-debug-only=isel``,861which prints out the DAG, along with other information like debug info,862after each of these steps. Alternatively, ``-debug-only=isel-dump`` shows only863the DAG dumps, but the results can be filtered by function names using864``-filter-print-funcs=<function names>``.865 866One great way to visualize what is going on here is to take advantage of a few867LLC command line options.  The following options pop up a window displaying the868SelectionDAG at specific times (if you only get errors printed to the console869while using this, you probably `need to configure your870system <ProgrammersManual.html#viewing-graphs-while-debugging-code>`_ to add support for it).871 872* ``-view-dag-combine1-dags`` displays the DAG after being built, before the873  first optimization pass.874 875* ``-view-legalize-dags`` displays the DAG before Legalization.876 877* ``-view-dag-combine2-dags`` displays the DAG before the second optimization878  pass.879 880* ``-view-isel-dags`` displays the DAG before the Select phase.881 882* ``-view-sched-dags`` displays the DAG before Scheduling.883 884The ``-view-sunit-dags`` displays the Scheduler's dependency graph.  This graph885is based on the final SelectionDAG, with nodes that must be scheduled together886bundled into a single scheduling-unit node, and with immediate operands and887other nodes that aren't relevant for scheduling omitted.888 889The option ``-filter-view-dags`` allows to select the name of the basic block890that you are interested in visualizing and filters all the previous891``view-*-dags`` options.892 893.. _Build initial DAG:894 895Initial SelectionDAG Construction896^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^897 898The initial SelectionDAG is na\ :raw-html:`&iuml;`\ vely peephole expanded from899the LLVM input by the ``SelectionDAGBuilder`` class.  The intent of this pass900is to expose as much low-level, target-specific details to the SelectionDAG as901possible.  This pass is mostly hard-coded (e.g., an LLVM ``add`` turns into an902``SDNode add`` while a ``getelementptr`` is expanded into the obvious903arithmetic). This pass requires target-specific hooks to lower calls, returns,904varargs, etc.  For these features, the :raw-html:`<tt>` `TargetLowering`_905:raw-html:`</tt>` interface is used.906 907.. _legalize types:908.. _Legalize SelectionDAG Types:909.. _Legalize SelectionDAG Ops:910 911SelectionDAG LegalizeTypes Phase912^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^913 914The Legalize phase is in charge of converting a DAG to only use the types that915are natively supported by the target.916 917There are two main ways of converting values of unsupported scalar types to918values of supported types: converting small types to larger types ("promoting"),919and breaking up large integer types into smaller ones ("expanding").  For920example, a target might require that all f32 values are promoted to f64 and that921all i1/i8/i16 values are promoted to i32.  The same target might require that922all i64 values be expanded into pairs of i32 values.  These changes can insert923sign and zero extensions as needed to make sure that the final code has the same924behavior as the input.925 926There are two main ways of converting values of unsupported vector types to927value of supported types: splitting vector types, multiple times if necessary,928until a legal type is found, and extending vector types by adding elements to929the end to round them out to legal types ("widening").  If a vector gets split930all the way down to single-element parts with no supported vector type being931found, the elements are converted to scalars ("scalarizing").932 933A target implementation tells the legalizer which types are supported (and which934register class to use for them) by calling the ``addRegisterClass`` method in935its ``TargetLowering`` constructor.936 937.. _legalize operations:938.. _Legalizer:939 940SelectionDAG Legalize Phase941^^^^^^^^^^^^^^^^^^^^^^^^^^^942 943The Legalize phase is in charge of converting a DAG to only use the operations944that are natively supported by the target.945 946Targets often have weird constraints, such as not supporting every operation on947every supported data type (e.g., X86 does not support byte conditional moves and948PowerPC does not support sign-extending loads from a 16-bit memory location).949Legalize takes care of this by open-coding another sequence of operations to950emulate the operation ("expansion"), by promoting one type to a larger type that951supports the operation ("promotion"), or by using a target-specific hook to952implement the legalization ("custom").953 954A target implementation tells the legalizer which operations are not supported955(and which of the above three actions to take) by calling the956``setOperationAction`` method in its ``TargetLowering`` constructor.957 958If a target has legal vector types, it is expected to produce efficient machine959code for common forms of the shufflevector IR instruction using those types.960This may require custom legalization for SelectionDAG vector operations that961are created from the shufflevector IR. The shufflevector forms that should be962handled include:963 964* Vector select --- Each element of the vector is chosen from either of the965  corresponding elements of the 2 input vectors. This operation may also be966  known as a "blend" or "bitwise select" in target assembly. This type of shuffle967  maps directly to the ``shuffle_vector`` SelectionDAG node.968 969* Insert subvector --- A vector is placed into a longer vector type starting970  at index 0. This type of shuffle maps directly to the ``insert_subvector``971  SelectionDAG node with the ``index`` operand set to 0.972 973* Extract subvector --- A vector is pulled from a longer vector type starting974  at index 0. This type of shuffle maps directly to the ``extract_subvector``975  SelectionDAG node with the ``index`` operand set to 0.976 977* Splat --- All elements of the vector have identical scalar elements. This978  operation may also be known as a "broadcast" or "duplicate" in target assembly.979  The shufflevector IR instruction may change the vector length, so this operation980  may map to multiple SelectionDAG nodes including ``shuffle_vector``,981  ``concat_vectors``, ``insert_subvector``, and ``extract_subvector``.982 983Prior to the existence of the Legalize passes, we required that every target984`selector`_ supported and handled every operator and type even if they are not985natively supported.  The introduction of the Legalize phases allows all of the986canonicalization patterns to be shared across targets, and makes it very easy to987optimize the canonicalized code because it is still in the form of a DAG.988 989.. _optimizations:990.. _Optimize SelectionDAG:991.. _selector:992 993SelectionDAG Optimization Phase: the DAG Combiner994^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^995 996The SelectionDAG optimization phase is run multiple times for code generation,997immediately after the DAG is built and once after each legalization.  The first998run of the pass allows the initial code to be cleaned up (e.g., performing999optimizations that depend on knowing that the operators have restricted type1000inputs).  Subsequent runs of the pass clean up the messy code generated by the1001Legalize passes, which allows Legalize to be very simple (it can focus on making1002code legal instead of focusing on generating *good* and legal code).1003 1004One important class of optimizations performed is optimizing inserted sign and1005zero extension instructions.  We currently use ad-hoc techniques, but could move1006to more rigorous techniques in the future.  Here are some good papers on the1007subject:1008 1009"`Widening integer arithmetic <http://www.eecs.harvard.edu/~nr/pubs/widen-abstract.html>`_" :raw-html:`<br>`1010Kevin Redwine and Norman Ramsey :raw-html:`<br>`1011International Conference on Compiler Construction (CC) 20041012 1013"`Effective sign extension elimination <http://portal.acm.org/citation.cfm?doid=512529.512552>`_"  :raw-html:`<br>`1014Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani :raw-html:`<br>`1015Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design1016and Implementation.1017 1018.. _Select instructions from DAG:1019 1020SelectionDAG Select Phase1021^^^^^^^^^^^^^^^^^^^^^^^^^1022 1023The Select phase is the bulk of the target-specific code for instruction1024selection.  This phase takes a legal SelectionDAG as input, pattern matches the1025instructions supported by the target to this DAG, and produces a new DAG of1026target code.  For example, consider the following LLVM fragment:1027 1028.. code-block:: llvm1029 1030  %t1 = fadd float %W, %X1031  %t2 = fmul float %t1, %Y1032  %t3 = fadd float %t2, %Z1033 1034This LLVM code corresponds to a SelectionDAG that looks basically like this:1035 1036.. code-block:: text1037 1038  (fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)1039 1040If a target supports floating point multiply-and-add (FMA) operations, one of1041the adds can be merged with the multiply.  On the PowerPC, for example, the1042output of the instruction selector might look like this DAG:1043 1044::1045 1046  (FMADDS (FADDS W, X), Y, Z)1047 1048The ``FMADDS`` instruction is a ternary instruction that multiplies its first1049two operands and adds the third (as single-precision floating-point numbers).1050The ``FADDS`` instruction is a simple binary single-precision add instruction.1051To perform this pattern match, the PowerPC backend includes the following1052instruction definitions:1053 1054.. code-block:: text1055  :emphasize-lines: 4-5,91056 1057  def FMADDS : AForm_1<59, 29,1058                      (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),1059                      "fmadds $FRT, $FRA, $FRC, $FRB",1060                      [(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),1061                                             F4RC:$FRB))]>;1062  def FADDS : AForm_2<59, 21,1063                      (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),1064                      "fadds $FRT, $FRA, $FRB",1065                      [(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))]>;1066 1067The highlighted portion of the instruction definitions indicates the pattern1068used to match the instructions. The DAG operators (like ``fmul``/``fadd``)1069are defined in the ``include/llvm/Target/TargetSelectionDAG.td`` file.1070"``F4RC``" is the register class of the input and result values.1071 1072The TableGen DAG instruction selector generator reads the instruction patterns1073in the ``.td`` file and automatically builds parts of the pattern matching code1074for your target.  It has the following strengths:1075 1076* At compiler-compile time, it analyzes your instruction patterns and tells you1077  if your patterns make sense or not.1078 1079* It can handle arbitrary constraints on operands for the pattern match.  In1080  particular, it is straightforward to say things like "match any immediate1081  that is a 13-bit sign-extended value".  For examples, see the ``immSExt16``1082  and related ``tblgen`` classes in the PowerPC backend.1083 1084* It knows several important identities for the patterns defined.  For example,1085  it knows that addition is commutative, so it allows the ``FMADDS`` pattern1086  above to match "``(fadd X, (fmul Y, Z))``" as well as "``(fadd (fmul X, Y),1087  Z)``", without the target author having to specially handle this case.1088 1089* It has a full-featured type-inferencing system.  In particular, you should1090  rarely have to explicitly tell the system what type parts of your patterns1091  are.  In the ``FMADDS`` case above, we didn't have to tell ``tblgen`` that all1092  of the nodes in the pattern are of type 'f32'.  It was able to infer and1093  propagate this knowledge from the fact that ``F4RC`` has type 'f32'.1094 1095* Targets can define their own (and rely on built-in) "pattern fragments".1096  Pattern fragments are chunks of reusable patterns that get inlined into your1097  patterns during compiler-compile time.  For example, the integer "``(not1098  x)``" operation is actually defined as a pattern fragment that expands as1099  "``(xor x, -1)``", since the SelectionDAG does not have a native '``not``'1100  operation.  Targets can define their own short-hand fragments as they see fit.1101  See the definition of '``not``' and '``ineg``' for examples.1102 1103* In addition to instructions, targets can specify arbitrary patterns that map1104  to one or more instructions using the 'Pat' class.  For example, the PowerPC1105  has no way to load an arbitrary integer immediate into a register in one1106  instruction. To tell tblgen how to do this, it defines:1107 1108  ::1109 1110    // Arbitrary immediate support.  Implement in terms of LIS/ORI.1111    def : Pat<(i32 imm:$imm),1112              (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;1113 1114  If none of the single-instruction patterns for loading an immediate into a1115  register match, this will be used.  This rule says "match an arbitrary i321116  immediate, turning it into an ``ORI`` ('or a 16-bit immediate') and an ``LIS``1117  ('load 16-bit immediate, where the immediate is shifted to the left 16 bits')1118  instruction".  To make this work, the ``LO16``/``HI16`` node transformations1119  are used to manipulate the input immediate (in this case, take the high or low1120  16-bits of the immediate).1121 1122* When using the 'Pat' class to map a pattern to an instruction that has one1123  or more complex operands (like e.g., `X86 addressing mode`_), the pattern may1124  either specify the operand as a whole using a ``ComplexPattern``, or else it1125  may specify the components of the complex operand separately.  The latter is1126  done e.g., for pre-increment instructions by the PowerPC back end:1127 1128  ::1129 1130    def STWU  : DForm_1<37, (outs ptr_rc:$ea_res), (ins GPRC:$rS, memri:$dst),1131                    "stwu $rS, $dst", LdStStoreUpd, []>,1132                    RegConstraint<"$dst.reg = $ea_res">;1133 1134    def : Pat<(pre_store GPRC:$rS, ptr_rc:$ptrreg, iaddroff:$ptroff),1135              (STWU GPRC:$rS, iaddroff:$ptroff, ptr_rc:$ptrreg)>;1136 1137  Here, the pair of ``ptroff`` and ``ptrreg`` operands is matched onto the1138  complex operand ``dst`` of class ``memri`` in the ``STWU`` instruction.1139 1140* While the system does automate a lot, it still allows you to write custom C++1141  code to match special cases if there is something that is hard to1142  express.1143 1144While it has many strengths, the system currently has some limitations,1145primarily because it is a work in progress and is not yet finished:1146 1147* Overall, there is no way to define or match SelectionDAG nodes that define1148  multiple values (e.g., ``SMUL_LOHI``, ``LOAD``, ``CALL``, etc).  This is the1149  biggest reason that you currently still *have to* write custom C++ code1150  for your instruction selector.1151 1152* There is no great way to support matching complex addressing modes yet.  In1153  the future, we will extend pattern fragments to allow them to define multiple1154  values (e.g., the four operands of the `X86 addressing mode`_, which are1155  currently matched with custom C++ code).  In addition, we'll extend fragments1156  so that a fragment can match multiple different patterns.1157 1158* We don't automatically infer flags like ``isStore``/``isLoad`` yet.1159 1160* We don't automatically generate the set of supported registers and operations1161  for the `Legalizer`_ yet.1162 1163* We don't have a way of tying in custom legalized nodes yet.1164 1165Despite these limitations, the instruction selector generator is still quite1166useful for most of the binary and logical operations in typical instruction1167sets.  If you run into any problems or can't figure out how to do something,1168please let Chris know!1169 1170.. _Scheduling and Formation:1171.. _SelectionDAG Scheduling and Formation:1172 1173SelectionDAG Scheduling and Formation Phase1174^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1175 1176The scheduling phase takes the DAG of target instructions from the selection1177phase and assigns an order.  The scheduler can pick an order depending on1178various constraints of the machines (i.e., order for minimal register pressure or1179try to cover instruction latencies).  Once an order is established, the DAG is1180converted to a list of :raw-html:`<tt>` `MachineInstr`_\s :raw-html:`</tt>` and1181the SelectionDAG is destroyed.1182 1183Note that this phase is logically separate from the instruction selection phase,1184but is tied to it closely in the code because it operates on SelectionDAGs.1185 1186Future directions for the SelectionDAG1187^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1188 1189#. Optional function-at-a-time selection.1190 1191#. Auto-generate entire selector from ``.td`` file.1192 1193.. _SSA-based Machine Code Optimizations:1194 1195SSA-based Machine Code Optimizations1196------------------------------------1197 1198To Be Written1199 1200Live Intervals1201--------------1202 1203Live Intervals are the ranges (intervals) where a variable is *live*.  They are1204used by some `register allocator`_ passes to determine if two or more virtual1205registers which require the same physical register are live at the same point in1206the program (i.e., they conflict).  When this situation occurs, one virtual1207register must be *spilled*.1208 1209Live Variable Analysis1210^^^^^^^^^^^^^^^^^^^^^^1211 1212The first step in determining the live intervals of variables is to calculate1213the set of registers that are immediately dead after the instruction (i.e., the1214instruction calculates the value, but it is never used) and the set of registers1215that are used by the instruction, but are never used after the instruction1216(i.e., they are killed). Live variable information is computed for1217each *virtual* register and *register allocatable* physical register1218in the function.  This is done in a very efficient manner because it uses SSA to1219sparsely compute lifetime information for virtual registers (which are in SSA1220form) and only has to track physical registers within a block.  Before register1221allocation, LLVM can assume that physical registers are only live within a1222single basic block.  This allows it to do a single, local analysis to resolve1223physical register lifetimes within each basic block. If a physical register is1224not register allocatable (e.g., a stack pointer or condition codes), it is not1225tracked.1226 1227Physical registers may be live in to or out of a function. Live in values are1228typically arguments in registers. Live out values are typically return values in1229registers. Live in values are marked as such, and are given a dummy "defining"1230instruction during live intervals analysis. If the last basic block of a1231function is a ``return``, then it's marked as using all live out values in the1232function.1233 1234``PHI`` nodes need to be handled specially, because the calculation of the live1235variable information from a depth first traversal of the CFG of the function1236won't guarantee that a virtual register used by the ``PHI`` node is defined1237before it's used. When a ``PHI`` node is encountered, only the definition is1238handled, because the uses will be handled in other basic blocks.1239 1240For each ``PHI`` node of the current basic block, we simulate an assignment at1241the end of the current basic block and traverse the successor basic blocks. If a1242successor basic block has a ``PHI`` node and one of the ``PHI`` node's operands1243is coming from the current basic block, then the variable is marked as *alive*1244within the current basic block and all of its predecessor basic blocks, until1245the basic block with the defining instruction is encountered.1246 1247Live Intervals Analysis1248^^^^^^^^^^^^^^^^^^^^^^^1249 1250We now have the information available to perform the live intervals analysis and1251build the live intervals themselves.  We start off by numbering the basic blocks1252and machine instructions.  We then handle the "live-in" values.  These are in1253physical registers, so the physical register is assumed to be killed by the end1254of the basic block.  Live intervals for virtual registers are computed for some1255ordering of the machine instructions ``[1, N]``.  A live interval is an interval1256``[i, j)``, where ``1 >= i >= j > N``, for which a variable is live.1257 1258.. note::1259  More to come...1260 1261.. _Register Allocation:1262.. _register allocator:1263 1264Register Allocation1265-------------------1266 1267The *Register Allocation problem* consists in mapping a program1268:raw-html:`<b><tt>` P\ :sub:`v`\ :raw-html:`</tt></b>`, that can use an unbounded1269number of virtual registers, to a program :raw-html:`<b><tt>` P\ :sub:`p`\1270:raw-html:`</tt></b>` that contains a finite (possibly small) number of physical1271registers. Each target architecture has a different number of physical1272registers. If the number of physical registers is not enough to accommodate all1273the virtual registers, some of them will have to be mapped into memory. These1274virtuals are called *spilled virtuals*.1275 1276How registers are represented in LLVM1277^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1278 1279In LLVM, physical registers are denoted by integer numbers that normally range1280from 1 to 1023. To see how this numbering is defined for a particular1281architecture, you can read the ``GenRegisterNames.inc`` file for that1282architecture. For instance, by inspecting1283``lib/Target/X86/X86GenRegisterInfo.inc`` we see that the 32-bit register1284``EAX`` is denoted by 43, and the MMX register ``MM0`` is mapped to 65.1285 1286Some architectures contain registers that share the same physical location. A1287notable example is the X86 platform. For instance, in the X86 architecture, the1288registers ``EAX``, ``AX`` and ``AL`` share the first eight bits. These physical1289registers are marked as *aliased* in LLVM. Given a particular architecture, you1290can check which registers are aliased by inspecting its ``RegisterInfo.td``1291file. Moreover, the class ``MCRegAliasIterator`` enumerates all the physical1292registers aliased to a register.1293 1294Physical registers, in LLVM, are grouped in *Register Classes*.  Elements in the1295same register class are functionally equivalent, and can be interchangeably1296used. Each virtual register can only be mapped to physical registers of a1297particular class. For instance, in the X86 architecture, some virtuals can only1298be allocated to 8-bit registers.  A register class is described by1299``TargetRegisterClass`` objects.  To discover if a virtual register is1300compatible with a given physical, this code can be used:1301 1302.. code-block:: c++1303 1304  bool RegMapping_Fer::compatible_class(MachineFunction &mf,1305                                        unsigned v_reg,1306                                        unsigned p_reg) {1307    assert(TargetRegisterInfo::isPhysicalRegister(p_reg) &&1308           "Target register must be physical");1309    const TargetRegisterClass *trc = mf.getRegInfo().getRegClass(v_reg);1310    return trc->contains(p_reg);1311  }1312 1313Sometimes, mostly for debugging purposes, it is useful to change the number of1314physical registers available in the target architecture. This must be done1315statically, inside the ``TargetRegisterInfo.td`` file. Just ``grep`` for1316``RegisterClass``, the last parameter of which is a list of registers. Just1317commenting some out is one simple way to avoid them being used. A more polite1318way is to explicitly exclude some registers from the *allocation order*. See the1319definition of the ``GR8`` register class in1320``lib/Target/X86/X86RegisterInfo.td`` for an example of this.1321 1322Virtual registers are also denoted by integer numbers. Contrary to physical1323registers, different virtual registers never share the same number. Whereas1324physical registers are statically defined in a ``TargetRegisterInfo.td`` file1325and cannot be created by the application developer, that is not the case with1326virtual registers. In order to create new virtual registers, use the method1327``MachineRegisterInfo::createVirtualRegister()``. This method will return a new1328virtual register. Use an ``IndexedMap<Foo, VirtReg2IndexFunctor>`` to hold1329information per virtual register. If you need to enumerate all virtual1330registers, use the function ``TargetRegisterInfo::index2VirtReg()`` to find the1331virtual register numbers:1332 1333.. code-block:: c++1334 1335    for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {1336      unsigned VirtReg = TargetRegisterInfo::index2VirtReg(i);1337      stuff(VirtReg);1338    }1339 1340Before register allocation, the operands of an instruction are mostly virtual1341registers, although physical registers may also be used. In order to check if a1342given machine operand is a register, use the boolean function1343``MachineOperand::isRegister()``. To obtain the integer code of a register, use1344``MachineOperand::getReg()``. An instruction may define or use a register. For1345instance, ``ADD reg:1026 := reg:1025 reg:1024`` defines the registers 1024, and1346uses registers 1025 and 1026. Given a register operand, the method1347``MachineOperand::isUse()`` informs if that register is being used by the1348instruction. The method ``MachineOperand::isDef()`` informs if that registers is1349being defined.1350 1351We will call physical registers present in the LLVM bitcode before register1352allocation *pre-colored registers*. Pre-colored registers are used in many1353different situations, for instance, to pass parameters of functions calls, and1354to store results of particular instructions. There are two types of pre-colored1355registers: the ones *implicitly* defined, and those *explicitly*1356defined. Explicitly defined registers are normal operands, and can be accessed1357with ``MachineInstr::getOperand(int)::getReg()``.  In order to check which1358registers are implicitly defined by an instruction, use the1359``TargetInstrInfo::get(opcode)::ImplicitDefs``, where ``opcode`` is the opcode1360of the target instruction. One important difference between explicit and1361implicit physical registers is that the latter are defined statically for each1362instruction, whereas the former may vary depending on the program being1363compiled. For example, an instruction that represents a function call will1364always implicitly define or use the same set of physical registers. To read the1365registers implicitly used by an instruction, use1366``TargetInstrInfo::get(opcode)::ImplicitUses``. Pre-colored registers impose1367constraints on any register allocation algorithm. The register allocator must1368make sure that none of them are overwritten by the values of virtual registers1369while still alive.1370 1371Mapping virtual registers to physical registers1372^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1373 1374There are two ways to map virtual registers to physical registers (or to memory1375slots). The first way, that we will call *direct mapping*, is based on the use1376of methods of the classes ``TargetRegisterInfo``, and ``MachineOperand``. The1377second way, that we will call *indirect mapping*, relies on the ``VirtRegMap``1378class in order to insert loads and stores sending and getting values to and from1379memory.1380 1381The direct mapping provides more flexibility to the developer of the register1382allocator; however, it is more error prone, and demands more implementation1383work.  Basically, the programmer will have to specify where load and store1384instructions should be inserted in the target function being compiled in order1385to get and store values in memory. To assign a physical register to a virtual1386register present in a given operand, use ``MachineOperand::setReg(p_reg)``. To1387insert a store instruction, use ``TargetInstrInfo::storeRegToStackSlot(...)``,1388and to insert a load instruction, use ``TargetInstrInfo::loadRegFromStackSlot``.1389 1390The indirect mapping shields the application developer from the complexities of1391inserting load and store instructions. In order to map a virtual register to a1392physical one, use ``VirtRegMap::assignVirt2Phys(vreg, preg)``.  In order to map1393a certain virtual register to memory, use1394``VirtRegMap::assignVirt2StackSlot(vreg)``. This method will return the stack1395slot where ``vreg``'s value will be located.  If it is necessary to map another1396virtual register to the same stack slot, use1397``VirtRegMap::assignVirt2StackSlot(vreg, stack_location)``. One important point1398to consider when using the indirect mapping, is that even if a virtual register1399is mapped to memory, it still needs to be mapped to a physical register. This1400physical register is the location where the virtual register is supposed to be1401found before being stored or after being reloaded.1402 1403If the indirect strategy is used, after all the virtual registers have been1404mapped to physical registers or stack slots, it is necessary to use a spiller1405object to place load and store instructions in the code. Every virtual that has1406been mapped to a stack slot will be stored to memory after being defined and will1407be loaded before being used. The implementation of the spiller tries to recycle1408load/store instructions, avoiding unnecessary instructions. For an example of1409how to invoke the spiller, see ``RegAllocLinearScan::runOnMachineFunction`` in1410``lib/CodeGen/RegAllocLinearScan.cpp``.1411 1412Handling two address instructions1413^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1414 1415With very rare exceptions (e.g., function calls), the LLVM machine code1416instructions are three address instructions. That is, each instruction is1417expected to define at most one register, and to use at most two registers.1418However, some architectures use two address instructions. In this case, the1419defined register is also one of the used registers. For instance, an instruction1420such as ``ADD %EAX, %EBX``, in X86 is actually equivalent to ``%EAX = %EAX +1421%EBX``.1422 1423In order to produce correct code, LLVM must convert three address instructions1424that represent two address instructions into true two address instructions. LLVM1425provides the pass ``TwoAddressInstructionPass`` for this specific purpose. It1426must be run before register allocation takes place. After its execution, the1427resulting code may no longer be in SSA form. This happens, for instance, in1428situations where an instruction such as ``%a = ADD %b %c`` is converted to two1429instructions such as:1430 1431::1432 1433  %a = MOVE %b1434  %a = ADD %a %c1435 1436Notice that, internally, the second instruction is represented as ``ADD1437%a[def/use] %c``. I.e., the register operand ``%a`` is both used and defined by1438the instruction.1439 1440The SSA deconstruction phase1441^^^^^^^^^^^^^^^^^^^^^^^^^^^^1442 1443An important transformation that happens during register allocation is called1444the *SSA Deconstruction Phase*. The SSA form simplifies many analyses that are1445performed on the control flow graph of programs. However, traditional1446instruction sets do not implement PHI instructions. Thus, in order to generate1447executable code, compilers must replace PHI instructions with other instructions1448that preserve their semantics.1449 1450There are many ways in which PHI instructions can safely be removed from the1451target code. The most traditional PHI deconstruction algorithm replaces PHI1452instructions with copy instructions. That is the strategy adopted by LLVM. The1453SSA deconstruction algorithm is implemented in1454``lib/CodeGen/PHIElimination.cpp``. In order to invoke this pass, the identifier1455``PHIEliminationID`` must be marked as required in the code of the register1456allocator.1457 1458Instruction folding1459^^^^^^^^^^^^^^^^^^^1460 1461*Instruction folding* is an optimization performed during register allocation1462that removes unnecessary copy instructions. For instance, a sequence of1463instructions such as:1464 1465::1466 1467  %EBX = LOAD %mem_address1468  %EAX = COPY %EBX1469 1470can be safely substituted by the single instruction:1471 1472::1473 1474  %EAX = LOAD %mem_address1475 1476Instructions can be folded with the1477``TargetRegisterInfo::foldMemoryOperand(...)`` method. Care must be taken when1478folding instructions; a folded instruction can be quite different from the1479original instruction. See ``LiveIntervals::addIntervalsForSpills`` in1480``lib/CodeGen/LiveIntervalAnalysis.cpp`` for an example of its use.1481 1482Built in register allocators1483^^^^^^^^^^^^^^^^^^^^^^^^^^^^1484 1485The LLVM infrastructure provides the application developer with three different1486register allocators:1487 1488* *Fast* --- This register allocator is the default for debug builds. It1489  allocates registers on a basic block level, attempting to keep values in1490  registers and reusing registers as appropriate.1491 1492* *Basic* --- This is an incremental approach to register allocation. Live1493  ranges are assigned to registers one at a time in an order that is driven by1494  heuristics. Since code can be rewritten on-the-fly during allocation, this1495  framework allows interesting allocators to be developed as extensions. It is1496  not itself a production register allocator but is a potentially useful1497  stand-alone mode for triaging bugs and as a performance baseline.1498 1499* *Greedy* --- *The default allocator*. This is a highly tuned implementation of1500  the *Basic* allocator that incorporates global live range splitting. This1501  allocator works hard to minimize the cost of spill code.1502 1503* *PBQP* --- A Partitioned Boolean Quadratic Programming (PBQP) based register1504  allocator. This allocator works by constructing a PBQP problem representing1505  the register allocation problem under consideration, solving this using a PBQP1506  solver, and mapping the solution back to a register assignment.1507 1508The type of register allocator used in ``llc`` can be chosen with the command1509line option ``-regalloc=...``:1510 1511.. code-block:: bash1512 1513  $ llc -regalloc=linearscan file.bc -o ln.s1514  $ llc -regalloc=fast file.bc -o fa.s1515  $ llc -regalloc=pbqp file.bc -o pbqp.s1516 1517.. _Prolog/Epilog Code Insertion:1518 1519Prolog/Epilog Code Insertion1520----------------------------1521 1522.. note::1523 1524  To Be Written1525 1526Compact Unwind1527--------------1528 1529Throwing an exception requires *unwinding* out of a function. The information on1530how to unwind a given function is traditionally expressed in DWARF unwind1531(a.k.a. frame) info. But that format was originally developed for debuggers to1532backtrace, and each Frame Description Entry (FDE) requires ~20-30 bytes per1533function. There is also the cost of mapping from an address in a function to the1534corresponding FDE at runtime. An alternative unwind encoding is called *compact1535unwind* and requires just 4-bytes per function.1536 1537The compact unwind encoding is a 32-bit value, which is encoded in an1538architecture-specific way. It specifies which registers to restore and from1539where, and how to unwind out of the function. When the linker creates a final1540linked image, it will create a ``__TEXT,__unwind_info`` section. This section is1541a small and fast way for the runtime to access unwind info for any given1542function. If we emit compact unwind info for the function, that compact unwind1543info will be encoded in the ``__TEXT,__unwind_info`` section. If we emit DWARF1544unwind info, the ``__TEXT,__unwind_info`` section will contain the offset of the1545FDE in the ``__TEXT,__eh_frame`` section in the final linked image.1546 1547For X86, there are three modes for the compact unwind encoding:1548 1549*Function with a Frame Pointer (``EBP`` or ``RBP``)*1550  ``EBP/RBP``-based frame, where ``EBP/RBP`` is pushed onto the stack1551  immediately after the return address, then ``ESP/RSP`` is moved to1552  ``EBP/RBP``. Thus to unwind, ``ESP/RSP`` is restored with the current1553  ``EBP/RBP`` value, then ``EBP/RBP`` is restored by popping the stack, and the1554  return is done by popping the stack once more into the PC. All non-volatile1555  registers that need to be restored must have been saved in a small range on1556  the stack that starts ``EBP-4`` to ``EBP-1020`` (``RBP-8`` to1557  ``RBP-1020``). The offset (divided by 4 in 32-bit mode and 8 in 64-bit mode)1558  is encoded in bits 16-23 (mask: ``0x00FF0000``).  The registers saved are1559  encoded in bits 0-14 (mask: ``0x00007FFF``) as five 3-bit entries from the1560  following table:1561 1562    ==============  =============  ===============1563    Compact Number  i386 Register  x86-64 Register1564    ==============  =============  ===============1565    1               ``EBX``        ``RBX``1566    2               ``ECX``        ``R12``1567    3               ``EDX``        ``R13``1568    4               ``EDI``        ``R14``1569    5               ``ESI``        ``R15``1570    6               ``EBP``        ``RBP``1571    ==============  =============  ===============1572 1573*Frameless with a Small Constant Stack Size (``EBP`` or ``RBP`` is not used as a frame pointer)*1574  To return, a constant (encoded in the compact unwind encoding) is added to the1575  ``ESP/RSP``.  Then the return is done by popping the stack into the PC. All1576  non-volatile registers that need to be restored must have been saved on the1577  stack immediately after the return address. The stack size (divided by 4 in1578  32-bit mode and 8 in 64-bit mode) is encoded in bits 16-23 (mask:1579  ``0x00FF0000``). There is a maximum stack size of 1024 bytes in 32-bit mode1580  and 2048 in 64-bit mode. The number of registers saved is encoded in bits 9-121581  (mask: ``0x00001C00``). Bits 0-9 (mask: ``0x000003FF``) contain which1582  registers were saved and their order. (See the1583  ``encodeCompactUnwindRegistersWithoutFrame()`` function in1584  ``lib/Target/X86FrameLowering.cpp`` for the encoding algorithm.)1585 1586*Frameless with a Large Constant Stack Size (``EBP`` or ``RBP`` is not used as a frame pointer)*1587  This case is like the "Frameless with a Small Constant Stack Size" case, but1588  the stack size is too large to encode in the compact unwind encoding. Instead1589  it requires that the function contains "``subl $nnnnnn, %esp``" in its1590  prolog. The compact encoding contains the offset to the ``$nnnnnn`` value in1591  the function in bits 9-12 (mask: ``0x00001C00``).1592 1593.. _Late Machine Code Optimizations:1594 1595Late Machine Code Optimizations1596-------------------------------1597 1598.. note::1599 1600  To Be Written1601 1602.. _Code Emission:1603 1604Code Emission1605-------------1606 1607The code emission step of code generation is responsible for lowering from the1608code generator abstractions (like `MachineFunction`_, `MachineInstr`_, etc) down1609to the abstractions used by the MC layer (`MCInst`_, `MCStreamer`_, etc).  This1610is done with a combination of several different classes: the (misnamed)1611target-independent AsmPrinter class, target-specific subclasses of AsmPrinter1612(such as SparcAsmPrinter), and the TargetLoweringObjectFile class.1613 1614Since the MC layer works at the level of abstraction of object files, it doesn't1615have a notion of functions, global variables etc.  Instead, it thinks about1616labels, directives, and instructions.  A key class used at this time is the1617MCStreamer class.  This is an abstract API that is implemented in different ways1618(e.g., to output a ``.s`` file, output an ELF ``.o`` file, etc) that is effectively an1619"assembler API".  MCStreamer has one method per directive, such as EmitLabel,1620EmitSymbolAttribute, switchSection, etc, which directly correspond to assembly1621level directives.1622 1623If you are interested in implementing a code generator for a target, there are1624three important things that you have to implement for your target:1625 1626#. First, you need a subclass of AsmPrinter for your target.  This class1627   implements the general lowering process converting MachineFunction's into MC1628   label constructs.  The AsmPrinter base class provides a number of useful1629   methods and routines, and also allows you to override the lowering process in1630   some important ways.  You should get much of the lowering for free if you are1631   implementing an ELF, COFF, or MachO target, because the1632   TargetLoweringObjectFile class implements much of the common logic.1633 1634#. Second, you need to implement an instruction printer for your target.  The1635   instruction printer takes an `MCInst`_ and renders it to a raw_ostream as1636   text.  Most of this is automatically generated from the .td file (when you1637   specify something like "``add $dst, $src1, $src2``" in the instructions), but1638   you need to implement routines to print operands.1639 1640#. Third, you need to implement code that lowers a `MachineInstr`_ to an MCInst,1641   usually implemented in "<target>MCInstLower.cpp".  This lowering process is1642   often target specific, and is responsible for turning jump table entries,1643   constant pool indices, global variable addresses, etc into MCLabels as1644   appropriate.  This translation layer is also responsible for expanding pseudo1645   ops used by the code generator into the actual machine instructions they1646   correspond to. The MCInsts that are generated by this are fed into the1647   instruction printer or the encoder.1648 1649Finally, at your choosing, you can also implement a subclass of MCCodeEmitter1650which lowers MCInst's into machine code bytes and relocations.  This is1651important if you want to support direct ``.o`` file emission, or would like to1652implement an assembler for your target.1653 1654Emitting function stack size information1655^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1656 1657A section containing metadata on function stack sizes will be emitted when1658``TargetLoweringObjectFile::StackSizesSection`` is not null, and1659``TargetOptions::EmitStackSizeSection`` is set (-stack-size-section). The1660section will contain an array of pairs of function symbol values (pointer size)1661and stack sizes (unsigned LEB128). The stack size values only include the space1662allocated in the function prologue. Functions with dynamic stack allocations are1663not included.1664 1665Emitting function call graph information1666^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1667 1668A section containing metadata on function call graph will be emitted when1669``TargetOptions::EmitCallGraphSection`` is set (--call-graph-section). Layout of1670this section is documented in detail at :doc:`CallGraphSection`.1671 1672VLIW Packetizer1673---------------1674 1675In a Very Long Instruction Word (VLIW) architecture, the compiler is responsible1676for mapping instructions to functional-units available on the architecture. To1677that end, the compiler creates groups of instructions called *packets* or1678*bundles*. The VLIW packetizer in LLVM is a target-independent mechanism to1679enable the packetization of machine instructions.1680 1681Mapping from instructions to functional units1682^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1683 1684Instructions in a VLIW target can typically be mapped to multiple functional1685units. During the process of packetizing, the compiler must be able to reason1686about whether an instruction can be added to a packet. This decision can be1687complex since the compiler has to examine all possible mappings of instructions1688to functional units. Therefore, to alleviate compilation-time complexity, the1689VLIW packetizer parses the instruction classes of a target and generates tables1690at compiler build time. These tables can then be queried by the provided1691machine-independent API to determine if an instruction can be accommodated in a1692packet.1693 1694How the packetization tables are generated and used1695^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1696 1697The packetizer reads instruction classes from a target's itineraries and creates1698a deterministic finite automaton (DFA) to represent the state of a packet. A DFA1699consists of three major elements: inputs, states, and transitions. The set of1700inputs for the generated DFA represents the instruction being added to a1701packet. The states represent the possible consumption of functional units by1702instructions in a packet. In the DFA, transitions from one state to another1703occur on the addition of an instruction to an existing packet. If there is a1704legal mapping of functional units to instructions, then the DFA contains a1705corresponding transition. The absence of a transition indicates that a legal1706mapping does not exist and that the instruction cannot be added to the packet.1707 1708To generate tables for a VLIW target, add *Target*\ GenDFAPacketizer.inc as a1709target to the Makefile in the target directory. The exported API provides three1710functions: ``DFAPacketizer::clearResources()``,1711``DFAPacketizer::reserveResources(MachineInstr *MI)``, and1712``DFAPacketizer::canReserveResources(MachineInstr *MI)``. These functions allow1713a target packetizer to add an instruction to an existing packet and to check1714whether an instruction can be added to a packet. See1715``llvm/CodeGen/DFAPacketizer.h`` for more information.1716 1717Implementing a Native Assembler1718===============================1719 1720Though you're probably reading this because you want to write or maintain a1721compiler backend, LLVM also fully supports building a native assembler.1722We've tried hard to automate the generation of the assembler from the .td files1723(in particular the instruction syntax and encodings), which means that a large1724part of the manual and repetitive data entry can be factored and shared with the1725compiler.1726 1727Instruction Parsing1728-------------------1729 1730.. note::1731 1732  To Be Written1733 1734 1735Instruction Alias Processing1736----------------------------1737 1738Once the instruction is parsed, it enters the MatchInstructionImpl function.1739The MatchInstructionImpl function performs alias processing and then performs actual1740matching.1741 1742Alias processing is the phase that canonicalizes different lexical forms of the1743same instructions down to one representation.  There are several different kinds1744of alias that are possible to implement and they are listed below in the order1745that they are processed (which is in order from simplest/weakest to most1746complex/powerful).  Generally you want to use the first alias mechanism that1747meets the needs of your instruction, because it will allow a more concise1748description.1749 1750Mnemonic Aliases1751^^^^^^^^^^^^^^^^1752 1753The first phase of alias processing is simple instruction mnemonic remapping for1754classes of instructions which are allowed with two different mnemonics.  This1755phase is a simple and unconditionally remapping from one input mnemonic to one1756output mnemonic.  It isn't possible for this form of alias to look at the1757operands at all, so the remapping must apply for all forms of a given mnemonic.1758Mnemonic aliases are defined simply, for example X86 has:1759 1760::1761 1762  def : MnemonicAlias<"cbw",     "cbtw">;1763  def : MnemonicAlias<"smovq",   "movsq">;1764  def : MnemonicAlias<"fldcww",  "fldcw">;1765  def : MnemonicAlias<"fucompi", "fucomip">;1766  def : MnemonicAlias<"ud2a",    "ud2">;1767 1768... and many others.  With a MnemonicAlias definition, the mnemonic is remapped1769simply and directly.  Though MnemonicAlias's can't look at any aspect of the1770instruction (such as the operands) they can depend on global modes (the same1771ones supported by the matcher), through a Requires clause:1772 1773::1774 1775  def : MnemonicAlias<"pushf", "pushfq">, Requires<[In64BitMode]>;1776  def : MnemonicAlias<"pushf", "pushfl">, Requires<[In32BitMode]>;1777 1778In this example, the mnemonic gets mapped into a different one depending on1779the current instruction set.1780 1781Instruction Aliases1782^^^^^^^^^^^^^^^^^^^1783 1784The most general phase of alias processing occurs while matching is happening:1785it provides new forms for the matcher to match along with a specific instruction1786to generate.  An instruction alias has two parts: the string to match and the1787instruction to generate.  For example:1788 1789::1790 1791  def : InstAlias<"movsx $src, $dst", (MOVSX16rr8W GR16:$dst, GR8  :$src)>;1792  def : InstAlias<"movsx $src, $dst", (MOVSX16rm8W GR16:$dst, i8mem:$src)>;1793  def : InstAlias<"movsx $src, $dst", (MOVSX32rr8  GR32:$dst, GR8  :$src)>;1794  def : InstAlias<"movsx $src, $dst", (MOVSX32rr16 GR32:$dst, GR16 :$src)>;1795  def : InstAlias<"movsx $src, $dst", (MOVSX64rr8  GR64:$dst, GR8  :$src)>;1796  def : InstAlias<"movsx $src, $dst", (MOVSX64rr16 GR64:$dst, GR16 :$src)>;1797  def : InstAlias<"movsx $src, $dst", (MOVSX64rr32 GR64:$dst, GR32 :$src)>;1798 1799This shows a powerful example of the instruction aliases, matching the same1800mnemonic in multiple different ways depending on what operands are present in1801the assembly.  The result of instruction aliases can include operands in a1802different order than the destination instruction, and can use an input multiple1803times, for example:1804 1805::1806 1807  def : InstAlias<"clrb $reg", (XOR8rr  GR8 :$reg, GR8 :$reg)>;1808  def : InstAlias<"clrw $reg", (XOR16rr GR16:$reg, GR16:$reg)>;1809  def : InstAlias<"clrl $reg", (XOR32rr GR32:$reg, GR32:$reg)>;1810  def : InstAlias<"clrq $reg", (XOR64rr GR64:$reg, GR64:$reg)>;1811 1812This example also shows that tied operands are only listed once.  In the X861813backend, XOR8rr has two input GR8's and one output GR8 (where an input is tied1814to the output).  InstAliases take a flattened operand list without duplicates1815for tied operands.  The result of an instruction alias can also use immediates1816and fixed physical registers which are added as simple immediate operands in the1817result, for example:1818 1819::1820 1821  // Fixed Immediate operand.1822  def : InstAlias<"aad", (AAD8i8 10)>;1823 1824  // Fixed register operand.1825  def : InstAlias<"fcomi", (COM_FIr ST1)>;1826 1827  // Simple alias.1828  def : InstAlias<"fcomi $reg", (COM_FIr RST:$reg)>;1829 1830Instruction aliases can also have a Requires clause to make them subtarget1831specific.1832 1833If the back-end supports it, the instruction printer can automatically emit the1834alias rather than what's being aliased. It typically leads to better, more1835readable code. If it's better to print out what's being aliased, then pass a '0'1836as the third parameter to the InstAlias definition.1837 1838Instruction Matching1839--------------------1840 1841.. note::1842 1843  To Be Written1844 1845.. _Implementations of the abstract target description interfaces:1846.. _implement the target description:1847 1848Target-specific Implementation Notes1849====================================1850 1851This section of the document explains features or design decisions that are1852specific to the code generator for a particular target.1853 1854.. _tail call section:1855 1856Tail call optimization1857----------------------1858 1859Tail call optimization, callee reusing the stack of the caller, is currently1860supported on x86/x86-64, PowerPC, AArch64, and WebAssembly. It is performed on1861x86/x86-64, PowerPC, and AArch64 if:1862 1863* Caller and callee have the calling convention ``fastcc``, ``cc 10`` (GHC1864  calling convention), ``cc 11`` (HiPE calling convention), ``tailcc``, or1865  ``swifttailcc``.1866 1867* The call is a tail call - in tail position (ret immediately follows call and1868  ret uses value of call or is void).1869 1870* Option ``-tailcallopt`` is enabled or the calling convention is ``tailcc``.1871 1872* Platform-specific constraints are met.1873 1874x86/x86-64 constraints:1875 1876* No variable argument lists are used.1877 1878* On x86-64 when generating GOT/PIC code only module-local calls (visibility =1879  hidden or protected) are supported.1880 1881PowerPC constraints:1882 1883* No variable argument lists are used.1884 1885* No byval parameters are used.1886 1887* On ppc32/64 GOT/PIC only module-local calls (visibility = hidden or protected)1888  are supported.1889 1890WebAssembly constraints:1891 1892* No variable argument lists are used1893 1894* The 'tail-call' target attribute is enabled.1895 1896* The caller and callee's return types must match. The caller cannot1897  be void unless the callee is, too.1898 1899AArch64 constraints:1900 1901* No variable argument lists are used.1902 1903Example:1904 1905Call as ``llc -tailcallopt test.ll``.1906 1907.. code-block:: llvm1908 1909  declare fastcc i32 @tailcallee(i32 inreg %a1, i32 inreg %a2, i32 %a3, i32 %a4)1910 1911  define fastcc i32 @tailcaller(i32 %in1, i32 %in2) {1912    %l1 = add i32 %in1, %in21913    %tmp = tail call fastcc i32 @tailcallee(i32 inreg %in1, i32 inreg %in2, i32 %in1, i32 %l1)1914    ret i32 %tmp1915  }1916 1917Implications of ``-tailcallopt``:1918 1919To support tail call optimization in situations where the callee has more1920arguments than the caller a 'callee pops arguments' convention is used. This1921currently causes each ``fastcc`` call that is not tail call optimized (because1922one or more of above constraints are not met) to be followed by a readjustment1923of the stack. So performance might be worse in such cases.1924 1925Sibling call optimization1926-------------------------1927 1928Sibling call optimization is a restricted form of tail call optimization.1929Unlike tail call optimization described in the previous section, it can be1930performed automatically on any tail calls when ``-tailcallopt`` option is not1931specified.1932 1933Sibling call optimization is currently performed on x86/x86-64 when the1934following constraints are met:1935 1936* Caller and callee have the same calling convention. It can be either ``c`` or1937  ``fastcc``.1938 1939* The call is a tail call - in tail position (ret immediately follows call and1940  ret uses value of call or is void).1941 1942* Caller and callee have matching return type or the callee result is not used.1943 1944* If any of the callee arguments are being passed on the stack, they must be1945  available in caller's own incoming argument stack and the frame offsets must1946  be the same.1947 1948Example:1949 1950.. code-block:: llvm1951 1952  declare i32 @bar(i32, i32)1953 1954  define i32 @foo(i32 %a, i32 %b, i32 %c) {1955  entry:1956    %0 = tail call i32 @bar(i32 %a, i32 %b)1957    ret i32 %01958  }1959 1960The X86 backend1961---------------1962 1963The X86 code generator lives in the ``lib/Target/X86`` directory.  This code1964generator is capable of targeting a variety of x86-32 and x86-64 processors, and1965includes support for ISA extensions such as MMX and SSE.1966 1967X86 Target Triples supported1968^^^^^^^^^^^^^^^^^^^^^^^^^^^^1969 1970The following are the known target triples that are supported by the X861971backend.  This is not an exhaustive list, and it would be useful to add those1972that people test.1973 1974* **i686-pc-linux-gnu** --- Linux1975 1976* **i386-unknown-freebsd5.3** --- FreeBSD 5.31977 1978* **i686-pc-cygwin** --- Cygwin on Win321979 1980* **i686-pc-mingw32** --- MingW on Win321981 1982* **i386-pc-mingw32msvc** --- MingW crosscompiler on Linux1983 1984* **i686-apple-darwin*** --- Apple Darwin on X861985 1986* **x86_64-unknown-linux-gnu** --- Linux1987 1988X86 Calling Conventions supported1989^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1990 1991The following target-specific calling conventions are known to backend:1992 1993* **x86_StdCall** --- stdcall calling convention seen on Microsoft Windows1994  platform (CC ID = 64).1995 1996* **x86_FastCall** --- fastcall calling convention seen on Microsoft Windows1997  platform (CC ID = 65).1998 1999* **x86_ThisCall** --- Similar to X86_StdCall. Passes first argument in ECX,2000  others via stack. Callee is responsible for stack cleaning. This convention is2001  used by MSVC by default for methods in its ABI (CC ID = 70).2002 2003.. _X86 addressing mode:2004 2005Representing X86 addressing modes in MachineInstrs2006^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2007 2008The x86 has a very flexible way of accessing memory.  It is capable of forming2009memory addresses of the following expression directly in integer instructions2010(which use ModR/M addressing):2011 2012::2013 2014  SegmentReg: Base + [1,2,4,8] * IndexReg + Disp322015 2016In order to represent this, LLVM tracks no less than 5 operands for each memory2017operand of this form.  This means that the "load" form of '``mov``' has the2018following ``MachineOperand``\s in this order:2019 2020::2021 2022  Index:        0     |    1        2       3           4          52023  Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement Segment2024  OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm  PhysReg2025 2026Stores, and all other instructions, treat the four memory operands in the same2027way and in the same order.  If the segment register is unspecified (regno = 0),2028then no segment override is generated.  "Lea" operations do not have a segment2029register specified, so they only have 4 operands for their memory reference.2030 2031X86 address spaces supported2032^^^^^^^^^^^^^^^^^^^^^^^^^^^^2033 2034x86 has a feature which provides the ability to perform loads and stores to2035different address spaces via the x86 segment registers.  A segment override2036prefix byte on an instruction causes the instruction's memory access to go to2037the specified segment.  LLVM address space 0 is the default address space, which2038includes the stack, and any unqualified memory accesses in a program.  Address2039spaces 1-255 are currently reserved for user-defined code.  The GS-segment is2040represented by address space 256, the FS-segment is represented by address space2041257, and the SS-segment is represented by address space 258. Other x86 segments2042have yet to be allocated address space numbers.2043 2044While these address spaces may seem similar to TLS via the ``thread_local``2045keyword, and often use the same underlying hardware, there are some fundamental2046differences.2047 2048The ``thread_local`` keyword applies to global variables and specifies that they2049are to be allocated in thread-local memory. There are no type qualifiers2050involved, and these variables can be pointed to with normal pointers and2051accessed with normal loads and stores.  The ``thread_local`` keyword is2052target-independent at the LLVM IR level (though LLVM doesn't yet have2053implementations of it for some configurations)2054 2055Special address spaces, in contrast, apply to static types. Every load and store2056has a particular address space in its address operand type, and this is what2057determines which address space is accessed.  LLVM ignores these special address2058space qualifiers on global variables, and does not provide a way to directly2059allocate storage in them.  At the LLVM IR level, the behavior of these special2060address spaces depends in part on the underlying OS or runtime environment, and2061they are specific to x86 (and LLVM doesn't yet handle them correctly in some2062cases).2063 2064Some operating systems and runtime environments use (or may in the future use)2065the FS/GS-segment registers for various low-level purposes, so care should be2066taken when considering them.2067 2068Instruction naming2069^^^^^^^^^^^^^^^^^^2070 2071An instruction name consists of the base name, a default operand size, and a2072character per operand with an optional special size. For example:2073 2074::2075 2076  ADD8rr      -> add, 8-bit register, 8-bit register2077  IMUL16rmi   -> imul, 16-bit register, 16-bit memory, 16-bit immediate2078  IMUL16rmi8  -> imul, 16-bit register, 16-bit memory, 8-bit immediate2079  MOVSX32rm16 -> movsx, 32-bit register, 16-bit memory2080 2081The PowerPC backend2082-------------------2083 2084The PowerPC code generator lives in the ``lib/Target/PowerPC`` directory.  The code2085generation is retargetable to several variations or *subtargets* of the PowerPC2086ISA; including ppc32, ppc64 and altivec.2087 2088LLVM PowerPC ABI2089^^^^^^^^^^^^^^^^2090 2091LLVM follows the AIX PowerPC ABI, with two deviations. LLVM uses a PC relative2092(PIC) or static addressing for accessing global values, so no TOC (r2) is2093used. Second, r31 is used as a frame pointer to allow dynamic growth of a stack2094frame.  LLVM takes advantage of having no TOC to provide space to save the frame2095pointer in the PowerPC linkage area of the caller frame.  Other details of2096PowerPC ABI can be found at `PowerPC ABI2097<http://developer.apple.com/documentation/DeveloperTools/Conceptual/LowLevelABI/Articles/32bitPowerPC.html>`_\2098. Note: This link describes the 32-bit ABI.  The 64-bit ABI is similar except2099space for GPRs are 8 bytes wide (not 4) and r13 is reserved for system use.2100 2101Frame Layout2102^^^^^^^^^^^^2103 2104The size of a PowerPC frame is usually fixed for the duration of a function's2105invocation.  Since the frame is fixed size, all references into the frame can be2106accessed via fixed offsets from the stack pointer.  The exception to this is2107when dynamic alloca or variable sized arrays are present, then a base pointer2108(r31) is used as a proxy for the stack pointer and stack pointer is free to grow2109or shrink.  A base pointer is also used if llvm-gcc is not passed the2110-fomit-frame-pointer flag. The stack pointer is always aligned to 16 bytes, so2111that space allocated for altivec vectors will be properly aligned.2112 2113An invocation frame is laid out as follows (low memory at top):2114 2115:raw-html:`<table border="1" cellspacing="0">`2116:raw-html:`<tr>`2117:raw-html:`<td>Linkage<br><br></td>`2118:raw-html:`</tr>`2119:raw-html:`<tr>`2120:raw-html:`<td>Parameter area<br><br></td>`2121:raw-html:`</tr>`2122:raw-html:`<tr>`2123:raw-html:`<td>Dynamic area<br><br></td>`2124:raw-html:`</tr>`2125:raw-html:`<tr>`2126:raw-html:`<td>Locals area<br><br></td>`2127:raw-html:`</tr>`2128:raw-html:`<tr>`2129:raw-html:`<td>Saved registers area<br><br></td>`2130:raw-html:`</tr>`2131:raw-html:`<tr style="border-style: none hidden none hidden;">`2132:raw-html:`<td><br></td>`2133:raw-html:`</tr>`2134:raw-html:`<tr>`2135:raw-html:`<td>Previous Frame<br><br></td>`2136:raw-html:`</tr>`2137:raw-html:`</table>`2138 2139The *linkage* area is used by a callee to save special registers prior to2140allocating its own frame.  Only three entries are relevant to LLVM. The first2141entry is the previous stack pointer (sp), aka link.  This allows probing tools2142like gdb or exception handlers to quickly scan the frames in the stack.  A2143function epilog can also use the link to pop the frame from the stack.  The2144third entry in the linkage area is used to save the return address from the lr2145register. Finally, as mentioned above, the last entry is used to save the2146previous frame pointer (r31.)  The entries in the linkage area are the size of a2147GPR, thus the linkage area is 24 bytes long in 32-bit mode and 48 bytes in214864-bit mode.2149 215032-bit linkage area:2151 2152:raw-html:`<table  border="1" cellspacing="0">`2153:raw-html:`<tr>`2154:raw-html:`<td>0</td>`2155:raw-html:`<td>Saved SP (r1)</td>`2156:raw-html:`</tr>`2157:raw-html:`<tr>`2158:raw-html:`<td>4</td>`2159:raw-html:`<td>Saved CR</td>`2160:raw-html:`</tr>`2161:raw-html:`<tr>`2162:raw-html:`<td>8</td>`2163:raw-html:`<td>Saved LR</td>`2164:raw-html:`</tr>`2165:raw-html:`<tr>`2166:raw-html:`<td>12</td>`2167:raw-html:`<td>Reserved</td>`2168:raw-html:`</tr>`2169:raw-html:`<tr>`2170:raw-html:`<td>16</td>`2171:raw-html:`<td>Reserved</td>`2172:raw-html:`</tr>`2173:raw-html:`<tr>`2174:raw-html:`<td>20</td>`2175:raw-html:`<td>Saved FP (r31)</td>`2176:raw-html:`</tr>`2177:raw-html:`</table>`2178 217964-bit linkage area:2180 2181:raw-html:`<table border="1" cellspacing="0">`2182:raw-html:`<tr>`2183:raw-html:`<td>0</td>`2184:raw-html:`<td>Saved SP (r1)</td>`2185:raw-html:`</tr>`2186:raw-html:`<tr>`2187:raw-html:`<td>8</td>`2188:raw-html:`<td>Saved CR</td>`2189:raw-html:`</tr>`2190:raw-html:`<tr>`2191:raw-html:`<td>16</td>`2192:raw-html:`<td>Saved LR</td>`2193:raw-html:`</tr>`2194:raw-html:`<tr>`2195:raw-html:`<td>24</td>`2196:raw-html:`<td>Reserved</td>`2197:raw-html:`</tr>`2198:raw-html:`<tr>`2199:raw-html:`<td>32</td>`2200:raw-html:`<td>Reserved</td>`2201:raw-html:`</tr>`2202:raw-html:`<tr>`2203:raw-html:`<td>40</td>`2204:raw-html:`<td>Saved FP (r31)</td>`2205:raw-html:`</tr>`2206:raw-html:`</table>`2207 2208The *parameter area* is used to store arguments being passed to a callee2209function.  Following the PowerPC ABI, the first few arguments are actually2210passed in registers, with the space in the parameter area unused.  However, if2211there are not enough registers or the callee is a thunk or vararg function,2212these register arguments can be spilled into the parameter area.  Thus, the2213parameter area must be large enough to store all the parameters for the largest2214call sequence made by the caller.  The size must also be minimally large enough2215to spill registers r3-r10.  This allows callees blind to the call signature,2216such as thunks and vararg functions, enough space to cache the argument2217registers.  Therefore, the parameter area is minimally 32 bytes (64 bytes in221864-bit mode.)  Also note that since the parameter area is a fixed offset from the2219top of the frame, that a callee can access its split arguments using fixed2220offsets from the stack pointer (or base pointer.)2221 2222Combining the information about the linkage, parameter areas and alignment. A2223stack frame is minimally 64 bytes in 32-bit mode and 128 bytes in 64-bit mode.2224 2225The *dynamic area* starts out as size zero.  If a function uses dynamic alloca2226then space is added to the stack, the linkage and parameter areas are shifted to2227top of stack, and the new space is available immediately below the linkage and2228parameter areas.  The cost of shifting the linkage and parameter areas is minor2229since only the link value needs to be copied.  The link value can be easily2230fetched by adding the original frame size to the base pointer.  Note that2231allocations in the dynamic space need to observe 16-byte alignment.2232 2233The *locals area* is where the llvm compiler reserves space for local variables.2234 2235The *saved registers area* is where the llvm compiler spills callee saved2236registers on entry to the callee.2237 2238Prolog/Epilog2239^^^^^^^^^^^^^2240 2241The llvm prolog and epilog are the same as described in the PowerPC ABI, with2242the following exceptions.  Callee saved registers are spilled after the frame is2243created.  This allows the llvm epilog/prolog support to be common with other2244targets.  The base pointer callee saved register r31 is saved in the TOC slot of2245linkage area.  This simplifies allocation of space for the base pointer and2246makes it convenient to locate programmatically and during debugging.2247 2248Dynamic Allocation2249^^^^^^^^^^^^^^^^^^2250 2251.. note::2252 2253  TODO - More to come.2254 2255The NVPTX backend2256-----------------2257 2258The NVPTX code generator under lib/Target/NVPTX is an open-source version of2259the NVIDIA NVPTX code generator for LLVM.  It is contributed by NVIDIA and is2260a port of the code generator used in the CUDA compiler (nvcc).  It targets the2261PTX 3.0/3.1 ISA and can target any compute capability greater than or equal to22622.0 (Fermi).2263 2264This target is of production quality and should be completely compatible with2265the official NVIDIA toolchain.2266 2267Code Generator Options:2268 2269:raw-html:`<table border="1" cellspacing="0">`2270:raw-html:`<tr>`2271:raw-html:`<th>Option</th>`2272:raw-html:`<th>Description</th>`2273:raw-html:`</tr>`2274:raw-html:`<tr>`2275:raw-html:`<td>sm_20</td>`2276:raw-html:`<td align="left">Set shader model/compute capability to 2.0</td>`2277:raw-html:`</tr>`2278:raw-html:`<tr>`2279:raw-html:`<td>sm_21</td>`2280:raw-html:`<td align="left">Set shader model/compute capability to 2.1</td>`2281:raw-html:`</tr>`2282:raw-html:`<tr>`2283:raw-html:`<td>sm_30</td>`2284:raw-html:`<td align="left">Set shader model/compute capability to 3.0</td>`2285:raw-html:`</tr>`2286:raw-html:`<tr>`2287:raw-html:`<td>sm_35</td>`2288:raw-html:`<td align="left">Set shader model/compute capability to 3.5</td>`2289:raw-html:`</tr>`2290:raw-html:`<tr>`2291:raw-html:`<td>ptx30</td>`2292:raw-html:`<td align="left">Target PTX 3.0</td>`2293:raw-html:`</tr>`2294:raw-html:`<tr>`2295:raw-html:`<td>ptx31</td>`2296:raw-html:`<td align="left">Target PTX 3.1</td>`2297:raw-html:`</tr>`2298:raw-html:`</table>`2299 2300The extended Berkeley Packet Filter (eBPF) backend2301--------------------------------------------------2302 2303Extended BPF (or eBPF) is similar to the original ("classic") BPF (cBPF) used2304to filter network packets.  The2305`bpf() system call <http://man7.org/linux/man-pages/man2/bpf.2.html>`_2306performs a range of operations related to eBPF.  For both cBPF and eBPF2307programs, the Linux kernel statically analyzes the programs before loading2308them, in order to ensure that they cannot harm the running system.  eBPF is2309a 64-bit RISC instruction set designed for one to one mapping to 64-bit CPUs.2310Opcodes are 8-bit encoded, and 87 instructions are defined.  There are 102311registers, grouped by function as outlined below.2312 2313::2314 2315  R0        return value from in-kernel functions; exit value for eBPF program2316  R1 - R5   function call arguments to in-kernel functions2317  R6 - R9   callee-saved registers preserved by in-kernel functions2318  R10       stack frame pointer (read only)2319 2320Instruction encoding (arithmetic and jump)2321^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2322eBPF is reusing most of the opcode encoding from classic to simplify conversion2323of classic BPF to eBPF.  For arithmetic and jump instructions the 8-bit 'code'2324field is divided into three parts:2325 2326::2327 2328  +----------------+--------+--------------------+2329  |   4 bits       |  1 bit |   3 bits           |2330  | operation code | source | instruction class  |2331  +----------------+--------+--------------------+2332  (MSB)                                      (LSB)2333 2334Three LSB bits store instruction class which is one of:2335 2336::2337 2338  BPF_LD     0x02339  BPF_LDX    0x12340  BPF_ST     0x22341  BPF_STX    0x32342  BPF_ALU    0x42343  BPF_JMP    0x52344  (unused)   0x62345  BPF_ALU64  0x72346 2347When BPF_CLASS(code) == BPF_ALU or BPF_ALU64 or BPF_JMP,23484th bit encodes source operand2349 2350::2351 2352  BPF_X     0x1  use src_reg register as source operand2353  BPF_K     0x0  use 32-bit immediate as source operand2354 2355and four MSB bits store operation code2356 2357::2358 2359  BPF_ADD   0x0  add2360  BPF_SUB   0x1  subtract2361  BPF_MUL   0x2  multiply2362  BPF_DIV   0x3  divide2363  BPF_OR    0x4  bitwise logical OR2364  BPF_AND   0x5  bitwise logical AND2365  BPF_LSH   0x6  left shift2366  BPF_RSH   0x7  right shift (zero extended)2367  BPF_NEG   0x8  arithmetic negation2368  BPF_MOD   0x9  modulo2369  BPF_XOR   0xa  bitwise logical XOR2370  BPF_MOV   0xb  move register to register2371  BPF_ARSH  0xc  right shift (sign extended)2372  BPF_END   0xd  endianness conversion2373 2374If BPF_CLASS(code) == BPF_JMP, BPF_OP(code) is one of2375 2376::2377 2378  BPF_JA    0x0  unconditional jump2379  BPF_JEQ   0x1  jump ==2380  BPF_JGT   0x2  jump >2381  BPF_JGE   0x3  jump >=2382  BPF_JSET  0x4  jump if (DST & SRC)2383  BPF_JNE   0x5  jump !=2384  BPF_JSGT  0x6  jump signed >2385  BPF_JSGE  0x7  jump signed >=2386  BPF_CALL  0x8  function call2387  BPF_EXIT  0x9  function return2388 2389Instruction encoding (load, store)2390^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2391For load and store instructions the 8-bit 'code' field is divided as:2392 2393::2394 2395  +--------+--------+-------------------+2396  | 3 bits | 2 bits |   3 bits          |2397  |  mode  |  size  | instruction class |2398  +--------+--------+-------------------+2399  (MSB)                             (LSB)2400 2401Size modifier is one of2402 2403::2404 2405  BPF_W       0x0  word2406  BPF_H       0x1  half word2407  BPF_B       0x2  byte2408  BPF_DW      0x3  double word2409 2410Mode modifier is one of2411 2412::2413 2414  BPF_IMM     0x0  immediate2415  BPF_ABS     0x1  used to access packet data2416  BPF_IND     0x2  used to access packet data2417  BPF_MEM     0x3  memory2418  (reserved)  0x42419  (reserved)  0x52420  BPF_XADD    0x6  exclusive add2421 2422 2423Packet data access (BPF_ABS, BPF_IND)2424^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2425 2426Two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and2427(BPF_IND | <size> | BPF_LD) which are used to access packet data.2428Register R6 is an implicit input that must contain pointer to sk_buff.2429Register R0 is an implicit output which contains the data fetched2430from the packet.  Registers R1-R5 are scratch registers and must not2431be used to store the data across BPF_ABS | BPF_LD or BPF_IND | BPF_LD2432instructions.  These instructions have implicit program exit condition2433as well.  When eBPF program is trying to access the data beyond2434the packet boundary, the interpreter will abort the execution of the program.2435 2436BPF_IND | BPF_W | BPF_LD is equivalent to:2437  R0 = ntohl(\*(u32 \*) (((struct sk_buff \*) R6)->data + src_reg + imm32))2438 2439eBPF maps2440^^^^^^^^^2441 2442eBPF maps are provided for sharing data between kernel and user-space.2443Currently implemented types are hash and array, with potential extension to2444support bloom filters, radix trees, etc.  A map is defined by its type,2445maximum number of elements, key size and value size in bytes.  eBPF syscall2446supports create, update, find and delete functions on maps.2447 2448Function calls2449^^^^^^^^^^^^^^2450 2451Function call arguments are passed using up to five registers (R1 - R5).2452The return value is passed in a dedicated register (R0).  Four additional2453registers (R6 - R9) are callee-saved, and the values in these registers2454are preserved within kernel functions.  R0 - R5 are scratch registers within2455kernel functions, and eBPF programs must therefor store/restore values in2456these registers if needed across function calls.  The stack can be accessed2457using the read-only frame pointer R10.  eBPF registers map 1:1 to hardware2458registers on x86_64 and other 64-bit architectures.  For example, x86_642459in-kernel JIT maps them as2460 2461::2462 2463  R0 - rax2464  R1 - rdi2465  R2 - rsi2466  R3 - rdx2467  R4 - rcx2468  R5 - r82469  R6 - rbx2470  R7 - r132471  R8 - r142472  R9 - r152473  R10 - rbp2474 2475since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing2476and rbx, r12 - r15 are callee saved.2477 2478Program start2479^^^^^^^^^^^^^2480 2481An eBPF program receives a single argument and contains2482a single eBPF main routine; the program does not contain eBPF functions.2483Function calls are limited to a predefined set of kernel functions.  The size2484of a program is limited to 4K instructions:  this ensures fast termination and2485a limited number of kernel function calls.  Prior to running an eBPF program,2486a verifier performs static analysis to prevent loops in the code and2487to ensure valid register usage and operand types.2488 2489The AMDGPU backend2490------------------2491 2492The AMDGPU code generator lives in the ``lib/Target/AMDGPU``2493directory. This code generator is capable of targeting a variety of2494AMD GPU processors. Refer to :doc:`AMDGPUUsage` for more information.2495