The problem is that inferior runloops cannot be re-entered via
continuation. One example (out of many) is the delegate pmclass, which
uses inferior runloops in vtable methods to run bytecode. The resulting
call structure (mixing bytecode and C) looks like this:
main runloop
=> main bytecode
=> op (e.g. set_s_p)
=> vtable method
=> inferior runloop
=> method bytecode
Calling a continuation requires restarting a runloop, but when the
method bytecode is running, there are two runloops. In principle, if
the method bytecode calls a continuation, as when signalling an error,
the continuation can go to the "right" runloop, i.e. the one where it
was taken. However, if the method bytecode creates a continuation which
is later called from the main bytecode, Parrot has no way of restarting
the abandoned inferior runloop. This problem also affects coroutines,
which have an implementation similar to continuations.
So the crux of the problem is that the C code that implements the op
has state that cannot be captured by a continuation. Normally, the
entire state of the computation is captured in Parrot-accessible
datastructures when the outer runloop is between instructions. Invoking
an inferior runloop violates this principle by running bytecode in the
middle of an instruction. And having vtable methods that do so
transparently makes this problem affect a great deal of the code, since
vtable methods are ubiquitous, and are generally assumed to be
low-level.
There are two broad solutions:
1. Restrict continuations to move only "outward", which makes it
unnecessary to restart inferior runloops. This may not be as bad as it
seems, as most of the languages I can think of can be implemented using
only outward (returning) continuations. And I believe the rest
(including Scheme) can be implemented without Parrot continuations, by
using the CP transformation, which is a standard Scheme compiler
technique in any case. However, we'd probably have to abandon
coroutines, since telling people that they can't use coroutines with OO
programming is really lame.
2. Eliminate inferior runloops. This is much harder, as it involves
rewriting much code, though the attached POC (see patch; more on this
below) shows that it is possible. The essential strategy is to split
the C code into two or more portions, the first containing the part that
sets up the bytecode call, and the rest deals with the result.
Ironically, this is just the CP transformation mentioned earlier; we are
turning the latter half of the C code into a continuation, and then
arrange to call it after the bytecode returns. Unfortunately, this is a
pain in C, as we have to fake a closure in order to retain state between
the C functions.
The second solution is subject to a few variations:
V1. It may be possible to redesign delegation in a way that doesn't
involve vtable methods. For instance, it's not clear that all uses of
VTABLE_get_string (there are ~250 of them) need to support delegation,
and some of them might be really hard to rewrite, being within deeply
nested C calls. Of course, set_s_p would need to call a delegated
method, but that is easier to special-case (it is the subject of the
POC). And that only covers some of the vtable-to-bytecode cases.
V2. Failing that, it may be possible to limit the number of vtable
methods that are subject to delegation.
MMD doesn't worry me. It has long been known that Parrot MMD needs
to be reimplemented more efficiently, and my own favorite candidate for
the job is the FSM-based dispatch that is standard technology for Common
Lisp systems. The idea is that, instead of doing the type dispatch
directly, the MMD engine builds an FSM in PIR that does argument
discrimination, compiles it to bytecode, caches it for future use, then
calls it to handle the case at hand. That neatly kills multiple birds
with one stone.
Nor does embedding. In embedding, it is normal to exit the main
runloop and later start another main runloop. As long as continuations
don't care which runloop they restart (i.e. there is only one setjmp
address that gets reset every time), this is not a problem.
I think V1 would be very, very desirable, but I'm not sure if it's
even possible. If not, the rest are are all long, hard roads; we should
be quite certain we are heading down the right one before we start.
What does everyone think?
-- Bob Rogers
http://rgrjr.dyndns.org/
Notes on the POC:
The patch changes set_s_p (around src/ops/set.ops:160) to call
Parrot_op_set_reg_from_vtable, which just does it if given a "normal"
get_string method, else it arranges to call the delegated method, saving
the result register type and number, and arranging to call
store_tail_result_into_register on continuation exit in order to do the
job.
It doesn't quite work, apparently because set_retval gives up too
soon, and so set_s_p always sets the result to a null string.
Consequently, Parrot doesn't even completely build; it fails compiling
PGE. In general, it breaks all non-error uses of set_s_p. However, it
is sufficient to fix t/pmc/exception.t case 30, which tests handling of
an error within set_s_p.
I started out by writing Parrot_op_set_reg_from_vtable to handle the
general case of storing the result from any vtable method into any
register, but wound up focusing on the "get_string => S register" path
in order to finish it in reasonable time. Had I not tried to be
general, it could have been a lot simpler. It could still be made
simpler by code sharing between the bytecode and non-bytecode cases, and
by undoing some of the C&P butchery.
Index: src/ops/set.ops
===================================================================
--- src/ops/set.ops (revision 13852)
+++ src/ops/set.ops (working copy)
@@ -155,9 +155,15 @@
goto NEXT();
}
+/* ' */
+
inline op set(out STR, invar PMC) :base_core {
- $1 = $2->vtable->get_string(interpreter, $2);
- goto NEXT();
+ opcode_t *next = expr NEXT();
+ next = Parrot_op_set_reg_from_vtable
+ (interpreter, PARROT_ARG_STRING, cur_opcode[1], next,
+ $2->vtable->get_string, "__get_string",
+ $2);
+ goto ADDRESS(next);
}
inline op set(out STR, invar STR) :base_core {
Index: src/inter_run.c
===================================================================
--- src/inter_run.c (revision 13852)
+++ src/inter_run.c (working copy)
@@ -276,6 +276,31 @@
return set_retval(interpreter, 0, ctx);
}
+opcode_t *
+Parrot_tailcall_meth_fromc(Interp *interpreter,
+ PMC *sub, PMC *obj, opcode_t *return_addr,
+ cont_C_continuation_t C_cont,
+ PMC *C_cont_state)
+/* This is magic for avoiding subordinate runloops. */
+{
+ parrot_context_t *old_ctx = CONTEXT(interpreter->ctx);
+ opcode_t offset, *dest;
+ struct Parrot_cont * cc;
+
+ interpreter->current_cont
+ = new_ret_continuation_pmc(interpreter, return_addr);
+ interpreter->current_object = obj;
+ cc = PMC_cont(interpreter->current_cont);
+ cc->C_continuation = C_cont;
+ cc->C_continuation_state = C_cont_state;
+ dest = VTABLE_invoke(interpreter, sub, (void*)1);
+ if (!dest)
+ internal_exception(1, "Subroutine returned a NULL address");
+ dest = parrot_pass_args_fromc(interpreter, "O", dest,
+ old_ctx, obj);
+ return dest;
+}
+
void *
Parrot_runops_fromc_args(Parrot_Interp interpreter, PMC *sub,
const char *sig, ...)
Index: src/pmc/retcontinuation.pmc
===================================================================
--- src/pmc/retcontinuation.pmc (revision 13852)
+++ src/pmc/retcontinuation.pmc (working copy)
@@ -123,6 +123,11 @@
INTERP->ctx.bp = caller_ctx->bp;
INTERP->ctx.bp_ps = caller_ctx->bp_ps;
next = cc->address;
+ if (cc->C_continuation) {
+ /* The C continuation replaces results handling. */
+ cc->C_continuation(INTERP, cc->from_ctx,
+ SELF, cc->C_continuation_state);
+ }
Parrot_free_context(INTERP, cc->from_ctx, 1);
seg = cc->seg;
#ifdef NDEBUG
Index: src/pmc/continuation.pmc
===================================================================
--- src/pmc/continuation.pmc (revision 13852)
+++ src/pmc/continuation.pmc (working copy)
@@ -87,6 +87,8 @@
struct Parrot_cont * cc = PMC_cont(SELF);
if (cc->to_ctx)
mark_context(INTERP, cc->to_ctx);
+ if (cc->C_continuation_state)
+ pobject_lives(INTERP, (PObj *)cc->C_continuation_state);
}
/*
@@ -269,6 +271,11 @@
ctx->current_results = cc->current_results;
}
pc = cc->address;
+ if (cc->C_continuation) {
+ /* The C continuation replaces results handling. */
+ cc->C_continuation(INTERP, caller_ctx,
+ SELF, cc->C_continuation_state);
+ }
if (ctx->current_results && INTERP->current_args) {
/*
* the register pointer is already switched back
Index: src/sub.c
===================================================================
--- src/sub.c (revision 13852)
+++ src/sub.c (working copy)
@@ -137,10 +137,13 @@
new_continuation(Interp *interp, struct Parrot_cont *to)
{
struct Parrot_cont * const cc = mem_sys_allocate(sizeof(struct
Parrot_cont));
- struct Parrot_Context * const to_ctx = to ? to->to_ctx :
CONTEXT(interp->ctx);
+ struct Parrot_Context * const to_ctx
+ = to ? to->to_ctx : CONTEXT(interp->ctx);
cc->to_ctx = to_ctx;
cc->from_ctx = CONTEXT(interp->ctx);
+ cc->C_continuation = NULL;
+ cc->C_continuation_state = NULL;
cc->runloop_id = 0;
CONTEXT(interp->ctx)->ref_count++;
if (to) {
@@ -172,6 +175,8 @@
struct Parrot_cont * const cc = mem_sys_allocate(sizeof(struct
Parrot_cont));
cc->to_ctx = CONTEXT(interp->ctx);
cc->from_ctx = NULL; /* filled in during a call */
+ cc->C_continuation = NULL;
+ cc->C_continuation_state = NULL;
cc->runloop_id = 0;
cc->seg = interp->code;
cc->current_results = NULL;
@@ -483,6 +488,133 @@
#endif
return clos_pmc;
}
+
+/* [stolen from delegate.pmc. -- rgr, 5-Aug-06.] */
+static PMC *
+find_method_internal(Interp* interpreter, PMC *pmc, STRING *meth) {
+ PMC *class = pmc;
+
+ if (PObj_is_object_TEST(pmc)) {
+ class = GET_CLASS((Buffer *)PMC_data(pmc), pmc);
+ }
+ return Parrot_find_method_with_cache(interpreter, class, meth);
+}
+
+/* [stolen from delegate.pmc. -- rgr, 5-Aug-06.] */
+static PMC *
+find_method_sub_or_die(Interp* interpreter, PMC *pmc, STRING *meth) {
+ PMC *returnPMC = find_method_internal(interpreter, pmc, meth);
+ if (PMC_IS_NULL(returnPMC)) {
+ PMC *class = pmc;
+ if (PObj_is_object_TEST(pmc)) {
+ class = GET_CLASS((Buffer *)PMC_data(pmc), pmc);
+ real_exception(interpreter, NULL, E_LookupError,
+ "Can't find method '%s' for object '%s'",
+ string_to_cstring(interpreter, meth),
+ string_to_cstring(interpreter, PMC_str_val(
+ get_attrib_num((SLOTTYPE *)PMC_data(class),
+ PCD_CLASS_NAME)))
+ );
+ } else {
+ real_exception(interpreter, NULL, E_LookupError,
+ "Can't find method '%s' - erroneous PMC",
+ string_to_cstring(interpreter, meth)
+ );
+ }
+ }
+ return returnPMC;
+}
+
+static void
+store_tail_result_into_register(Interp* interpreter,
+ parrot_context_t *returning_ctx,
+ PMC* continuation, PMC* c_closure_state)
+{
+ struct Parrot_Context *ctx = CONTEXT(interpreter->ctx);
+ INTVAL arg_type
+ = VTABLE_get_integer_keyed_int(interpreter, c_closure_state, 0);
+ INTVAL arg_register
+ = VTABLE_get_integer_keyed_int(interpreter, c_closure_state, 1);
+
+ switch (arg_type) {
+ case PARROT_ARG_STRING:
+ CTX_REG_STR(ctx, arg_register)
+ = set_retval(interpreter, 'S', returning_ctx);
+ fprintf(stderr, "stuffed string %p from ctx %p "
+ "via cont %p type %d "
+ "to reg %d of ctx %p\n",
+ CTX_REG_STR(ctx, arg_register), returning_ctx,
+ continuation, continuation->vtable->base_type,
+ arg_register, ctx);
+ break;
+ case PARROT_ARG_PMC:
+ CTX_REG_PMC(ctx, arg_register)
+ = set_retval(interpreter, 'P', returning_ctx);
+ break;
+ case PARROT_ARG_INTVAL:
+ case PARROT_ARG_FLOATVAL:
+ default:
+ real_exception(interpreter, NULL, 1,
+ "oops; got arg_type %d when storing tail result\n",
+ arg_type);
+ }
+}
+
+opcode_t *
+Parrot_op_set_reg_from_vtable(Interp *interpreter,
+ Call_bits_enum_t arg_type,
+ INTVAL arg_register,
+ opcode_t *next,
+ get_string_method_t vtable_method,
+ char *method_name,
+ PMC *method_object)
+{
+ struct Parrot_Context *ctx = CONTEXT(interpreter->ctx);
+
+ if (vtable_method == interpreter->vtables[enum_class_delegate]->get_string) {
+ /* winner */
+ /* fprintf(stderr, "gotcha\n"); */
+ STRING *meth = const_string(interpreter, method_name);
+ PMC *sub = find_method_sub_or_die(interpreter, method_object, meth);
+ PMC *state;
+ opcode_t *next_instruction;
+
+ state = pmc_new(interpreter, enum_class_FixedIntegerArray);
+ VTABLE_set_integer_native(interpreter, state, 2);
+ VTABLE_set_integer_keyed_int(interpreter, state, 0, (INTVAL) arg_type);
+ VTABLE_set_integer_keyed_int(interpreter, state, 1, (INTVAL)
arg_register);
+ next_instruction
+ = Parrot_tailcall_meth_fromc(interpreter, sub, method_object, next,
+ store_tail_result_into_register,
+ state);
+ return next_instruction;
+ }
+ else {
+ /* just call the method and stuff it in the register. */
+ switch (arg_type) {
+ case PARROT_ARG_INTVAL:
+ CTX_REG_INT(ctx, arg_register)
+ = (INTVAL) (*vtable_method) (interpreter, method_object);
+ break;
+ case PARROT_ARG_FLOATVAL:
+ /* CTX_REG_NUM(ctx, arg_register) = (FLOATVAL) (*vtable_method)
(interpreter, method_object); */
+ break;
+ case PARROT_ARG_STRING:
+ CTX_REG_STR(ctx, arg_register)
+ = (struct parrot_string_t *)
+ (*vtable_method) (interpreter, method_object);
+ break;
+ case PARROT_ARG_PMC:
+ CTX_REG_PMC(ctx, arg_register)
+ = (PMC *) (*vtable_method) (interpreter, method_object);
+ break;
+ default:
+ internal_exception(1, "oops\n");
+ }
+ return next;
+ }
+}
+
/*
=back
Index: include/parrot/sub.h
===================================================================
--- include/parrot/sub.h (revision 13852)
+++ include/parrot/sub.h (working copy)
@@ -118,6 +118,11 @@
struct Parrot_Context *from_ctx; /* sub, this cont is returning from */
opcode_t *current_results; /* ptr into code with get_results opcode
full continuation only */
+ cont_C_continuation_t C_continuation;
+ /* if not NULL, a C function to call
+ instead of normal return value
+ processing. */
+ PMC *C_continuation_state; /* state passed to C_continuation */
int runloop_id; /* id of the creating runloop. */
} * parrot_cont_t;
@@ -152,6 +157,11 @@
PMC* Parrot_find_pad(Interp*, STRING *lex_name, parrot_context_t *);
PMC* parrot_new_closure(Interp*, PMC*);
+opcode_t* Parrot_op_set_reg_from_vtable(Interp *, Call_bits_enum_t, INTVAL,
+ opcode_t *, get_string_method_t,
+ char *, PMC *);
+
+
#endif /* PARROT_SUB_H_GUARD */
/*
Index: include/parrot/interpreter.h
===================================================================
--- include/parrot/interpreter.h (revision 13852)
+++ include/parrot/interpreter.h (working copy)
@@ -436,6 +436,12 @@
/* &end_gen */
+/* This is for a C "tailcall" function used instead of normal subroutine return
+ processing. */
+typedef void (*cont_C_continuation_t)(Interp* interpreter,
+ parrot_context_t *caller_ctx,
+ PMC* continuation, PMC* c_closure_state);
+
PARROT_API Interp *make_interpreter(Interp * parent, Interp_flags);
PARROT_API void Parrot_init(Interp *);
PARROT_API void Parrot_destroy(Interp *);
@@ -459,6 +465,8 @@
va_list);
PARROT_API void* Parrot_run_meth_fromc(Interp *, PMC *sub, PMC* obj, STRING
*meth);
+PARROT_API opcode_t * Parrot_tailcall_meth_fromc(Interp *,
+ PMC *, PMC *, opcode_t *, cont_C_continuation_t, PMC *);
PARROT_API void* Parrot_run_meth_fromc_args(Interp *, PMC *sub,
PMC* obj, STRING *meth, const char *signature, ...);
PARROT_API INTVAL Parrot_run_meth_fromc_args_reti(Interp *, PMC *sub,
