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 Register Allocation:
  15 ====================
  16
  17 With lcc you can assign a fixed register to a tree before register
  18 allocation. For example this is needed by call, which return the value always
  19 in EAX on x86. The current implementation works without such system, due to
  20 special forest generation.
  21
  22 Different Register Sets:
  23 ========================
  24
  25 Most processors have more that one register set, at least one for floating
  26 point values, and one for integers. Should we support architectures with more
  27 that two sets? Does someone knows such an architecture?
  28
  29 64bit Integer Values:
  30 =====================
  31
  32 I can imagine two different implementation. On possibility would be to treat
  33 long (64bit) values simply like any other value type. This implies that we
  34 call class methods for ALU operations like add or sub. Sure, this method will
  35 be be a bit inefficient.
  36
  37 The more performant solution is to allocate two 32bit registers for each 64bit
  38 value. We add a new non terminal to the monoburg grammar called "lreg". The
  39 register allocation routines takes care of this non terminal and allocates two
  40 32 bit registers for them.
  41
  42 Forest generation:
  43 ==================
  44
  45 Consider the following code:
  46
  47 OPCODE:         STACK           LOCALS
  48 LDLOC.0         (5)             [5,0]
  49 LDC.1           (5,1)           [5,0]
  50 STLOC.0         (5)             [1,0]
  51 STLOC.1         ()              [1,5]
  52
  53 A simple forest generation generates:
  54
  55 STLOC.0(LDC.1)
  56 STLOC.1(LDLOC.0)
  57
  58 Which is wrong, since it stores the wrong value (1 instead of 5). Instead we
  59 must generate something like:
  60
  61 STLOC.TMP(LDLOC.0)
  62 STLOC.0(LDC.1)
  63 STLOC.1(LDLOC.TMP)
  64
  65 Where STLOC.TMP saves the value into a new temporary variable.
  66
  67 We also need a similar solution for basic block boundaries when the stack depth
  68 is not zero. We can simply save those values to new temporary values. Consider
  69 the following basic block with one instruction:
  70
  71 LDLOC.1
  72 This should generate a tree like:
  73
  74 STLOC.TMP(LDLOC.1) Please notice that an intelligent register allocator can
  75 still allocate registers for those new variables.
  76
  77 DAG handling:
  78 =============
  79
  80 Monoburg can't handle DAGs, instead we need real trees as input for
  81 the code generator. So we have two problems:
  82
  83 1.) DUP instruction: This one is obvious - we need to store the value
  84 into a temporary variable to solve the problem.
  85
  86 2.) function calls: Chapter 12.8, page 343 of "A retargetable C compiler"
  87 explains that: "because listing a call node will give it a hidden reference
  88 from the code list". I don't understand that (can someone explain that?), but
  89 there is another reason to save return values to temporaries: Consider the
  90 following code:
  91
  92 x = f(y) + g(z); // all functions return integers
  93
  94 We could generate such a tree for this expression: STLOC(ADD(CALL,CALL))
  95
  96 The problem is that both calls returns the value in the same register,
  97 so it is non trivial to generate code for that tree. We must copy one
  98 register into another one, which make register allocation more complex.
  99 The easier solution is store the result of function calls to
 100 temporaries. This leads to the following forest:
 101
 102 STLOC(CALL)
 103 STLOC(CALL)
 104 STLOC(ADD (LDLOC, LDLOC))
 105
 106 This is what lcc is doing, if I understood 12.8, page 342, 343?
 107
 108 Possible Optimisations:
 109 =======================
 110
 111 Miguel said ORP does some optimisation on IL level, for example moving array
 112 bounds checking out of loops:
 113
 114 for (i = 0; i < N; i++) { check_range (a, i); a [i] = X; }
 115
 116 id transformed to:
 117
 118 if (in_range (a, 0, N)) { for (i = 0; i < N; i++) a[i] = X; }
 119 else for (i = 0; i < N; i++) { check_range (a, i); a [i] = X; }
 120
 121 The "else" is only to keep original semantics (exception handling).
 122
 123 We need loop detection logic in order to implement this (dominator tree).
 124
 125 AFAIK CACAO also implements this.