Rewriting byte codes

[Jim Pick]

On Sun, Mar 31, 2002 at 09:02:46PM +0200, Erik Corry wrote:
> 
> Hi
> 
> I'd like to make some changes to Kaffe to make it simpler to
> do more precise GC.

I'm all for getting some better GC capabilities into Kaffe.

> What would be needed at a minimum would
> be:
> 
> * Split local variables that can be either reference or non-reference
>   into two.  (The alternative is to keep track of when they are what).

What do the other VMs with non-conservative GC do?

Forgive my ignorance, but I haven't had enough time to do an in-depth
study of the issue yet.  I do know that we do have to keep track of
where the references are on the stack in order to do non-conservative
GC (something we do not currently do).  Beyond that, I'm pretty dumb,
so I'm going to ask some stupid questions.  :-)

> * Keep track of which stack positions are references when we do a
>   call or new.  Luckily the stack is zapped on an exception so we
>   don't have trouble there.

Where does the information about which stack positions are references
get stored?  On the stack, I suppose?

I need to look at some other VM implementations to see how they keep
track of references on the stack (not to mention objects on the heap).

> * Make copies of jsr code so that each basic block can only be called
>   from one jsr call point chain (default the null chain of course)

I think I understand the idea behind splitting the local variables
(since the local variable used to store the return PC from a jsr call
could also be used to store a reference).

> There's an obvious problem that when we split the variable, one
> of the new variables could end up above the 256 byte level.  Similarly
> we could end up with more than 65536 bytes in a method.
> In order to fix this a little byte code rewriting is inevitable.  I
> would suggest we rewrite the byte codes such that:
> 
> * All insns are wide (16 bit index to local variables), and we drop
>   the wide prefix
> * All inline constants are native-endian
> * All pc indexes are 32 bits and of course native endian (mostly a
>   problem with the exception table I think, also replace GOTO with
>   GOTO_W throughout)

The ideas sound nice, although I we should think seriously about what
the tradeoffs are before making this the default.  The rewriting phase
is some additional overhead, and there is some code expansion (but
maybe the resulting code will be faster).

I think it would be nice to have a generic spot where we can rewrite
bytecode before JITing it.  I imagine that could be used for some
other optimizations too.
 
> Copying jsr code is very nice because it means all problems related
> to jsrs just disappear.  We can replace jsrs and rets with gotos.
> You are not allowed to recurse with jsr (though you are allowed
> nesting) so semantics should be preserved.
>
> In theory it can give exponential code expansion, in practice I
> doubt it does.  I don't think you can construct an example in
> Java that gives exponential code expansion, and if you had byte
> code that did that, it would take exponential time to verify, so
> it's a bad idea anyway.

I'm afraid that I don't understand the reasoning behind copying to get
rid of jsrs.  What problems are you getting rid of?  Wouldn't just
using a separate local variable that was designated as never holding a
reference do the trick?

Theoretically, somebody could hand code a subroutine that did
something different with the jsr return PC value that is pushed onto
the stack (instead of using an astore, as is typically found in a
finally clause).  In real life, that probably never happens, but isn't
it still legal bytecode?
 
> Any comments?  I'm not guaranteeing I'll have time, but right
> now it looks as though I may need it for something else anyway.

I'm very interested in seeing what we can do to improve our GC.

At the same time, I'd like to see what we can do to make kaffe more
interoperable with other free software VMs out there.  I'd love it if
we could define a clean enough interface that would enable us to "plug
in" a GC subsystem from another free JVM (eg. ORP, Jikes RVM, Sable,
Latte).  I'd also like to see if we "plug in" and execute pre-compiled
objects built with gcj.

I think I've got a lot of studying to do.  :-)

Cheers,

 - Jim