A blog about programming topics, mostly JVM, Linux kernel, and x86 related things.

Friday, July 13, 2007

Live Interval Splitting

I tried to enable assertion messages in the regression test suite of Jato but saw crashes within java.lang.StringBuffer#<init> whenever an assertion failed. After some debugging, I narrowed the problem down to method invocations clobbering registers. So I hacked a simple test program to illustrate the problem:

    public void testReturnFromInvokeVirtualReinstatesTheFrameOfTheInvoker() {
Dispatcher dispatcher = new Dispatcher();
InvocationTarget target = new InvocationTarget();
dispatcher.dispatch(target);
}

public class Dispatcher {
public Object self;

public Dispatcher() { this.self = this; }
public void dispatch(InvocationTarget target) { target.invoke(); }
}

public class InvocationTarget {
public Object self;

public InvocationTarget() { this.self = this; }
public void invoke() { }
}


Which also causes a crash because we don't preserve any registers during a function call.

The SysV ABI for x86 divides general purpose interger registers into two groups: caller-saved (eax, ecx, and edx) and callee-saved registeers (ebx, ebp, esi, and edi). You only need to preserve callee-saved registers in the function prolog and are free to clobber any caller-saved registers you want. The caller is responsible for preserving any registers that are live during a function call.

Both problems can be solved by extending the register allocator with live interval splitting. For callee-saved registers, we simply mark them as live throughout the whole function. If any of the callee-saved registers are used, the register allocator will spill it and reload the register from memory before returning from the method. Likewise, for caller-saved registers, we mark them defined by any call instruction which surrounds the call instruction with one instruction long interval. Thus any live intervals using any of the registers will be split and spilled before the call and reloaded before the next use.

Now all I need to do is write the code.