Details of the Tamarin Trace Recorder

This post gives an overview of how the trace recorder in Tamarin records and interprets code. This is done at the same time. It also gives a birds eye view of what happens during the actual trace recording. I'll go into the intermediate representation in another post. So let's go into more detail than was explained in the general overview of the trace recorder. After a call to trace() we get the following:

Interpreter.cpp
trace(f, ip-1, sp, rp);
switch (curword)
{
#define lir_entry(x,y) case x: goto label_##x;
#define plain_entry(x) case x: goto label_##x;
}
So now we jump back to the vm_min_interp Forth words. Let's continue to use our example of the Forth word "and".
vm_min_interp.h
INTERP_PRIMCASE(AND)
INTERP_CALLPRIM(int32_t, i_1_0, AND, (sp[-1].i, sp[0].i))
INTERP_COPY(sp[-1].i, i_1_0)
INTERP_INVALBOXTYPE(sp[-1])
INTERP_ADJUSTSP(-1)
INTERP_NEXT(AND)
and finally the kicker is to look at INTERP_NEXT again:
Interpreter.cpp
#define INTERP_NEXT(x) TIMING_END(t_interp) } goto top_of_loop;
which jumps to the beginning of the Forth interpreter loop. However, since we are recording, the NEXTIP macro falls through and we jump back to handle_trace, which again calls trace. Here is a little diagram of what's going on in pseudocode form:
Interpreter.cpp
top_of_loop:
if (not recording) {
switch (forth word) {
... Forth interpreter body ...
}
} // end if

handle_trace:
trace();
jump to next Forth word
execute Forth word
Forth word jumps to top_of_loop

Therefore trace() is called for every single Forth word that is executed during trace recording. Now let's go a bit further into what is actually being recorded. Tamarin actually records Forth words and converts them to another intermediate representation during actual recording of the trace. It also does optimization during trace recording. Here's a quick pseudocode overview of what happens during the recording phase:
// constant folding, copy propagation
switch (Forth Word) {
if (constantFolded || copyPropogated) {
return; // don't record anything
}
}

// algebraic optimizations

switch (Forth Word) {
case: add to LIR instruction stream;
}

return;

That's it for tonight. The blog posts from here will probably become more intermittent as the amount of time to figure something out increases exponentially. I'll try to get into the LIR and the data structures surrounding tracing/compilation soon.