www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Explicitly unimplemented computed gotos

reply bearophile <bearophileHUGS lycos.com> writes:
When I have suggested to add "computed gotos" (similar to the ones of GCC) to
D, Walter has answered that they need some work to be implemented, and they
have limited usefulness, almost only to optimize interpreters.

But:
- D is a system language, so writing interpreters is an important application
of it.
- I have found GCC computed gotos useful to speed up some of my code. Recently
even the CPython has introduced their usage in the main interpreter loop.
- The GCC implementation of computed gotos is not standard for C and other
compilers may not understand it (to solve this trouble in GNU C code you need
to disable pieces of code, and this is less easy to do in D).

So even if computed gotos are not going to be implemented in DMD I suggest to:
1) Invent a syntax to represent and use them (probably the GCC syntax is good,
because it's already known in C).
2) Make DMD understand this syntax, but refuse it at compile time (because DMD
doesn't support computer gotos).
3) Define a new standard Predefined Version, like "computed_goto" or
"Computed_goto" or something similar, that is defined if a D compiler supports
them (so DMD doesn't define it), that allows to disable the code that contains
the computed goto if a compiler doesn't support them.

This:
- Allows other D implementations, based on LLVM and GCC back-ends that already
support computed gotos, to support such gotos in D code too;
- Allows the programmer to write two versions of a performance-critical routine
with and without computed gotos, in a clean way just like is done for
version(D_InlineAsm_X86){...}else{...}.
- Gives a single standard common syntax that all future D compilers may use,
avoiding troubles caused by nonstandard syntax and implementations.

(Explicitly unimplemented features have a precedent in D, the array operations.
The difference is that D may never implement computed gotos.)
(This an additive feature, so it may be left for D3 too.)

Bye,
bearophile
Nov 25 2010
next sibling parent Jimmy Cao <jcao219 gmail.com> writes:
--001485f4501ae5d57f0495ee71e6
Content-Type: text/plain; charset=ISO-8859-1

Good suggestion for a D3 feature.
Wikipedia says this is also called an "Assigned Goto."
It could make writing interpreters more efficient.

On Thu, Nov 25, 2010 at 9:55 PM, bearophile <bearophileHUGS lycos.com>wrote:

 When I have suggested to add "computed gotos" (similar to the ones of GCC)
 to D, Walter has answered that they need some work to be implemented, and
 they have limited usefulness, almost only to optimize interpreters.

 But:
 - D is a system language, so writing interpreters is an important
 application of it.
 - I have found GCC computed gotos useful to speed up some of my code.
 Recently even the CPython has introduced their usage in the main interpreter
 loop.
 - The GCC implementation of computed gotos is not standard for C and other
 compilers may not understand it (to solve this trouble in GNU C code you
 need to disable pieces of code, and this is less easy to do in D).

 So even if computed gotos are not going to be implemented in DMD I suggest
 to:
 1) Invent a syntax to represent and use them (probably the GCC syntax is
 good, because it's already known in C).
 2) Make DMD understand this syntax, but refuse it at compile time (because
 DMD doesn't support computer gotos).
 3) Define a new standard Predefined Version, like "computed_goto" or
 "Computed_goto" or something similar, that is defined if a D compiler
 supports them (so DMD doesn't define it), that allows to disable the code
 that contains the computed goto if a compiler doesn't support them.

 This:
 - Allows other D implementations, based on LLVM and GCC back-ends that
 already support computed gotos, to support such gotos in D code too;
 - Allows the programmer to write two versions of a performance-critical
 routine with and without computed gotos, in a clean way just like is done
 for version(D_InlineAsm_X86){...}else{...}.
 - Gives a single standard common syntax that all future D compilers may
 use, avoiding troubles caused by nonstandard syntax and implementations.

 (Explicitly unimplemented features have a precedent in D, the array
 operations. The difference is that D may never implement computed gotos.)
 (This an additive feature, so it may be left for D3 too.)

 Bye,
 bearophile

--001485f4501ae5d57f0495ee71e6 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Good suggestion for a D3 feature.<div>Wikipedia says this is also called an= &quot;Assigned Goto.&quot;</div><div>It could make writing interpreters mo= re efficient.<br><br><div class=3D"gmail_quote">On Thu, Nov 25, 2010 at 9:5= 5 PM, bearophile <span dir=3D"ltr">&lt;<a href=3D"mailto:bearophileHUGS lyc= os.com">bearophileHUGS lycos.com</a>&gt;</span> wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex;">When I have suggested to add &quot;computed= gotos&quot; (similar to the ones of GCC) to D, Walter has answered that th= ey need some work to be implemented, and they have limited usefulness, almo= st only to optimize interpreters.<br> <br> But:<br> - D is a system language, so writing interpreters is an important applicati= on of it.<br> - I have found GCC computed gotos useful to speed up some of my code. Recen= tly even the CPython has introduced their usage in the main interpreter loo= p.<br> - The GCC implementation of computed gotos is not standard for C and other = compilers may not understand it (to solve this trouble in GNU C code you ne= ed to disable pieces of code, and this is less easy to do in D).<br> <br> So even if computed gotos are not going to be implemented in DMD I suggest = to:<br> 1) Invent a syntax to represent and use them (probably the GCC syntax is go= od, because it&#39;s already known in C).<br> 2) Make DMD understand this syntax, but refuse it at compile time (because = DMD doesn&#39;t support computer gotos).<br> 3) Define a new standard Predefined Version, like &quot;computed_goto&quot;= or &quot;Computed_goto&quot; or something similar, that is defined if a D = compiler supports them (so DMD doesn&#39;t define it), that allows to disab= le the code that contains the computed goto if a compiler doesn&#39;t suppo= rt them.<br> <br> This:<br> - Allows other D implementations, based on LLVM and GCC back-ends that alre= ady support computed gotos, to support such gotos in D code too;<br> - Allows the programmer to write two versions of a performance-critical rou= tine with and without computed gotos, in a clean way just like is done for = version(D_InlineAsm_X86){...}else{...}.<br> - Gives a single standard common syntax that all future D compilers may use= , avoiding troubles caused by nonstandard syntax and implementations.<br> <br> (Explicitly unimplemented features have a precedent in D, the array operati= ons. The difference is that D may never implement computed gotos.)<br> (This an additive feature, so it may be left for D3 too.)<br> <br> Bye,<br> <font color=3D"#888888">bearophile<br> </font></blockquote></div><br></div> --001485f4501ae5d57f0495ee71e6--
Nov 25 2010
prev sibling next sibling parent Adam D. Ruppe <destructionator gmail.com> writes:
bearophile wrote:

 1) Invent a syntax to represent and use them (probably the GCC syntax is good,

I'd argue that we have a syntax reserved for them already: switch(x) { case 0: case 1: case 2: [......] } And this is just a little optimization in the generated code. (Specifically: if a switch has integer cases that fill in a whole range from [0..n), it could be rewritten as pre-caching the addresses in an array of length n and the dispatch simply be written as a jump to the entry in that array.) The beauty of using switch is it continues to work even in compilers that don't implement the optimization, without having to write the code twice.
 The difference is that D may never implement computed gotos.

I'm actually pretty amazed that we can't really do them right now with the inline assembler. Well... actually, we can, but it isn't the most beautiful implementation. Check this out: ======= void main() { void* val; lbl1: asm { call near ptr $+2; // call this location + 2 bytes - that is, the address of the pop instruction jmp short lbl2; // FIXME: if the jmp isn't actually short, the whole thing blows up! This feels like an assembler bug; it should probably bitch that I'm asking for the impossible instead of just ignoring the short pop ESI; // it now holds the address pushed by call mov EAX, ESI; // load up the address for some work... add AL, [ESI - 1]; // ESI is address of the jmp opcode. +1 is the offset of the jump... thus adding it gets the absolute address of the label. FIXME: what if al overflows? mov [val], EAX; // store it jmp [val]; // and let's go ahead and make the computed goto. The program should print "34" } printf("2"); lbl2: printf("3"); lbl3: printf("4"); } ========= (I used printf to make the object dump a bit shorter than with writefln) If you change to lbl3 it correctly prints 4. My voodoo worked! If that were wrapped up into a string mixin and fixed those FIXME's - not terribly hard in this specific case, but might be hard to generalize - we'd have a general way to getLabelAddress and jumpToPointer (the latter being trivial - that one jmp [val]; instruction) implemented right in the library. It won't be as efficient as a compiler generated jump table, but initialization is unlikely to be a big deal here anyway. (What this code does is take the compiler's generated code and reads it back at runtime! Obviously skipping that read back at runtime step would be a lil faster, but since it is a one time cost it can probably be ignored.) I've started the mixin solution but it isn't quite right yet. I'm thinking I have an off by one error when populating the array. Been a while since I've done machine code reading and manipulation like this and it is getting late. Nevertheless, I'm pretty convinced that the language offers everything we need to implement this in the library right now, albeit the initialization won't be 100% perfect. If I can fix this minor error in my current mixin loop, we can get very close. Of course, reading the program's own binary code isn't the most elegant implementation, but the usage is simple enough: // first is the name of the array to create, then the names of the labels with which to populate it mixin(getLabelAddresses!("labels", "lbl1", "lbl2", "lbl3", "lbl4")); mixin(gotoPointer!("labels", 3)); // array name and index to jump to Anyway I spent way too much time on this. Gotta get to bed. But my feeling on the proposal again: 1) We have a syntax that works this way: switch(). The optimizer could, in theory, recognize this usage and create it. 2) We have an inline assembler that can surely do the job. Let's use it and see what we can do.
Nov 25 2010
prev sibling parent reply Iain Buclaw <ibuclaw ubuntu.com> writes:
== Quote from bearophile (bearophileHUGS lycos.com)'s article
 When I have suggested to add "computed gotos" (similar to the ones of GCC) to
D,

limited usefulness, almost only to optimize interpreters.
 But:
 - D is a system language, so writing interpreters is an important application
of it.
 - I have found GCC computed gotos useful to speed up some of my code. Recently

 - The GCC implementation of computed gotos is not standard for C and other

disable pieces of code, and this is less easy to do in D).
 So even if computed gotos are not going to be implemented in DMD I suggest to:
 1) Invent a syntax to represent and use them (probably the GCC syntax is good,

 2) Make DMD understand this syntax, but refuse it at compile time (because DMD

 3) Define a new standard Predefined Version, like "computed_goto" or

them (so DMD doesn't define it), that allows to disable the code that contains the computed goto if a compiler doesn't support them. I don't think this feature really warrants a new keyword. Since we already have: const var = 42; switch (x) { case var: ... break; } Would only make sense to do the same for goto's. goto *ptr; Something that *would* warrant perhaps a new keyword would be non-local gotos, but it's usefulness is very negligible... Regards Iain
Nov 26 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Iain Buclaw:

 I don't think this feature really warrants a new keyword.

I have not asked for a new keyword.
 Something that *would* warrant perhaps a new keyword would be non-local gotos,
but
 it's usefulness is very negligible...

I don't like those :-) Bye, bearophile
Nov 26 2010