Re: Public domain Pcode spec/interpreter

Tim-- I saw on comp.compilers that you are thinking about a pcode system
that can freely intermix pcode and native code. As luck may have it, a
while ago I wrote such a beast as a school project.


The result was a C->C compiler that would strip out the bodies of
functions and replace each with an array of pcode instructions, a little
glue, and a call to the pcode interpreter. Something along the following
lines:


Given the following code:


int foo (int x, int y)
{


return (x + y);
}


Emit something along the lines of:


int foo (int x, int y)
{


/* This isn't the actual pcode, just */
/* an approximation. */
static pcode_op_t __instructions [] = {
ADD_INT, /* pop top 2 ints, push sum. */
RET_INT /* pop and return int. */
};


PUSH_INT (x); /* push x onto the pcode stack. */
PUSH_INT (y); /* push y onto the pcode stack. */


/* call the entry point to the */
/* interpreter that is set up */
/* to return an int. */
return (_pcode_int (__instructions));
}


Of course, for this function, there probably isn't any savings. However,
for longer functions, there was considerable savings-- usually about 30%
over native MC68000, much more for something like a MIPS or Sparc
(although I don't have the numbers handy).


The actual implementation was somewhat C-specific, but I think the ideas
are portable. Wherever you see "C", substitute the language of choice.


Function calls inside the pcode were the most complicated piece-- they
built a normal C stack frame and called the C function. If the function
turned out to be a pcode function after all, then of course this was a
waste of time, but it allows you to use the regular linker to blindly mix
and match ordinary C functions and pcode functions.


Accessing static and global variables were another problem, since in order
to be accessible to ordinary C functions they had to live outside the
pcode universe, but some extensions to the pcode made this work as well.


Setjmp and longjmp didn't work; they'd need to be modified to grab some
information about the pcode interpreter state (stack, registers, etc). I
didn't think about this very much.


dbx'ing the code was a confusing experience-- it wasn't possible to look
at the values of local variables, or do any other sort of source-level
debugging while the pcode interpreter was doing its thing. The debugger
would have to be extended in quite a few ways.


For the compiler front end, I used lcc, and for the pcode, I started with
pretty much the raw three-address ops that lcc feeds to the code
generator. After analyzing the results for a number of programs, I
started generating new pcode instructions to replace common sequences of
instructions with shorter sequences. For example, the C expr (array [i] =
7) might be converted into a bunch of instructions like to compute the
address of array [i] and then store 7 there. If array is some scalar
type, however, this can all be done in one 3-address function. Of course,
the right thing to do would have been to detect these constructs
syntactically in the front end, but I was reluctant to do so (lcc's parser
is (or was) hand-written), so I let the code generator pick through the
parse tree and find these sorts of things.


I could send you a copy of the code and docs, but 95% of the good ideas in
it are illustrated above. I actually did things a little differently than
shown, involving some assembler hacks that can't be done in C, and the
part of the pcode interpreter that knows how to call C functions was of
course in assembler-- MC680x0, which was the only practical assembler I
knew at the time (I tried to hack it into MIPS R3000, but didn't have the
right documentation).


My implementation also didn't cover functions that returned structures,
and the pcode interpreter didn't fully implement doubles, and the register
spill routines had a bug which made large functions use registers try to
use registers that didn't exist... Still, I was able to compile and run a
lot of fairly complex (double-free) programs before I had to hand the
thing in.


If you get rich or famous by using these ideas, please mention me in
your memoirs.


-Dan
--
Dan Ellard - ellard@bbn.com -- BBN HARK Systems Corporation
--

Return to the comp.compilers page.
Search the comp.compilers archives again.