A safe replacement for computed goto

Dmitry Olshansky dmitry.olsh at gmail.com
Tue Mar 27 08:52:29 PDT 2012


On 27.03.2012 16:24, Dmitry Olshansky wrote:
> On 27.03.2012 1:07, Timon Gehr wrote:
>> On 03/26/2012 09:10 PM, Dmitry Olshansky wrote:
>>>
>>> Speaking more of run-time version of regex, it is essentially running a
>>> VM that executes instructions that do various kinds of match-this,
>>> match-that. The VM dispatch code is quite slow, the optimal _threaded_
>>> code requires either doing it in _assembly_ or _computed_ goto in the
>>> language.
>>
>> Language-enforced tail call optimization would probably work too.
>
> Indeed it would.
> I recall being close to that observation, when I pictured a feature like
> guaranteed non-return function call, a-la:
> void foo()
> {
> ...
> goto fn(); //can safely overwrite foo's stack frame
> //never gets here
> }
>
> kind of unix exec for functions.
>

Come to think of it, I like my small feature more then full computed 
gotos. Because if properly implemented it doesn't violate memory safety.

Namely add to the language new statement:
goto Call-expr;

To designate a switch-to call, or forced tail call.
That must be semantically equivalent to:
1. Save arguments on stack.
2. Move them over current stackframe, overwriting it in the process.
3. Use jump instead of call, step 2 should place params as per ABI for 
function call.
Steps 1-2 should be combined into one and optimized as necessary.

Rationale:
1. It allows implementing threaded VM interpreter in @safe D code, 
that's quite a feat.
(VM is the main use case for computed gotos btw, but they are not safe)
2. More then that it provides the ability for programmer to make 
assumptions about code that relies on tail-call optimization. Previously 
such code would be either very fragile or only usable in release mode.
3. Avoids problematics of providing pointer type for labels.

I can imagine it may be useful for parallel work stealing framework, and 
threading in general.

Problem: C-style function call convention, namely the caller responsible 
for restoring the stack.
Ways to solve:

a) require callee cleanup convention for functions that are goto'ed. 
 From what I see on D ABI page it works for extern(D) on win32 only(?):

 > The callee cleans the stack.

b) provide some kind of hack to restore original stack pointer on 
eventual return, so that caller correctly cleans it up.

-- 
Dmitry Olshansky


More information about the Digitalmars-d mailing list