docs/CodeGenerator.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2                       "http://www.w3.org/TR/html4/strict.dtd">
   3 <html>
   4 <head>
   5   <title>The LLVM Target-Independent Code Generator</title>
   6   <link rel="stylesheet" href="llvm.css" type="text/css">
   7 </head>
   8 <body>
   9
  10 <div class="doc_title">
  11   The LLVM Target-Independent Code Generator
  12 </div>
  13
  14 <ol>
  15   <li><a href="#introduction">Introduction</a>
  16     <ul>
  17       <li><a href="#required">Required components in the code generator</a></li>
  18       <li><a href="#high-level-design">The high-level design of the code generator</a></li>
  19       <li><a href="#tablegen">Using TableGen for target description</a></li>
  20     </ul>
  21   </li>
  22   <li><a href="#targetdesc">Target description classes</a>
  23     <ul>
  24       <li><a href="#targetmachine">The <tt>TargetMachine</tt> class</a></li>
  25       <li><a href="#targetdata">The <tt>TargetData</tt> class</a></li>
  26       <li><a href="#mregisterinfo">The <tt>MRegisterInfo</tt> class</a></li>
  27       <li><a href="#targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a></li>
  28       <li><a href="#targetframeinfo">The <tt>TargetFrameInfo</tt> class</a></li>
  29       <li><a href="#targetjitinfo">The <tt>TargetJITInfo</tt> class</a></li>
  30     </ul>
  31   </li>
  32   <li><a href="#codegendesc">Machine code description classes</a>
  33     <ul>
  34       <li><a href="#machineinstr">The <tt>MachineInstr</tt> class</a></li>
  35     </ul>
  36   </li>
  37   <li><a href="#codegenalgs">Target-independent code generation algorithms</a>
  38   </li>
  39   <li><a href="#targetimpls">Target description implementations</a>
  40     <ul>
  41       <li><a href="#x86">The X86 backend</a></li>
  42     </ul>
  43   </li>
  44
  45 </ol>
  46
  47 <div class="doc_author">
  48   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
  49 </div>
  50
  51 <div class="doc_warning">
  52   <p>Warning: This is a work in progress.</p>
  53 </div>
  54
  55 <!-- *********************************************************************** -->
  56 <div class="doc_section">
  57   <a name="introduction">Introduction</a>
  58 </div>
  59 <!-- *********************************************************************** -->
  60
  61 <div class="doc_text">
  62
  63 <p>The LLVM target-independent code generator is a framework that provides a
  64 suite of reusable components for translating the LLVM internal representation to
  65 the machine code for a specified target -- either in assembly form (suitable for
  66 a static compiler) or in binary machine code format (usable for a JIT compiler).
  67 The LLVM target-independent code generator consists of five main components:</p>
  68
  69 <ol>
  70 <li><a href="#targetdesc">Abstract target description</a> interfaces which
  71 capture important properties about various aspects of the machine, independently
  72 of how they will be used.  These interfaces are defined in
  73 <tt>include/llvm/Target/</tt>.</li>
  74
  75 <li>Classes used to represent the <a href="#codegendesc">machine code</a> being
  76 generated for a target.  These classes are intended to be abstract enough to
  77 represent the machine code for <i>any</i> target machine.  These classes are
  78 defined in <tt>include/llvm/CodeGen/</tt>.</li>
  79
  80 <li><a href="#codegenalgs">Target-independent algorithms</a> used to implement
  81 various phases of native code generation (register allocation, scheduling, stack
  82 frame representation, etc).  This code lives in <tt>lib/CodeGen/</tt>.</li>
  83
  84 <li><a href="#targetimpls">Implementations of the abstract target description
  85 interfaces</a> for particular targets.  These machine descriptions make use of
  86 the components provided by LLVM, and can optionally provide custom
  87 target-specific passes, to build complete code generators for a specific target.
  88 Target descriptions live in <tt>lib/Target/</tt>.</li>
  89
  90 <li><a href="#jit">The target-independent JIT components</a>.  The LLVM JIT is
  91 completely target independent (it uses the <tt>TargetJITInfo</tt> structure to
  92 interface for target-specific issues.  The code for the target-independent
  93 JIT lives in <tt>lib/ExecutionEngine/JIT</tt>.</li>
  94
  95 </ol>
  96
  97 <p>
  98 Depending on which part of the code generator you are interested in working on,
  99 different pieces of this will be useful to you.  In any case, you should be
 100 familiar with the <a href="#targetdesc">target description</a> and <a
 101 href="#codegendesc">machine code representation</a> classes.  If you want to add
 102 a backend for a new target, you will need to <a href="#targetimpls">implement the
 103 target description</a> classes for your new target and understand the <a
 104 href="LangRef.html">LLVM code representation</a>.  If you are interested in
 105 implementing a new <a href="#codegenalgs">code generation algorithm</a>, it
 106 should only depend on the target-description and machine code representation
 107 classes, ensuring that it is portable.
 108 </p>
 109
 110 </div>
 111
 112 <!-- ======================================================================= -->
 113 <div class="doc_subsection">
 114  <a name="required">Required components in the code generator</a>
 115 </div>
 116
 117 <div class="doc_text">
 118
 119 <p>The two pieces of the LLVM code generator are the high-level interface to the
 120 code generator and the set of reusable components that can be used to build
 121 target-specific backends.  The two most important interfaces (<a
 122 href="#targetmachine"><tt>TargetMachine</tt></a> and <a
 123 href="#targetdata"><tt>TargetData</tt></a> classes) are the only ones that are
 124 required to be defined for a backend to fit into the LLVM system, but the others
 125 must be defined if the reusable code generator components are going to be
 126 used.</p>
 127
 128 <p>This design has two important implications.  The first is that LLVM can
 129 support completely non-traditional code generation targets.  For example, the C
 130 backend does not require register allocation, instruction selection, or any of
 131 the other standard components provided by the system.  As such, it only
 132 implements these two interfaces, and does its own thing.  Another example of a
 133 code generator like this is a (purely hypothetical) backend that converts LLVM
 134 to the GCC RTL form and uses GCC to emit machine code for a target.</p>
 135
 136 <p>This design also implies that it is possible to design and
 137 implement radically different code generators in the LLVM system that do not
 138 make use of any of the built-in components.  Doing so is not recommended at all,
 139 but could be required for radically different targets that do not fit into the
 140 LLVM machine description model: programmable FPGAs for example.</p>
 141
 142 <p><b>Important Note:</b> For historical reasons, the LLVM SparcV9 code
 143 generator uses almost entirely different code paths than described in this
 144 document.  For this reason, there are some deprecated interfaces (such as
 145 <tt>TargetRegInfo</tt> and <tt>TargetSchedInfo</tt>), which are only used by the
 146 V9 backend and should not be used by any other targets.  Also, all code in the
 147 <tt>lib/Target/SparcV9</tt> directory and subdirectories should be considered
 148 deprecated, and should not be used as the basis for future code generator work.
 149 The SparcV9 backend is slowly being merged into the rest of the
 150 target-independent code generators, but this is a low-priority process with no
 151 predictable completion date.</p>
 152
 153 </div>
 154
 155 <!-- ======================================================================= -->
 156 <div class="doc_subsection">
 157  <a name="high-level-design">The high-level design of the code generator</a>
 158 </div>
 159
 160 <div class="doc_text">
 161
 162 <p>The LLVM target-indendent code generator is designed to support efficient and
 163 quality code generation for standard register-based microprocessors.  Code
 164 generation in this model is divided into the following stages:</p>
 165
 166 <ol>
 167 <li><b>Instruction Selection</b> - Determining an efficient implementation of the
 168 input LLVM code in the target instruction set.  This stage produces the initial
 169 code for the program in the target instruction set, then makes use of virtual
 170 registers in SSA form and physical registers that represent any required
 171 register assignments due to target constraints or calling conventions.</li>
 172
 173 <li><b>SSA-based Machine Code Optimizations</b> - This (optional) stage consists
 174 of a series of machine-code optimizations that operate on the SSA-form produced
 175 by the instruction selector.  Optimizations like modulo-scheduling, normal
 176 scheduling, or peephole optimization work here.</li>
 177
 178 <li><b>Register Allocation</b> - The target code is transformed from an infinite
 179 virtual register file in SSA form to the concrete register file used by the
 180 target.  This phase introduces spill code and eliminates all virtual register
 181 references from the program.</li>
 182
 183 <li><b>Prolog/Epilog Code Insertion</b> - Once the machine code has been
 184 generated for the function and the amount of stack space required is known (used
 185 for LLVM alloca's and spill slots), the prolog and epilog code for the function
 186 can be inserted and "abstract stack location references" can be eliminated.
 187 This stage is responsible for implementing optimizations like frame-pointer
 188 elimination and stack packing.</li>
 189
 190 <li><b>Late Machine Code Optimizations</b> - Optimizations that operate on
 191 "final" machine code can go here, such as spill code scheduling and peephole
 192 optimizations.</li>
 193
 194 <li><b>Code Emission</b> - The final stage actually outputs the code for
 195 the current function, either in the target assembler format or in machine
 196 code.</li>
 197
 198 </ol>
 199
 200 <p>
 201 The code generator is based on the assumption that the instruction selector will
 202 use an optimal pattern matching selector to create high-quality sequences of
 203 native instructions.  Alternative code generator designs based on pattern
 204 expansion and
 205 aggressive iterative peephole optimization are much slower.  This design
 206 permits efficient compilation (important for JIT environments) and
 207 aggressive optimization (used when generating code offline) by allowing
 208 components of varying levels of sophisication to be used for any step of
 209 compilation.</p>
 210
 211 <p>
 212 In addition to these stages, target implementations can insert arbitrary
 213 target-specific passes into the flow.  For example, the X86 target uses a
 214 special pass to handle the 80x87 floating point stack architecture.  Other
 215 targets with unusual requirements can be supported with custom passes as needed.
 216 </p>
 217
 218 </div>
 219
 220
 221 <!-- ======================================================================= -->
 222 <div class="doc_subsection">
 223  <a name="tablegen">Using TableGen for target description</a>
 224 </div>
 225
 226 <div class="doc_text">
 227
 228 <p>The target description classes require a detailed description of the target
 229 architecture.  These target descriptions often have a large amount of common
 230 information (e.g., an add instruction is almost identical to a sub instruction).
 231 In order to allow the maximum amount of commonality to be factored out, the LLVM
 232 code generator uses the <a href="TableGenFundamentals.html">TableGen</a> tool to
 233 describe big chunks of the target machine, which allows the use of domain- and
 234 target-specific abstractions to reduce the amount of repetition.
 235 </p>
 236
 237 </div>
 238
 239 <!-- *********************************************************************** -->
 240 <div class="doc_section">
 241   <a name="targetdesc">Target description classes</a>
 242 </div>
 243 <!-- *********************************************************************** -->
 244
 245 <div class="doc_text">
 246
 247 <p>The LLVM target description classes (which are located in the
 248 <tt>include/llvm/Target</tt> directory) provide an abstract description of the
 249 target machine, independent of any particular client.  These classes are
 250 designed to capture the <i>abstract</i> properties of the target (such as what
 251 instruction and registers it has), and do not incorporate any particular pieces
 252 of code generation algorithms (these interfaces do not take interference graphs
 253 as inputs or other algorithm-specific data structures).</p>
 254
 255 <p>All of the target description classes (except the <tt><a
 256 href="#targetdata">TargetData</a></tt> class) are designed to be subclassed by
 257 the concrete target implementation, and have virtual methods implemented.  To
 258 get to these implementations, the <tt><a
 259 href="#targetmachine">TargetMachine</a></tt> class provides accessors that
 260 should be implemented by the target.</p>
 261
 262 </div>
 263
 264 <!-- ======================================================================= -->
 265 <div class="doc_subsection">
 266   <a name="targetmachine">The <tt>TargetMachine</tt> class</a>
 267 </div>
 268
 269 <div class="doc_text">
 270
 271 <p>The <tt>TargetMachine</tt> class provides virtual methods that are used to
 272 access the target-specific implementations of the various target description
 273 classes (with the <tt>getInstrInfo</tt>, <tt>getRegisterInfo</tt>,
 274 <tt>getFrameInfo</tt>, ... methods).  This class is designed to be specialized by
 275 a concrete target implementation (e.g., <tt>X86TargetMachine</tt>) which
 276 implements the various virtual methods.  The only required target description
 277 class is the <a href="#targetdata"><tt>TargetData</tt></a> class, but if the
 278 code generator components are to be used, the other interfaces should be
 279 implemented as well.</p>
 280
 281 </div>
 282
 283
 284 <!-- ======================================================================= -->
 285 <div class="doc_subsection">
 286   <a name="targetdata">The <tt>TargetData</tt> class</a>
 287 </div>
 288
 289 <div class="doc_text">
 290
 291 <p>The <tt>TargetData</tt> class is the only required target description class,
 292 and it is the only class that is not extensible (it cannot be derived from).  It
 293 specifies information about how the target lays out memory for structures, the
 294 alignment requirements for various data types, the size of pointers in the
 295 target, and whether the target is little- or big-endian.</p>
 296
 297 </div>
 298
 299
 300 <!-- ======================================================================= -->
 301 <div class="doc_subsection">
 302   <a name="mregisterinfo">The <tt>MRegisterInfo</tt> class</a>
 303 </div>
 304
 305 <div class="doc_text">
 306
 307 <p>The <tt>MRegisterInfo</tt> class (which will eventually be renamed to
 308 <tt>TargetRegisterInfo</tt>) is used to describe the register file of the
 309 target and any interactions between the registers.</p>
 310
 311 <p>Registers in the code generator are represented in the code generator by
 312 unsigned numbers.  Physical registers (those that actually exist in the target
 313 description) are unique small numbers, and virtual registers are generally
 314 large.</p>
 315
 316 <p>Each register in the processor description has an associated
 317 <tt>MRegisterDesc</tt> entry, which provides a textual name for the register
 318 (used for assembly output and debugging dumps), a set of aliases (used to
 319 indicate that one register overlaps with another), and some flag bits.
 320 </p>
 321
 322 <p>In addition to the per-register description, the <tt>MRegisterInfo</tt> class
 323 exposes a set of processor specific register classes (instances of the
 324 <tt>TargetRegisterClass</tt> class).  Each register class contains sets of
 325 registers that have the same properties (for example, they are all 32-bit
 326 integer registers).  Each SSA virtual register created by the instruction
 327 selector has an associated register class.  When the register allocator runs, it
 328 replaces virtual registers with a physical register in the set.</p>
 329
 330 <p>
 331 The target-specific implementations of these classes is auto-generated from a <a
 332 href="TableGenFundamentals.html">TableGen</a> description of the register file.
 333 </p>
 334
 335 </div>
 336
 337 <!-- ======================================================================= -->
 338 <div class="doc_subsection">
 339   <a name="targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a>
 340 </div>
 341
 342 <!-- ======================================================================= -->
 343 <div class="doc_subsection">
 344   <a name="targetframeinfo">The <tt>TargetFrameInfo</tt> class</a>
 345 </div>
 346
 347 <!-- ======================================================================= -->
 348 <div class="doc_subsection">
 349   <a name="targetjitinfo">The <tt>TargetJITInfo</tt> class</a>
 350 </div>
 351
 352 <!-- *********************************************************************** -->
 353 <div class="doc_section">
 354   <a name="codegendesc">Machine code description classes</a>
 355 </div>
 356 <!-- *********************************************************************** -->
 357
 358 <div class="doc_text">
 359
 360 <p>
 361 At the high-level, LLVM code is translated to a machine specific representation
 362 formed out of MachineFunction, MachineBasicBlock, and <a
 363 href="#machineinstr"><tt>MachineInstr</tt></a> instances
 364 (defined in include/llvm/CodeGen).  This representation is completely target
 365 agnostic, representing instructions in their most abstract form: an opcode and a
 366 series of operands.  This representation is designed to support both SSA
 367 representation for machine code, as well as a register allocated, non-SSA form.
 368 </p>
 369
 370 </div>
 371
 372 <!-- ======================================================================= -->
 373 <div class="doc_subsection">
 374   <a name="machineinstr">The <tt>MachineInstr</tt> class</a>
 375 </div>
 376
 377 <div class="doc_text">
 378
 379 <p>Target machine instructions are represented as instances of the
 380 <tt>MachineInstr</tt> class.  This class is an extremely abstract way of
 381 representing machine instructions.  In particular, all it keeps track of is
 382 an opcode number and some number of operands.</p>
 383
 384 <p>The opcode number is an simple unsigned number that only has meaning to a
 385 specific backend.  All of the instructions for a target should be defined in
 386 the <tt>*InstrInfo.td</tt> file for the target, and the opcode enum values
 387 are autogenerated from this description.  The <tt>MachineInstr</tt> class does
 388 not have any information about how to intepret the instruction (i.e., what the
 389 semantics of the instruction are): for that you must refer to the
 390 <tt><a href="#targetinstrinfo">TargetInstrInfo</a></tt> class.</p>
 391
 392 <p>The operands of a machine instruction can be of several different types:
 393 they can be a register reference, constant integer, basic block reference, etc.
 394 In addition, a machine operand should be marked as a def or a use of the value
 395 (though only registers are allowed to be defs).</p>
 396
 397 <p>By convention, the LLVM code generator orders instruction operands so that
 398 all register definitions come before the register uses, even on architectures
 399 that are normally printed in other orders.  For example, the sparc add
 400 instruction: "<tt>add %i1, %i2, %i3</tt>" adds the "%i1", and "%i2" registers
 401 and stores the result into the "%i3" register.  In the LLVM code generator,
 402 the operands should be stored as "<tt>%i3, %i1, %i2</tt>": with the destination
 403 first.</p>
 404
 405 <p>Keeping destination operands at the beginning of the operand list has several
 406 advantages.  In particular, the debugging printer will print the instruction
 407 like this:</p>
 408
 409 <pre>
 410   %r3 = add %i1, %i2
 411 </pre>
 412
 413 <p>If the first operand is a def, and it is also easier to <a
 414 href="#buildmi">create instructions</a> whose only def is the first
 415 operand.</p>
 416
 417 </div>
 418
 419 <!-- _______________________________________________________________________ -->
 420 <div class="doc_subsubsection">
 421   <a name="buildmi">Using the <tt>MachineInstrBuilder.h</tt> functions</a>
 422 </div>
 423
 424 <div class="doc_text">
 425
 426 <p>Machine instructions are created by using the <tt>BuildMI</tt> functions,
 427 located in the <tt>include/llvm/CodeGen/MachineInstrBuilder.h</tt> file.  The
 428 <tt>BuildMI</tt> functions make it easy to build arbitrary machine
 429 instructions.  Usage of the <tt>BuildMI</tt> functions look like this:
 430 </p>
 431
 432 <pre>
 433   // Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
 434   // instruction.  The '1' specifies how many operands will be added.
 435   MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
 436
 437   // Create the same instr, but insert it at the end of a basic block.
 438   MachineBasicBlock &amp;MBB = ...
 439   BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
 440
 441   // Create the same instr, but insert it before a specified iterator point.
 442   MachineBasicBlock::iterator MBBI = ...
 443   BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
 444
 445   // Create a 'cmp Reg, 0' instruction, no destination reg.
 446   MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
 447   // Create an 'sahf' instruction which takes no operands and stores nothing.
 448   MI = BuildMI(X86::SAHF, 0);
 449
 450   // Create a self looping branch instruction.
 451   BuildMI(MBB, X86::JNE, 1).addMBB(&amp;MBB);
 452 </pre>
 453
 454 <p>
 455 The key thing to remember with the <tt>BuildMI</tt> functions is that you have
 456 to specify the number of operands that the machine instruction will take
 457 (allowing efficient memory allocation).  Also, if operands default to be uses
 458 of values, not definitions.  If you need to add a definition operand (other
 459 than the optional destination register), you must explicitly mark it as such.
 460 </p>
 461
 462 </div>
 463
 464 <!-- _______________________________________________________________________ -->
 465 <div class="doc_subsubsection">
 466   <a name="fixedregs">Fixed (aka preassigned) registers</a>
 467 </div>
 468
 469 <div class="doc_text">
 470
 471 <p>One important issue that the code generator needs to be aware of is the
 472 presence of fixed registers.  In particular, there are often places in the
 473 instruction stream where the register allocator <em>must</em> arrange for a
 474 particular value to be in a particular register.  This can occur due to
 475 limitations in the instruction set (e.g., the X86 can only do a 32-bit divide
 476 with the <tt>EAX</tt>/<tt>EDX</tt> registers), or external factors like calling
 477 conventions.  In any case, the instruction selector should emit code that
 478 copies a virtual register into or out of a physical register when needed.</p>
 479
 480 <p>For example, consider this simple LLVM example:</p>
 481
 482 <pre>
 483   int %test(int %X, int %Y) {
 484     %Z = div int %X, %Y
 485     ret int %Z
 486   }
 487 </pre>
 488
 489 <p>The X86 instruction selector produces this machine code for the div
 490 and ret (use
 491 "<tt>llc X.bc -march=x86 -print-machineinstrs</tt>" to get this):</p>
 492
 493 <pre>
 494         ;; Start of div
 495         %EAX = mov %reg1024           ;; Copy X (in reg1024) into EAX
 496         %reg1027 = sar %reg1024, 31
 497         %EDX = mov %reg1027           ;; Sign extend X into EDX
 498         idiv %reg1025                 ;; Divide by Y (in reg1025)
 499         %reg1026 = mov %EAX           ;; Read the result (Z) out of EAX
 500
 501         ;; Start of ret
 502         %EAX = mov %reg1026           ;; 32-bit return value goes in EAX
 503         ret
 504 </pre>
 505
 506 <p>By the end of code generation, the register allocator has coallesced
 507 the registers and deleted the resultant identity moves, producing the
 508 following code:</p>
 509
 510 <pre>
 511         ;; X is in EAX, Y is in ECX
 512         mov %EAX, %EDX
 513         sar %EDX, 31
 514         idiv %ECX
 515         ret
 516 </pre>
 517
 518 <p>This approach is extremely general (if it can handle the X86 architecture,
 519 it can handle anything!) and allows all of the target specific
 520 knowledge about the instruction stream to be isolated in the instruction
 521 selector.  Note that physical registers should have a short lifetime for good
 522 code generation, and all physical registers are assumed dead on entry and
 523 exit of basic blocks (before register allocation).  Thus if you need a value
 524 to be live across basic block boundaries, it <em>must</em> live in a virtual
 525 register.</p>
 526
 527 </div>
 528
 529 <!-- _______________________________________________________________________ -->
 530 <div class="doc_subsubsection">
 531   <a name="ssa">Machine code SSA form</a>
 532 </div>
 533
 534 <div class="doc_text">
 535
 536 <p><tt>MachineInstr</tt>'s are initially instruction selected in SSA-form, and
 537 are maintained in SSA-form until register allocation happens.  For the most
 538 part, this is trivially simple since LLVM is already in SSA form: LLVM PHI nodes
 539 become machine code PHI nodes, and virtual registers are only allowed to have a
 540 single definition.</p>
 541
 542 <p>After register allocation, machine code is no longer in SSA-form, as there
 543 are no virtual registers left in the code.</p>
 544
 545 </div>
 546
 547 <!-- *********************************************************************** -->
 548 <div class="doc_section">
 549   <a name="targetimpls">Target description implementations</a>
 550 </div>
 551 <!-- *********************************************************************** -->
 552
 553 <div class="doc_text">
 554
 555 <p>This section of the document explains any features or design decisions that
 556 are specific to the code generator for a particular target.</p>
 557
 558 </div>
 559
 560
 561 <!-- ======================================================================= -->
 562 <div class="doc_subsection">
 563   <a name="x86">The X86 backend</a>
 564 </div>
 565
 566 <div class="doc_text">
 567
 568 <p>
 569 The X86 code generator lives in the <tt>lib/Target/X86</tt> directory.  This
 570 code generator currently targets a generic P6-like processor.  As such, it
 571 produces a few P6-and-above instructions (like conditional moves), but it does
 572 not make use of newer features like MMX or SSE.  In the future, the X86 backend
 573 will have subtarget support added for specific processor families and
 574 implementations.</p>
 575
 576 </div>
 577
 578 <!-- _______________________________________________________________________ -->
 579 <div class="doc_subsubsection">
 580   <a name="x86_memory">Representing X86 addressing modes in MachineInstrs</a>
 581 </div>
 582
 583 <div class="doc_text">
 584
 585 <p>
 586 The x86 has a very, uhm, flexible, way of accessing memory.  It is capable of
 587 forming memory addresses of the following expression directly in integer
 588 instructions (which use ModR/M addressing):</p>
 589
 590 <pre>
 591    Base+[1,2,4,8]*IndexReg+Disp32
 592 </pre>
 593
 594 <p>Wow, that's crazy.  In order to represent this, LLVM tracks no less that 4
 595 operands for each memory operand of this form.  This means that the "load" form
 596 of 'mov' has the following "Operands" in this order:</p>
 597
 598 <pre>
 599 Index:        0     |    1        2       3           4
 600 Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement
 601 OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm
 602 </pre>
 603
 604 <p>Stores and all other instructions treat the four memory operands in the same
 605 way, in the same order.</p>
 606
 607 </div>
 608
 609 <!-- _______________________________________________________________________ -->
 610 <div class="doc_subsubsection">
 611   <a name="x86_names">Instruction naming</a>
 612 </div>
 613
 614 <div class="doc_text">
 615
 616 <p>
 617 An instruction name consists of the base name, a default operand size
 618 followed by a character per operand with an optional special size. For
 619 example:</p>
 620
 621 <p>
 622 <tt>ADD8rr</tt> -&gt; add, 8-bit register, 8-bit register<br>
 623 <tt>IMUL16rmi</tt> -&gt; imul, 16-bit register, 16-bit memory, 16-bit immediate<br>
 624 <tt>IMUL16rmi8</tt> -&gt; imul, 16-bit register, 16-bit memory, 8-bit immediate<br>
 625 <tt>MOVSX32rm16</tt> -&gt; movsx, 32-bit register, 16-bit memory
 626 </p>
 627
 628 </div>
 629
 630 <!-- *********************************************************************** -->
 631 <hr>
 632 <address>
 633   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 634   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 635   <a href="http://validator.w3.org/check/referer"><img
 636   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
 637
 638   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
 639   <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
 640   Last modified: $Date$
 641 </address>
 642
 643 </body>
 644 </html>