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