Chip Salzenberg <[EMAIL PROTECTED]> wrote: > What design issues are crying for attention right now?
The CPS (continuation passing style) call scheme has some still unsolved implications. There are mainly two issues: 1) correctness 2) speed I'd like to summarize mainly the correctness item. "Branching" around via a continuation is invisible to the register allocator. The register allocator just sees a linear control flow from a subroutine call to the next statements after the call. But if the subroutine captured the return continuation, it can return repeatedly through the same location, which effectively creates a loop in the CFG (control flow graph). A detailed analysis is in: Subject: "Continuations, basic blocks, loops and register allocation" Date: Sat, 13 Nov 2004 The mentioned point 1) Exceptions is solved, the "push_eh label" opcode is implemented. Still unsolved is the issue with continuations. There was a lot of discussion but it boils basically down to two things we can do: ,--[ Dan ]------------------------------------------------------------ | The loop variable must have a backing store outside of the register | set. The contents of registers must be assumed to be unreliable when | a continuation is continued. If we declare that they are put back | into the state they were when the continuation was taken, which is | reasonable though not required, the values of non-reference type | registers (ints and floats) will be reset. The rference type | registers (strings and PMCs) will also be reset so the pointers to | the string/pmc structs will be what they were when the continuation | was taken, but as they are references the referred-to thing may have | changed and the changed value will be seen. `--------------------------------------------------------------------- NB: the STRING variables also behave like value types: e.g. concat S0, S1 creates a new string in S0, if the storage isn't sufficient to concatenate S1 in place. This seems to imply that e.g. integer count variables are unusable around function calls. The need for a backing store invalidates all efficiency gained by the usage of native types. PMCs and other register types would suddenly have different semantics with the presence of a continuation. Additionally the term "put back" smells like copying register frames, which is known to be highly inefficient. More on this issue is in the thread: Subject: "continuation enhanced arcs" Date: Mon, 22 Nov 2004 with another summary in my discussion with Piers: ,--[ Leo ]--------------------------------------------------------------- | Piers Cawley <[EMAIL PROTECTED]> wrote: | > Okay, I'm confused, I thought that the whole point of a caller saves, | > continuation passing regime was that the caller only saves what it's | > interested in using after the function returns. | | We don't have a problem WRT register preservation, the problem arises | due to register re-using. | | > ... Exactly *where* that | > return happens, and whether it happens more than once, is completely | > irrelevant from the point of view of the caller. | | The return can only happen, where the normal function call would have | returned, but anyway. | | > ... ISTM that the register | > allocator should work on the principle that anything it didn't save | > before it made the call will be toast afterwards. | | Yes. But - please remember your example "Fun with nondeterministic searches". | Here's the relevant piece of code from main: | | arr1=[1,3,5] | arr2=[1,5,9] | x = choose(arr1) | y = choose(arr2) | $P0 = find_lex "fail" | $P0() | | You know, both "choose" calls capture the continuation and backtrack via | "fail" (basically). But the register allocator isn't aware of that. The | control flow graph (CFG) is linear top down, with new basic blocks | starting after each function call. "arr2" is obviously used around a | call and allocated in the preserved (non-volatile) register area. This | works fine. | | Now the register allocator assigns a register to "$P0". It finds the | register that "arr2" had usable, because in a linear CFG, there's no way | that "arr2" might be used again. So that register is considered being | available. Now if $P0 happens to get the register that "arr2" had, | backtracking through the call to "fail()" obviously fails, as "arr2" is | now the Closure PMC. And that was exactly the case. `-------------------------------------------------------------------------- As the problem isn't register preserving per se, but register re-using, it seems to me that any "solution" that involves register copying isn't correct. Value registers would be restored to a previous state, pointer registers keep on pointing to the same item. ,--[ Luke ]--------------------------------------------------------------- | ... The problem is the | semantics. If you copy the registers, then when you invoke the | continuation, their *values* restore to what they were when you made the | continuation. These are not proper semantics, and would result in | subtle, incorrect infinite loops. `------------------------------------------------------------------------- My proposal to attack this problem is here: Subject: Lexicals, continuations, and register allocation Date: Tue, 23 Nov 2004 which basically states: we use a variable sized register frame, where lexicals and preserved temporaries have a distinct storage. ,--[ Ken Fox ]--------------------------------------------------------- | A very strong architecture for sure. | | > + no lexical fetch overhead | | That alone is worth the price of admission. No register allocator | needed because the HLL only needs volatiles for anonymous temporaries | which are easily allocated during expression parsing. `---------------------------------------------------------------------- Dan was mandating the register preserving idea: ,--[ Dan ]---------------------------------------------------------- | ... We mandated that call/return preserved the top 16 | registers of all the types automatically. That's *all* we did. The | rest is implementation detail. `------------------------------------------------------------------- which IMHO does not solve the issue at all. Related but also abandoned is my proposal: Subject: [PROPOSAL] for a new calling scheme Date: Tue, 16 Nov 2004 which has some ideas about variable sized register frames. leo
