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 improtant 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 generator 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 <a href="#targetimpls">implement the
 103 targe 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>The other implication of this design is 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 a 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 the 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 machine 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 code.  Alternative code generator designs based on pattern expansion and
 204 aggressive iterative peephole optimization are much slower.  This design is
 205 designed to permit efficient compilation (important for JIT environments) and
 206 aggressive optimization (used when generate code offline) by allowing components
 207 of varying levels of sophisication to be used for any step of compilation.</p>
 208
 209 <p>
 210 In addition to these stages, target implementations can insert arbitrary
 211 target-specific passes into the flow.  For example, the X86 target uses a
 212 special pass to handle the 80x87 floating point stack architecture.  Other
 213 targets with unusual requirements can be supported with custom passes as needed.
 214 </p>
 215
 216 </div>
 217
 218
 219 <!-- ======================================================================= -->
 220 <div class="doc_subsection">
 221  <a name="tablegen">Using TableGen for target description</a>
 222 </div>
 223
 224 <div class="doc_text">
 225
 226 <p>The target description classes require a detailed description of the target
 227 architecture.  These target descriptions often have a large amount of common
 228 information (e.g., an add instruction is almost identical to a sub instruction).
 229 In order to allow the maximum amount of commonality to be factored out, the LLVM
 230 code generator uses the <a href="TableGenFundamentals.html">TableGen</a> tool to
 231 describe big chunks of the target machine, which allows the use of domain- and
 232 target-specific abstractions to reduce the amount of repetition.
 233 </p>
 234
 235 </div>
 236
 237 <!-- *********************************************************************** -->
 238 <div class="doc_section">
 239   <a name="targetdesc">Target description classes</a>
 240 </div>
 241 <!-- *********************************************************************** -->
 242
 243 <div class="doc_text">
 244
 245 <p>The LLVM target description classes (which are located in the
 246 <tt>include/llvm/Target</tt> directory) provide an abstract description of the
 247 target machine, independent of any particular client.  These classes are
 248 designed to capture the <i>abstract</i> properties of the target (such as what
 249 instruction and registers it has), and do not incorporate any particular pieces
 250 of code generation algorithms (these interfaces do not take interference graphs
 251 as inputs or other algorithm-specific data structures).</p>
 252
 253 <p>All of the target description classes (except the <tt><a
 254 href="#targetdata">TargetData</a></tt> class) are designed to be subclassed by
 255 the concrete target implementation, and have virtual methods implemented.  To
 256 get to these implementations, <tt><a
 257 href="#targetmachine">TargetMachine</a></tt> class provides accessors that
 258 should be implemented by the target.</p>
 259
 260 </div>
 261
 262 <!-- ======================================================================= -->
 263 <div class="doc_subsection">
 264   <a name="targetmachine">The <tt>TargetMachine</tt> class</a>
 265 </div>
 266
 267 <div class="doc_text">
 268
 269 <p>The <tt>TargetMachine</tt> class provides virtual methods that are used to
 270 access the target-specific implementations of the various target description
 271 classes (with the <tt>getInstrInfo</tt>, <tt>getRegisterInfo</tt>,
 272 <tt>getFrameInfo</tt>, ... methods).  This class is designed to be subclassed by
 273 a concrete target implementation (e.g., <tt>X86TargetMachine</tt>) which
 274 implements the various virtual methods.  The only required target description
 275 class is the <a href="#targetdata"><tt>TargetData</tt></a> class, but if the
 276 code generator components are to be used, the other interfaces should be
 277 implemented as well.</p>
 278
 279 </div>
 280
 281
 282 <!-- ======================================================================= -->
 283 <div class="doc_subsection">
 284   <a name="targetdata">The <tt>TargetData</tt> class</a>
 285 </div>
 286
 287 <div class="doc_text">
 288
 289 <p>The <tt>TargetData</tt> class is the only required target description class,
 290 and it is the only class that is not extensible (it cannot be derived from).  It
 291 specifies information about how the target lays out memory for structures, the
 292 alignment requirements for various data types, the size of pointers in the
 293 target, and whether the target is little- or big-endian.</p>
 294
 295 </div>
 296
 297
 298 <!-- ======================================================================= -->
 299 <div class="doc_subsection">
 300   <a name="mregisterinfo">The <tt>MRegisterInfo</tt> class</a>
 301 </div>
 302
 303 <div class="doc_text">
 304
 305 <p>The <tt>MRegisterInfo</tt> class (which will eventually be renamed to
 306 <tt>TargetRegisterInfo</tt>) is used to describe the register file of the
 307 target and any interactions between the registers.</p>
 308
 309 <p>Registers in the code generator are represented in the code generator by
 310 unsigned numbers.  Physical registers (those that actually exist in the target
 311 description) are unique small numbers, and virtual registers are generally
 312 large.</p>
 313
 314 <p>Each register in the processor description has an associated
 315 <tt>MRegisterDesc</tt> entry, which provides a textual name for the register
 316 (used for assembly output and debugging dumps), a set of aliases (used to
 317 indicate that one register overlaps with another), and some flag bits.
 318 </p>
 319
 320 <p>In addition to the per-register description, the <tt>MRegisterInfo</tt> class
 321 exposes a set of processor specific register classes (instances of the
 322 <tt>TargetRegisterClass</tt> class).  Each register class contains sets of
 323 registers that have the same properties (for example, they are all 32-bit
 324 integer registers).  Each SSA virtual register created by the instruction
 325 selector has an associated register class.  When the register allocator runs, it
 326 replaces virtual registers with a physical register in the set.</p>
 327
 328 <p>
 329 The target-specific implementations of these classes is auto-generated from a <a
 330 href="TableGenFundamentals.html">TableGen</a> description of the register file.
 331 </p>
 332
 333 </div>
 334
 335 <!-- ======================================================================= -->
 336 <div class="doc_subsection">
 337   <a name="targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a>
 338 </div>
 339
 340 <!-- ======================================================================= -->
 341 <div class="doc_subsection">
 342   <a name="targetframeinfo">The <tt>TargetFrameInfo</tt> class</a>
 343 </div>
 344
 345 <!-- ======================================================================= -->
 346 <div class="doc_subsection">
 347   <a name="targetjitinfo">The <tt>TargetJITInfo</tt> class</a>
 348 </div>
 349
 350 <!-- *********************************************************************** -->
 351 <div class="doc_section">
 352   <a name="codegendesc">Machine code description classes</a>
 353 </div>
 354 <!-- *********************************************************************** -->
 355
 356 <div class="doc_text">
 357
 358 <p>
 359 At the high-level, LLVM code is translated to a machine specific representation
 360 formed out of MachineFunction, MachineBasicBlock, and <a
 361 href="#machineinstr"><tt>MachineInstr</tt></a> instances
 362 (defined in include/llvm/CodeGen).  This representation is completely target
 363 agnostic, representing instructions in their most abstract form: an opcode and a
 364 series of operands.  This representation is designed to support both SSA
 365 representation for machine code, as well as a register allocated, non-SSA form.
 366 </p>
 367
 368 </div>
 369
 370 <!-- ======================================================================= -->
 371 <div class="doc_subsection">
 372   <a name="machineinstr">The <tt>MachineInstr</tt> class</a>
 373 </div>
 374
 375 <div class="doc_text">
 376
 377 <p>Target machine instructions are represented as instances of the
 378 <tt>MachineInstr</tt> class.  This class is an extremely abstract way of
 379 representing machine instructions.  In particular, all it keeps track of is
 380 an opcode number and some number of operands.</p>
 381
 382 <p>The opcode number is an simple unsigned number that only has meaning to a
 383 specific backend.  All of the instructions for a target should be defined in
 384 the <tt>*InstrInfo.td</tt> file for the target, and the opcode enum values
 385 are autogenerated from this description.  The <tt>MachineInstr</tt> class does
 386 not have any information about how to intepret the instruction (i.e., what the
 387 semantics of the instruction are): for that you must refer to the
 388 <tt><a href="#targetinstrinfo">TargetInstrInfo</a></tt> class.</p>
 389
 390 <p>The operands of a machine instruction can be of several different types:
 391 they can be a register reference, constant integer, basic block reference, etc.
 392 In addition, a machine operand should be marked as a def or a use of the value
 393 (though only registers are allowed to be defs).</p>
 394
 395 <p>By convention, the LLVM code generator orders instruction operands so that
 396 all register definitions come before the register uses, even on architectures
 397 that are normally printed in other orders.  For example, the sparc add
 398 instruction: "<tt>add %i1, %i2, %i3</tt>" adds the "%i1", and "%i2" registers
 399 and stores the result into the "%i3" register.  In the LLVM code generator,
 400 the operands should be stored as "<tt>%i3, %i1, %i2</tt>": with the destination
 401 first.</p>
 402
 403 <p>Keeping destination operands at the beginning of the operand list has several
 404 advantages.  In particular, the debugging printer will print the instruction
 405 like this:</p>
 406
 407 <pre>
 408   %r3 = add %i1, %i2
 409 </pre>
 410
 411 <p>If the first operand is a def, and it is also easier to <a
 412 href="#buildmi">create instructions</a> whose only def is the first
 413 operand.</p>
 414
 415 </div>
 416
 417 <!-- _______________________________________________________________________ -->
 418 <div class="doc_subsubsection">
 419   <a name="buildmi">Using the <tt>MachineInstrBuilder.h</tt> functions</a>
 420 </div>
 421
 422 <div class="doc_text">
 423
 424 <p>Machine instructions are created by using the <tt>BuildMI</tt> functions,
 425 located in the <tt>include/llvm/CodeGen/MachineInstrBuilder.h</tt> file.  The
 426 <tt>BuildMI</tt> functions make it easy to build arbitrary machine
 427 instructions.  Usage of the <tt>BuildMI</tt> functions look like this:
 428 </p>
 429
 430 <pre>
 431   // Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
 432   // instruction.  The '1' specifies how many operands will be added.
 433   MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
 434
 435   // Create the same instr, but insert it at the end of a basic block.
 436   MachineBasicBlock &amp;MBB = ...
 437   BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
 438
 439   // Create the same instr, but insert it before a specified iterator point.
 440   MachineBasicBlock::iterator MBBI = ...
 441   BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
 442
 443   // Create a 'cmp Reg, 0' instruction, no destination reg.
 444   MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
 445   // Create an 'sahf' instruction which takes no operands and stores nothing.
 446   MI = BuildMI(X86::SAHF, 0);
 447
 448   // Create a self looping branch instruction.
 449   BuildMI(MBB, X86::JNE, 1).addMBB(&amp;MBB);
 450 </pre>
 451
 452 <p>
 453 The key thing to remember with the <tt>BuildMI</tt> functions is that you have
 454 to specify the number of operands that the machine instruction will take
 455 (allowing efficient memory allocation).  Also, if operands default to be uses
 456 of values, not definitions.  If you need to add a definition operand (other
 457 than the optional destination register), you must explicitly mark it as such.
 458 </p>
 459
 460 </div>
 461
 462 <!-- _______________________________________________________________________ -->
 463 <div class="doc_subsubsection">
 464   <a name="fixedregs">Fixed (aka preassigned) registers</a>
 465 </div>
 466
 467 <div class="doc_text">
 468
 469 <p>One important issue that the code generator needs to be aware of is the
 470 presence of fixed registers.  In particular, there are often places in the
 471 instruction stream where the register allocator <em>must</em> arrange for a
 472 particular value to be in a particular register.  This can occur due to
 473 limitations in the instruction set (e.g., the X86 can only do a 32-bit divide
 474 with the <tt>EAX</tt>/<tt>EDX</tt> registers), or external factors like calling
 475 conventions.  In any case, the instruction selector should emit code that
 476 copies a virtual register into or out of a physical register when needed.</p>
 477
 478 <p>For example, consider this simple LLVM example:</p>
 479
 480 <pre>
 481   int %test(int %X, int %Y) {
 482     %Z = div int %X, %Y
 483     ret int %Z
 484   }
 485 </pre>
 486
 487 <p>The X86 instruction selector produces this machine code for the div
 488 and ret (use
 489 "<tt>llc X.bc -march=x86 -print-machineinstrs</tt>" to get this):</p>
 490
 491 <pre>
 492         ;; Start of div
 493         %EAX = mov %reg1024           ;; Copy X (in reg1024) into EAX
 494         %reg1027 = sar %reg1024, 31
 495         %EDX = mov %reg1027           ;; Sign extend X into EDX
 496         idiv %reg1025                 ;; Divide by Y (in reg1025)
 497         %reg1026 = mov %EAX           ;; Read the result (Z) out of EAX
 498
 499         ;; Start of ret
 500         %EAX = mov %reg1026           ;; 32-bit return value goes in EAX
 501         ret
 502 </pre>
 503
 504 <p>By the end of code generation, the register allocator has coallesced
 505 the registers and deleted the resultant identity moves, producing the
 506 following code:</p>
 507
 508 <pre>
 509         ;; X is in EAX, Y is in ECX
 510         mov %EAX, %EDX
 511         sar %EDX, 31
 512         idiv %ECX
 513         ret
 514 </pre>
 515
 516 <p>This approach is extremely general (if it can handle the X86 architecture,
 517 it can handle anything!) and allows all of the target specific
 518 knowledge about the instruction stream to be isolated in the instruction
 519 selector.  Note that physical registers should have a short lifetime for good
 520 code generation, and all physical registers are assumed dead on entry and
 521 exit of basic blocks (before register allocation).  Thus if you need a value
 522 to be live across basic block boundaries, it <em>must</em> live in a virtual
 523 register.</p>
 524
 525 </div>
 526
 527 <!-- _______________________________________________________________________ -->
 528 <div class="doc_subsubsection">
 529   <a name="ssa">Machine code SSA form</a>
 530 </div>
 531
 532 <div class="doc_text">
 533
 534 <p><tt>MachineInstr</tt>'s are initially instruction selected in SSA-form, and
 535 are maintained in SSA-form until register allocation happens.  For the most
 536 part, this is trivially simple since LLVM is already in SSA form: LLVM PHI nodes
 537 become machine code PHI nodes, and virtual registers are only allowed to have a
 538 single definition.</p>
 539
 540 <p>After register allocation, machine code is no longer in SSA-form, as there
 541 are no virtual registers left in the code.</p>
 542
 543 </div>
 544
 545 <!-- *********************************************************************** -->
 546 <div class="doc_section">
 547   <a name="targetimpls">Target description implementations</a>
 548 </div>
 549 <!-- *********************************************************************** -->
 550
 551 <div class="doc_text">
 552
 553 <p>This section of the document explains any features or design decisions that
 554 are specific to the code generator for a particular target.</p>
 555
 556 </div>
 557
 558
 559 <!-- ======================================================================= -->
 560 <div class="doc_subsection">
 561   <a name="x86">The X86 backend</a>
 562 </div>
 563
 564 <div class="doc_text">
 565
 566 <p>
 567 The X86 code generator lives in the <tt>lib/Target/X86</tt> directory.  This
 568 code generator currently targets a generic P6-like processor.  As such, it
 569 produces a few P6-and-above instructions (like conditional moves), but it does
 570 not make use of newer features like MMX or SSE.  In the future, the X86 backend
 571 will have subtarget support added for specific processor families and
 572 implementations.</p>
 573
 574 </div>
 575
 576 <!-- _______________________________________________________________________ -->
 577 <div class="doc_subsubsection">
 578   <a name="x86_memory">Representing X86 addressing modes in MachineInstrs</a>
 579 </div>
 580
 581 <div class="doc_text">
 582
 583 <p>
 584 The x86 has a very, uhm, flexible, way of accessing memory.  It is capable of
 585 forming memory addresses of the following expression directly in integer
 586 instructions (which use ModR/M addressing):</p>
 587
 588 <pre>
 589    Base+[1,2,4,8]*IndexReg+Disp32
 590 </pre>
 591
 592 <p>Wow, that's crazy.  In order to represent this, LLVM tracks no less that 4
 593 operands for each memory operand of this form.  This means that the "load" form
 594 of 'mov' has the following "Operands" in this order:</p>
 595
 596 <pre>
 597 Index:        0     |    1        2       3           4
 598 Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement
 599 OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm
 600 </pre>
 601
 602 <p>Stores and all other instructions treat the four memory operands in the same
 603 way, in the same order.</p>
 604
 605 </div>
 606
 607 <!-- _______________________________________________________________________ -->
 608 <div class="doc_subsubsection">
 609   <a name="x86_names">Instruction naming</a>
 610 </div>
 611
 612 <div class="doc_text">
 613
 614 <p>
 615 An instruction name consists of the base name, a default operand size
 616 followed by a character per operand with an optional special size. For
 617 example:</p>
 618
 619 <p>
 620 <tt>ADD8rr</tt> -&gt; add, 8-bit register, 8-bit register<br>
 621 <tt>IMUL16rmi</tt> -&gt; imul, 16-bit register, 16-bit memory, 16-bit immediate<br>
 622 <tt>IMUL16rmi8</tt> -&gt; imul, 16-bit register, 16-bit memory, 8-bit immediate<br>
 623 <tt>MOVSX32rm16</tt> -&gt; movsx, 32-bit register, 16-bit memory
 624 </p>
 625
 626 </div>
 627
 628 <!-- *********************************************************************** -->
 629 <hr>
 630 <address>
 631   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 632   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 633   <a href="http://validator.w3.org/check/referer"><img
 634   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
 635
 636   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
 637   <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
 638   Last modified: $Date$
 639 </address>
 640
 641 </body>
 642 </html>