docs/jit-thoughts

   1 Just some thoughts for the JITer:
   2
   3 General issues:
   4 ===============
   5
   6 We are designing a JIT compiler, so we have to consider two things:
   7
   8 - the quality of the generated code
   9 - the time needed to generate that code
  10
  11 The current approach is to keep the JITer as simple as possible, and thus as
  12 fast as possible. The generated code quality will suffer from that.
  13
  14 X86 register allocation:
  15 ========================
  16
  17 We can use 8bit or 16bit registers on the x86. If we use that feature we have
  18 more registers to allocate, which maybe prevents some register spills. We
  19 currently ignore that ability and always allocate 32 bit registers, because I
  20 think we would gain very little from that optimisation and it would complicate
  21 the code.
  22
  23 Different Register Sets:
  24 ========================
  25
  26 Most processors have more that one register set, at least one for floating
  27 point values, and one for integers. Should we support architectures with more
  28 that two sets? Does someone knows such an architecture?
  29
  30 Register Allocation:
  31 ====================
  32
  33 With lcc you can assign a fixed register to a tree before register
  34 allocation. For example this is needed by call, which return the value always
  35 in EAX on x86. The current implementation works without such system (due to
  36 special forest generation), and I wonder if we really need this feature?
  37
  38 Forest generation:
  39 ==================
  40
  41 One idea was to drive the code generation directly from the CIL code, without
  42 generating an intermediate forest of trees. I think this is not possible,
  43 because you always have to gather some attributes and attach it to the
  44 instruction (for example the register allocation info). So I thing generating a
  45 tree is the right thing and that also works perfectly with monoburg. IMO we
  46 would not get any benefit from trying to feed monoburg directly with CIL
  47 instructions.
  48
  49 We can also speedup the tree generation by using alloca instead of malloc.
  50
  51 DAG handling:
  52 =============
  53
  54 Monoburg can't handle DAGs, instead we need real trees as input for
  55 the code generator. So we have two problems:
  56
  57 1.) DUP instruction: This one is obvious - we need to store the value
  58 into a temporary variable to solve the problem.
  59
  60 2.) function calls: Chapter 12.8, page 343 of "A retargetable C compiler"
  61 explains that: "because listing a call node will give it a hidden reference
  62 from the code list". I don't understand that (can someone explain that?), but
  63 there is another reason to save return values to temporaries: Consider the
  64 following code:
  65
  66 x = f(y) + g(z); // all functions return integers
  67
  68 We could generate such a tree for this expression: STLOC(ADD(CALL,CALL))
  69
  70 The problem is that both calls returns the value in the same register,
  71 so it is non trivial to generate code for that tree. We must copy one
  72 register into another one, which make register allocation more complex.
  73 The easier solution is store the result of function calls to
  74 temporaries. This leads to the following forest:
  75
  76 STLOC(CALL)
  77 STLOC(CALL)
  78 STLOC(ADD (LDLOC, LDLOC))
  79
  80 This is what lcc is doing, if I understood 12.8, page 342, 343?
  81
  82 Value Types:
  83 ============
  84
  85 The only CLI instructions which can handle value types are loads and stores,
  86 either to local variable, to the stack or to array elements. Value types with a
  87 size smaller than sizeof(int) are handled like any other basic type. For other
  88 value types we load the base address and emit block copies to store them.
  89