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