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