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