From ec94f80b077ada57fd16e673d4bdab2bb0728e71 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Fri, 4 Jun 2004 00:16:02 +0000 Subject: [PATCH] Fix PR356: [doc] lib/Target/X86/README.txt needs update Also add some documentation about how instructions work git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@14006 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/CodeGenerator.html | 281 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 280 insertions(+), 1 deletion(-) diff --git a/docs/CodeGenerator.html b/docs/CodeGenerator.html index 2145449f0a0..0dddad66079 100644 --- a/docs/CodeGenerator.html +++ b/docs/CodeGenerator.html @@ -30,6 +30,9 @@
  • Machine code description classes +
  • Target-independent code generation algorithms
    • @@ -61,7 +64,7 @@ suite of reusable components for translating the LLVM internal representation to the machine code for a specified target -- either in assembly form (suitable for a static compiler) or in binary machine code format (usable for a JIT compiler). -The LLVM target-independent code generator consists of four main components:

    +The LLVM target-independent code generator consists of five main components:

    1. Abstract target description interfaces which @@ -84,6 +87,11 @@ the components provided by LLVM, and can optionally provide custom target-specific passes, to build complete code generators for a specific target. Target descriptions live in lib/Target/.
      2. +
    2. The target-independent JIT components. The LLVM JIT is +completely target independent (it uses the TargetJITInfo structure to +interface for target-specific issues. The code for the target-independent +JIT lives in lib/ExecutionEngine/JIT.
      3. +

    @@ -345,7 +353,278 @@ href="TableGenFundamentals.html">TableGen description of the register file. +

    + +

    +At the high-level, LLVM code is translated to a machine specific representation +formed out of MachineFunction, MachineBasicBlock, and MachineInstr instances +(defined in include/llvm/CodeGen). This representation is completely target +agnostic, representing instructions in their most abstract form: an opcode and a +series of operands. This representation is designed to support both SSA +representation for machine code, as well as a register allocated, non-SSA form. +

    + +
    + + +
    + The MachineInstr class +
    + +
    + +

    Target machine instructions are represented as instances of the +MachineInstr class. This class is an extremely abstract way of +representing machine instructions. In particular, all it keeps track of is +an opcode number and some number of operands.

    + +

    The opcode number is an simple unsigned number that only has meaning to a +specific backend. All of the instructions for a target should be defined in +the *InstrInfo.td file for the target, and the opcode enum values +are autogenerated from this description. The MachineInstr class does +not have any information about how to intepret the instruction (i.e., what the +semantics of the instruction are): for that you must refer to the +TargetInstrInfo class.

    + +

    The operands of a machine instruction can be of several different types: +they can be a register reference, constant integer, basic block reference, etc. +In addition, a machine operand should be marked as a def or a use of the value +(though only registers are allowed to be defs).

    + +

    By convention, the LLVM code generator orders instruction operands so that +all register definitions come before the register uses, even on architectures +that are normally printed in other orders. For example, the sparc add +instruction: "add %i1, %i2, %i3" adds the "%i1", and "%i2" registers +and stores the result into the "%i3" register. In the LLVM code generator, +the operands should be stored as "%i3, %i1, %i2": with the destination +first.

    + +

    Keeping destination operands at the beginning of the operand list has several +advantages. In particular, the debugging printer will print the instruction +like this:

    + +
    +  %r3 = add %i1, %i2
+
    + +

    If the first operand is a def, and it is also easier to create instructions whose only def is the first +operand.

    + +
    + + +
    + Using the MachineInstrBuilder.h functions +
    + +
    + +

    Machine instructions are created by using the BuildMI functions, +located in the include/llvm/CodeGen/MachineInstrBuilder.h file. The +BuildMI functions make it easy to build arbitrary machine +instructions. Usage of the BuildMI functions look like this: +

    + +
    +  // Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
+  // instruction.  The '1' specifies how many operands will be added.
+  MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
+
+  // Create the same instr, but insert it at the end of a basic block.
+  MachineBasicBlock &MBB = ...
+  BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
+
+  // Create the same instr, but insert it before a specified iterator point.
+  MachineBasicBlock::iterator MBBI = ...
+  BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
+
+  // Create a 'cmp Reg, 0' instruction, no destination reg.
+  MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
+  // Create an 'sahf' instruction which takes no operands and stores nothing.
+  MI = BuildMI(X86::SAHF, 0);
+
+  // Create a self looping branch instruction.
+  BuildMI(MBB, X86::JNE, 1).addMBB(&MBB);
+
    + +

    +The key thing to remember with the BuildMI functions is that you have +to specify the number of operands that the machine instruction will take +(allowing efficient memory allocation). Also, if operands default to be uses +of values, not definitions. If you need to add a definition operand (other +than the optional destination register), you must explicitly mark it as such. +

    + +
    + + +
    + Fixed (aka preassigned) registers +
    + +
    + +

    One important issue that the code generator needs to be aware of is the +presence of fixed registers. In particular, there are often places in the +instruction stream where the register allocator must arrange for a +particular value to be in a particular register. This can occur due to +limitations in the instruction set (e.g., the X86 can only do a 32-bit divide +with the EAX/EDX registers), or external factors like calling +conventions. In any case, the instruction selector should emit code that +copies a virtual register into or out of a physical register when needed.

    + +

    For example, consider this simple LLVM example:

    + +
    +  int %test(int %X, int %Y) {
+    %Z = div int %X, %Y
+    ret int %Z
+  }
+
    + +

    The X86 instruction selector produces this machine code for the div +and ret (use +"llc X.bc -march=x86 -print-machineinstrs" to get this):

    + +
    +        ;; Start of div
+        %EAX = mov %reg1024           ;; Copy X (in reg1024) into EAX
+        %reg1027 = sar %reg1024, 31
+        %EDX = mov %reg1027           ;; Sign extend X into EDX
+        idiv %reg1025                 ;; Divide by Y (in reg1025)
+        %reg1026 = mov %EAX           ;; Read the result (Z) out of EAX
+
+        ;; Start of ret
+        %EAX = mov %reg1026           ;; 32-bit return value goes in EAX
+        ret
+
    + +

    By the end of code generation, the register allocator has coallesced +the registers and deleted the resultant identity moves, producing the +following code:

    + +
    +        ;; X is in EAX, Y is in ECX
+        mov %EAX, %EDX
+        sar %EDX, 31
+        idiv %ECX
+        ret 
+
    + +

    This approach is extremely general (if it can handle the X86 architecture, +it can handle anything!) and allows all of the target specific +knowledge about the instruction stream to be isolated in the instruction +selector. Note that physical registers should have a short lifetime for good +code generation, and all physical registers are assumed dead on entry and +exit of basic blocks (before register allocation). Thus if you need a value +to be live across basic block boundaries, it must live in a virtual +register.

    + +
    + + +
    + Machine code SSA form +
    + +
    +

    MachineInstr's are initially instruction selected in SSA-form, and +are maintained in SSA-form until register allocation happens. For the most +part, this is trivially simple since LLVM is already in SSA form: LLVM PHI nodes +become machine code PHI nodes, and virtual registers are only allowed to have a +single definition.

    + +

    After register allocation, machine code is no longer in SSA-form, as there +are no virtual registers left in the code.

    + +
    + + +
    + Target description implementations +
    + + +
    + +

    This section of the document explains any features or design decisions that +are specific to the code generator for a particular target.

    + +
    + + + +
    + The X86 backend +
    + +
    + +

    +The X86 code generator lives in the lib/Target/X86 directory. This +code generator currently targets a generic P6-like processor. As such, it +produces a few P6-and-above instructions (like conditional moves), but it does +not make use of newer features like MMX or SSE. In the future, the X86 backend +will have subtarget support added for specific processor families and +implementations.

    + +
    + + +
    + Representing X86 addressing modes in MachineInstrs +
    + +
    + +

    +The x86 has a very, uhm, flexible, way of accessing memory. It is capable of +forming memory addresses of the following expression directly in integer +instructions (which use ModR/M addressing):

    + +
    +   Base+[1,2,4,8]*IndexReg+Disp32
+
    + +

    Wow, that's crazy. In order to represent this, LLVM tracks no less that 4 +operands for each memory operand of this form. This means that the "load" form +of 'mov' has the following "Operands" in this order:

    + +
    +Index:        0     |    1        2       3           4
+Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement
+OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm
+
    + +

    Stores and all other instructions treat the four memory operands in the same +way, in the same order.

    +

    + +
    + + +
    + Instruction naming +
    + +
    + +

    +An instruction name consists of the base name, a default operand size +followed by a character per operand with an optional special size. For +example:

    + +

    +ADD8rr -> add, 8-bit register, 8-bit register
    +IMUL16rmi -> imul, 16-bit register, 16-bit memory, 16-bit immediate
    +IMUL16rmi8 -> imul, 16-bit register, 16-bit memory, 8-bit immediate
    +MOVSX32rm16 -> movsx, 32-bit register, 16-bit memory +

    + +
    -- 2.34.1