[Lightning] Adding support for a multi pass intermediate representation

[Paulo César Pereira de Andrade]

  Hi,

  I have posted some random ideas about it before, but now I think
I have good, starting point model for it.

  I already implemented it partially in my new, also initial, jit generation
model for my language http://code.google.com/p/exl/ in the files
elightning.c, ethunder.c and erain.c (it is a storm :-)

  The core data structure is somewhat like:

struct lit_node {
    struct lit_node     *next;
    int                  code;
    int                  r0;
    int                  r1;
    int                  r2;
    union {
        int              i;
        long             l;
        void            *p;
        float            f;
        double           d;
    } i0;
    union {
        int              i;
        long             l;
        void            *p;
        float            f;
        double           d;
    } i1;
};

36 bytes on 32 bits and 40 on 64 bits, so, have at least 8 bytes for an
extra flags/state field, and have it aligned at a 16 bytes.

  Absolute rule that must be met is that, jit_prolog marks a function start,
and its body finishes in the next jit_prolog or end of input. And no jump
in the middle of the jit function should be allowed, otherwise, there is no
much use of the concept.

  Some fast optimizations that can be done include:
o Copy propagation and constant propagation
  If a register naming, ssa like schema is used, it can also handle
  code around jump/label boundaries, but this start being in the
  slow optimization field, and may only pay off if one has loops
  executing like a few million times
o Jump threading
o With minimal extra logic, it can ensure one does not need to start
  over due to running out of jit buffer space; it can reallocate, or
  restart over with a newer buffer without telling about it
o Read/write intermediate representation to/from a file, so one can
  cache the jit if sources did not change
o Several other, unlisted here :-) Most of which would depend on
  a ssa or register naming/numbering approach

  Some background of the newer representation, and how I started
it, is because in my language I am generating a lot of code like:

a = b + c;
->
  ld pointerof(b) in %r1
  ld type %r1 in %r0
  bne_i not_int %r0 t_int
  ld int value %r1 in %v1
  jmpi next_int
not_int:
  bne_i not_float %r0 t_float
  ld float value %r1 in %f0
  jmpi next_float
not_float:
  prepare 1
    pusharg_p %r1
  finish vm_ld
next_int:
next_float:
[and so on to setup the operation, push arguments to vm stack, etc]

The problem obviously is that it forgets about the type when it
merges code paths, but this is remediated by having 3 lists, and
being able to dynamically construct states on the C stack while
generating jit, so that it only merges the code paths when the
value type becomes unknown.

  Comments?

Thanks,
Paulo