lib/Target/X86/README.txt

   1 //===- README.txt - Information about the X86 backend and related files ---===//
   2 //
   3 // This file contains random notes and points of interest about the X86 backend.
   4 //
   5 // Snippets of this document will probably become the final report for CS497
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 ===========
  10 I. Overview
  11 ===========
  12
  13 This directory contains a machine description for the X86 processor.  Currently
  14 this machine description is used for a high performance code generator used by a
  15 LLVM JIT.  One of the main objectives that we would like to support with this
  16 project is to build a nice clean code generator that may be extended in the
  17 future in a variety of ways: new targets, new optimizations, new
  18 transformations, etc.
  19
  20 This document describes the current state of the LLVM JIT, along with
  21 implementation notes, design decisions, and other stuff.
  22
  23
  24 ===================================
  25 II. Architecture / Design Decisions
  26 ===================================
  27
  28 We designed the infrastructure into the generic LLVM machine specific
  29 representation, which allows us to support as many targets as possible with our
  30 framework.  This framework should allow us to share many common machine specific
  31 transformations (register allocation, instruction scheduling, etc...) among all
  32 of the backends that may eventually be supported by LLVM, and ensures that the
  33 JIT and static compiler backends are largely shared.
  34
  35 At the high-level, LLVM code is translated to a machine specific representation
  36 formed out of MachineFunction, MachineBasicBlock, and MachineInstr instances
  37 (defined in include/llvm/CodeGen).  This representation is completely target
  38 agnostic, representing instructions in their most abstract form: an opcode, a
  39 destination, and a series of operands.  This representation is designed to
  40 support both SSA representation for machine code, as well as a register
  41 allocated, non-SSA form.
  42
  43 Because the Machine* representation must work regardless of the target machine,
  44 it contains very little semantic information about the program.  To get semantic
  45 information about the program, a layer of Target description datastructures are
  46 used, defined in include/llvm/Target.
  47
  48 Note that there is some amount of complexity that the X86 backend contains due
  49 to the Sparc backend's legacy requirements.  These should eventually fade away
  50 as the project progresses.
  51
  52
  53 SSA Instruction Representation
  54 ------------------------------
  55 Target machine instructions are represented as instances of MachineInstr, and
  56 all specific machine instruction types should have an entry in the
  57 InstructionInfo table defined through X86InstrInfo.def.  In the X86 backend,
  58 there are two particularly interesting forms of machine instruction: those that
  59 produce a value (such as add), and those that do not (such as a store).
  60
  61 Instructions that produce a value use Operand #0 as the "destination" register.
  62 When printing the assembly code with the built-in machine instruction printer,
  63 these destination registers will be printed to the left side of an '=' sign, as
  64 in: %reg1027 = addl %reg1026, %reg1025
  65
  66 This 'addl' MachineInstruction contains three "operands": the first is the
  67 destination register (#1027), the second is the first source register (#1026)
  68 and the third is the second source register (#1025).  Never forget the
  69 destination register will show up in the MachineInstr operands vector.  The code
  70 to generate this instruction looks like this:
  71
  72   BuildMI(BB, X86::ADDrr32, 2, 1027).addReg(1026).addReg(1025);
  73
  74 The first argument to BuildMI is the basic block to append the machine
  75 instruction to, the second is the opcode, the third is the number of operands,
  76 the fourth is the destination register.  The two addReg calls specify operands
  77 in order.
  78
  79 MachineInstrs that do not produce a value do not have this implicit first
  80 operand, they simply have #operands = #uses.  To create them, simply do not
  81 specify a destination register to the BuildMI call.
  82
  83
  84 =======================
  85 III. Source Code Layout
  86 =======================
  87
  88 The LLVM-JIT is composed of source files primarily in the following locations:
  89
  90 include/llvm/CodeGen
  91 --------------------
  92 This directory contains header files that are used to represent the program in a
  93 machine specific representation.  It currently also contains a bunch of stuff
  94 used by the Sparc backend that we don't want to get mixed up in, such as
  95 register allocation internals.
  96
  97 include/llvm/Target
  98 -------------------
  99 This directory contains header files that are used to interpret the machine
 100 specific representation of the program.  This allows us to write generic
 101 transformations that will work on any target that implements the interfaces
 102 defined in this directory.  The only classes used by the X86 backend so far are
 103 the TargetMachine, TargetData, MachineInstrInfo, and MRegisterInfo classes.
 104
 105 lib/CodeGen
 106 -----------
 107 This directory will contain all of the target independent transformations (for
 108 example, register allocation) that we write.  These transformations should only
 109 use information exposed through the Target interface, they should not include
 110 any target specific header files.
 111
 112 lib/Target/X86
 113 --------------
 114 This directory contains the machine description for X86 that is required to the
 115 rest of the compiler working.  It contains any code that is truly specific to
 116 the X86 backend, for example the instruction selector and machine code emitter.
 117
 118 tools/jello
 119 -----------
 120 This directory contains the top-level code for the JIT compiler.  This code
 121 basically boils down to a call to TargetMachine::addPassesToJITCompile.  As we
 122 progress with the project, this will also contain the compile-dispatch-recompile
 123 loop.
 124
 125 test/Regression/Jello
 126 ---------------------
 127 This directory contains regression tests for the JIT.  Initially it contains a
 128 bunch of really trivial testcases that we should build up to supporting.
 129
 130
 131 ===================================================
 132 IV. Strange Things, or, Things That Should Be Known
 133 ===================================================
 134
 135 Representing memory in MachineInstrs
 136 ------------------------------------
 137
 138 The x86 has a very, uhm, flexible, way of accessing memory.  It is capable of
 139 addressing memory addresses of the following form directly in integer
 140 instructions (which use ModR/M addressing):
 141
 142    Base+[1,2,4,8]*IndexReg+Disp32
 143
 144 Wow, that's crazy.  In order to represent this, LLVM tracks no less that 4
 145 operands for each memory operand of this form.  This means that the "load" form
 146 of 'mov' has the following "Operands" in this order:
 147
 148 Index:        0     |    1        2       3           4
 149 Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement
 150 OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm
 151
 152 Stores and all other instructions treat the four memory operands in the same
 153 way, in the same order.
 154
 155
 156 ==========================
 157 V. TODO / Future Projects
 158 ==========================
 159
 160 There are a large number of things remaining to do.  Here is a partial list:
 161
 162 Critical path:
 163 -------------
 164
 165 0. Finish providing SSA form.  This involves keeping track of some information
 166    when instructions are added to the function, but should not affect that API
 167    for creating new MInstructions or adding them to the program.
 168 1. Finish dumb instruction selector
 169 2. Write dumb register allocator
 170 3. Write assembly language emitter
 171 4. Write machine code emitter
 172
 173 Next Phase:
 174 -----------
 175 1. Implement linear time optimal instruction selector
 176 2. Implement smarter (linear scan?) register allocator
 177
 178 After this project:
 179 -------------------
 180 1. Implement lots of nifty runtime optimizations
 181 2. Implement a static compiler backend for x86 (might come almost for free...)
 182 3. Implement new spiffy targets: IA64? X86-64? M68k?  Who knows...
 183
 184 Infrastructure Improvements:
 185 ----------------------------
 186
 187 1. Bytecode is designed to be able to read particular functions from the
 188    bytecode without having to read the whole program.  Bytecode reader should be
 189    extended to allow on-demand loading of functions.
 190
 191 2. PassManager needs to be able to run just a single function through a pipeline
 192    of FunctionPass's.
 193
 194 3. llvmgcc needs to be modified to output 32-bit little endian LLVM files.
 195    Preferably it will be parameterizable so that multiple binaries need not
 196    exist.  Until this happens, we will be restricted to using type safe
 197    programs (most of the Olden suite and many smaller tests), which should be
 198    sufficient for our 497 project.  Additionally there are a few places in the
 199    LLVM infrastructure where we assume Sparc TargetData layout.  These should
 200    be easy to factor out and identify though.