call frames, or not call frames...

call frames, or not call frames...

Post by cr8819 » Thu, 22 Jan 2009 16:35:47

partly making use of prior written text...).

so, for general context, I have my compiler framework which compiles C to a
language I call RPNIL (which is also the name of the compiler which compiles
this language to assembler).

RPNIL is a language with some remaining heritage in languages like FORTH and
PostScript, but is in many ways quite different given the special task it
had been designed for (to define code sequences which are to be compiled to
native code).

so, functionally, it serves a role similar to Java Bytecode or .NET CIL, but
differing in that its native form is textual, and with a syntax cosmetically
between that of PostScript and COBOL (it uses a COBOL-like notation for the
toplevel, but uses a PostScript like notation for runnable code).

the language and compiler had been "frozen" for about 1 year as I tried
(without success) to implement a replacement (and I then proceeded to
develop many other areas of the project codebase).

so, recently I started doing several interconnected efforts (they are
related as far as purpose, but the code is disjoint), namely, adding a good
deal of extensions to RPNIL, targetting the JVM to RPNIL, and considering
the possibility of targetting CIL to RPNIL.

now, of course, RPNIL and JBC don't fit exactly, but for most things a minor
amount of crufting has been sufficient (including adding alternate opcodes
to RPNIL which more closely resemble those in JBC and CIL).

actually, RPNIL is a bit "higher level" than JBC, and so in many cases whole
groups of JVM opcodes are merged into a single RPNIL opcode (and sometimes
casts are inserted in order to compensate for the generally untyped nature
of JBC, where JBC specifices types in the operations, whereas RPNIL
specifies types in the values...).

in general though the conversion is fairly straightforwards...

and, among these extensions and awkwardness, was figuring out how to
interface RPNIL and my object system (since it was originally designed for
C, it lacks built in object support).

the eventual considered solution is the use of "self-initializing accessor
thunks", which behave more or less like stub functions (a stub is created
for each field in each accessed class). each stub will in-effect contain a
static variable, which will hold the actual slot or method handle (which
will be loaded the first time the stub is called).

when accessing a slot, if no such stub is listed, it is added to the list
(the code for the stubs is likely to be generated after the code for the

the reason I had used this approach, even though it has a slightly higher
overhead than is ideal, is because it still allows separate compilation
without the need for special linker trickery (although, even as such, it is
necessary for the classes to "exist" in the object system both before
compiling the module, and before running any code in the module, which in
the case of the JVM would mean declaring the classes to the object system
prior to JIT'ing the module...).

in part, the above restriction is because the system doesn't actually define
the classes internally (which would require adding a mirror class/instance
system in the RPNIL compiler), but instead "imports" objects from the
external C/I system and builds against those (this does save, however, when
compiling a module, as it is just like "import this class", rather than
having to declare the enti

call frames, or not call frames...

Post by robertwess » Thu, 22 Jan 2009 17:48:48

Out of curiosity, what strategy are you using to manage C objects and
pointers such that the code will make it past the byte code verifier?


call frames, or not call frames...

Post by Robbert Ha » Thu, 22 Jan 2009 21:13:42

Is there any reason you couldn't allocate these frames on the stack? You
say that a frame is created when a call is made and released when the
call returns. This suggests to me that stack allocation is an option.

Taking a step up, I wonder why you have to worry about classes and
calling conventions as much as you do. You say the reason is that RPNIL
was designed to deal with C. It seems to me you could translate the
operations of your source program into something that can be expressed
in C, and that RPNIL would then be able to deal with it. What I mean is:
instead of adapting RPNIL to the operations that the JVM and the CLI
expose, why don't you try to express those operations in terms of what
RPNIL already supports?



There are 10 kinds of people in the world; those who understand trinary,
those who don't, and those who confuse it with binary.

call frames, or not call frames...

Post by cr8819 » Thu, 22 Jan 2009 22:44:10

errm, I am not compiling C to JBC here...

basically it is like this:


so, C never has to worry about the bytecode verifier...

crude attempt at ASCII diagrams (which will probably not survive the font

-> -> ->
\ / \

BGBDY implements the object system (and other components). DYTy, DYClass,
and DYLL are subsystems of BGBDY.

| \ | \ |
DYTy DYClass \ |
| / | /
RPNIL -----------+--- /

BGBDY := {DYTy, DYClass, DYLL, ...}
{DYTy, DYClass, DYLL, ...} -> BGBGC

RPNIL -> DYClass

so, RPNIL uses a number of different components...

as for my JVM, I call it BJVM.

\ /

ClassLoader -> BJVM

BJAS: JBC assembler, Jasmin-style syntax
BJS / uBJS: JavaScript engine (incomplete)

BJVM := {ClassLoader, BJAS, BJS}
BJVM is, in general, not yet complete...

however, at present, it does not implement a verifier.

given the JIT for JBC is converting to a higher-level representation, this
is just odd, but still works...

C is compiled via BGBCCC.


PP = PreProcessor
CP = C Parser
CC = C Compiler (AKA: "Upper Compiler")


BGBCCC depends heavily on BGBDY, but presently does not use DYClass or DYLL
at all...

PP -> CP -> CC -> RPNIL

or such...

call frames, or not call frames...

Post by cr8819 » Fri, 23 Jan 2009 05:30:33

"Robbert Haarman" < XXXX@XXXXX.COM > wrote in message
news: XXXX@XXXXX.COM ...

it is possible, but there is a problem:
stack-allocated call frames would get in the way if ever I wanted to
implement continuations, closures, tail-call optimization, ...
it would be needed to be able to distinguish heap and stack frames, in order
to allow frames to be relocated to the heap whenever a continuation is made,
deal with memory under the control of the caller when making a tail-call,

but, the stack would be higher performance.

the idea I have for the frame allocator though is to make use of a very
specialized free-list allocator (specialized to the point where most of the
frames are fixed-size, like T-Shirts), such that a typical allocation can be
done in a short glob of assembly instructions.

from elsewhere:
mov al, 1
lock cmpxchg [dyll_frame_lock], al
jnz .lock

mov eax, [dyll_frame_list_0]
and eax, eax
jz .alloc
mov edx, [eax]
mov [dyll_frame_list_0], edx

mov byte [dyll_frame_lock], 0

;more expensive mutex-style lock

;free frames list is empty, grab memory for more frames and add to list

this could make performance tolerable at least, but this is still a bit more
overhead than C, which could lead to people writing a smaller number of
bigger functions (rather than a bigger number of smaller functions).

OTOH, this would also leave a lot more of a reason for the implementation to
make use of inlining wherever possible...

very likely, when operating under this mode, much of the code structure
during compilation will be reworked into a variation of CPS...

though this is possible, RPNIL is not the most intelligent when it comes to
optimizing, and the awkwardness required to get around many of these issues
would very likely hurt performance... (it is much the same issue as if a HLL
compiler targets its output to C... it works, but the performance is not as
good as if, for example, it were to target CIL, or have an optimizing

meanwhile, adding built-in support in the RPNIL compiler for all these
features allows a good deal more optimizing power for these cases...