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