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