www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Feature request: First class labels

reply Paul Findlay <r.lph50+d gmail.com> writes:
First-class labels (or "labels as values" [1]) would make D a much better
platform for implementing interpreters. Is there any chance of having
something like this?

It would mean virtual machine execution could be implemented using direct
threading [2] and make possible all sorts of tricks including using D
compiler generated executable code for JIT [3]. Direct threading often has
less branch mis-prediction than using switches to dispatch VM intructions
[2].

I don't know the cost of implementing this for DMD, but it needn't introduce
a new basic type or keywords to the language.. (perhaps labels could be
typdef'd in std.intrinsics)

Hope this makes sense (both what I've written and as a feature :) )

 - Paul Findlay

1: http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
2; http://www.complang.tuwien.ac.at/forth/threaded-code.html
3: M. Anton Ertl and David Gregg, Retargeting JIT compilers using C-compiler
generated executable code, in Proceedings of the International Conference
on Parallel Architectures and Compilation Techniques (PACT 04), pp. 7-14,
Antibes Juan les Pins, Septmber 2004
(http://www.complang.tuwien.ac.at/papers/ertl%26gregg04pact.ps.gz)
May 05 2007
next sibling parent reply Hasan Aljudy <hasan.aljudy gmail.com> writes:
Paul Findlay wrote:

 First-class labels (or "labels as values" [1]) would make D a much better
 platform for implementing interpreters. Is there any chance of having
 something like this?


I'm not sure I understand ..
Do you mean like, being able to "increment" labels and move them around?


 
 It would mean virtual machine execution could be implemented using direct
 threading [2] and make possible all sorts of tricks including using D
 compiler generated executable code for JIT [3]. Direct threading often has
 less branch mis-prediction than using switches to dispatch VM intructions
 [2].
 
 I don't know the cost of implementing this for DMD, but it needn't introduce
 a new basic type or keywords to the language.. (perhaps labels could be
 typdef'd in std.intrinsics)
 
 Hope this makes sense (both what I've written and as a feature :) )
 
  - Paul Findlay
 
 1: http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
 2; http://www.complang.tuwien.ac.at/forth/threaded-code.html
 3: M. Anton Ertl and David Gregg, Retargeting JIT compilers using C-compiler
 generated executable code, in Proceedings of the International Conference
 on Parallel Architectures and Compilation Techniques (PACT 04), pp. 7-14,
 Antibes Juan les Pins, Septmber 2004
 (http://www.complang.tuwien.ac.at/papers/ertl%26gregg04pact.ps.gz)
May 05 2007
parent Paul Findlay <r.lph50+d gmail.com> writes:
Hasan Aljudy wrote:

 I'm not sure I understand ..
 Do you mean like, being able to "increment" labels and move them around?


Yeah, assign them to variables, store them in arrays and use them as memory
addresses to do stuff like:
        memcpy(dest, &start_label, (&end_label - &start_label));

 - Paul
May 06 2007
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
They're a good idea, but they are a fair amount of work to implement, 
and their utility is not much beyond doing interpreters.
May 06 2007
next sibling parent Paul Findlay <r.lph50+d gmail.com> writes:
Walter Bright wrote:


 They're a good idea, but they are a fair amount of work to implement,
 and their utility is not much beyond doing interpreters.


Or state machines :) But I see your point.

 - Paul
May 06 2007
prev sibling next sibling parent =?ISO-8859-1?Q?Lu=EDs_Marques?= <luismarques+spam gmail.com> writes:
Walter Bright wrote:

 They're a good idea, but they are a fair amount of work to implement, 
 and their utility is not much beyond doing interpreters.


I find them useful. I used them some days ago to get the size of a block 
of code.

Anyway, isn't D going to be an awesome language for interpreters? ;)

--
Luís
May 06 2007
prev sibling parent reply BCS <ao pathlink.com> writes:
Reply to Walter,


 They're a good idea, but they are a fair amount of work to implement,


Mostly just curiosity, but what makes them hard/not-easy?


 and their utility is not much beyond doing interpreters.
 


they can also be used to remove conditionals from loops


|for(int i = 1; i<1000000; i++)
|{
| if(complex_loop_invariant)
|  nothing();
| else
|  that()
| if(complex_loop_invariant2)
|  other();
| else
|  bat();
|}

// no tests in loop.
|void* l1 = complex_loop_invariant ? &&a : &&b;
|void* l2 = complex_loop_invariant2 ? &&c : &&d;
|
|for(int i = 1; i<1000000; i++)
|{
| goto *l1
| a:  nothing();
|     goto l2:
| b:  that()
|     goto l2:
| c:  other();
|     break;
| d:  bat();
|}

and other fun things I can't talk about for a few days
May 06 2007
parent reply =?ISO-8859-1?Q?Lu=EDs_Marques?= <luismarques+spam gmail.com> writes:
BCS wrote:

 // no tests in loop.
 |void* l1 = complex_loop_invariant ? &&a : &&b;
 |void* l2 = complex_loop_invariant2 ? &&c : &&d;
 |
 |for(int i = 1; i<1000000; i++)
 |{
 | goto *l1
 | a:  nothing();
 |     goto l2:
 | b:  that()
 |     goto l2:
 | c:  other();
 |     break;
 | d:  bat();
 |}


I hope people don't use that except in critical inner-loops or 
encapsulated in some form :-)

--
Luís
May 06 2007
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Luís Marques wrote:

 BCS wrote:

 // no tests in loop.
 |void* l1 = complex_loop_invariant ? &&a : &&b;
 |void* l2 = complex_loop_invariant2 ? &&c : &&d;
 |
 |for(int i = 1; i<1000000; i++)
 |{
 | goto *l1
 | a:  nothing();
 |     goto l2:
 | b:  that()
 |     goto l2:
 | c:  other();
 |     break;
 | d:  bat();
 |}


 
 I hope people don't use that except in critical inner-loops or
 encapsulated in some form :-)
 
 -- 
 Luís


What about this?

|for(int i = 1; i<1000000; i++)
|{
| invariant if(complex_loop_invariant)
|  nothing();
| else
|  that()
| invariant if(complex_loop_invariant2)
|  other();
| else
|  bat();
|}

Where "invariant if" is defined as "a conditional statement whose result
is invariant in the current scope, allowing the compiler to optimise and
elide subsequent evaluations until the scope is left."  Or something
like that.

It'd be really cool if this could be extended to the general case inside
of functions, provided there's a way to "reset" the switch.  Maybe
something like this:


 void padd(ubyte[] a, ubyte[] b)
 {
 selectSSE2:
     invariant if( cpuid.hasSSE2 )
     {
         // SSE2 implementation
     }
     else
     {
         // Software implementation
     }
 }

 void reset_padd()
 {
     break padd.selectSSE2;
 }


Which could translate to:


 void* padd_selectSSE2 = &&padd.selectSSE2_init;

 void padd(ubyte[] a, ubyte[] b)
 {
     goto *padd_selectSSE2;

 selectSSE2_init:
     if( cpuid.hasSSE2 )
         padd_selectSSE2 = &&selectSSE2_true;
     else
         padd_selectSSE2 = &&selectSSE2_false;
     goto *padd_selectSSE2;

 selectSSE2_true:
         // SSE2 implementation
         goto selectSSE2_end;
 selectSSE2_false:
         // Software implementation
         goto selectSSE2_end;
 selectSSE2_end:
 }

 void reset_padd()
 {
     padd_selectSSE2 = &&padd.selectSSE2_init;
 }


That might even please the people talking about multi-platform binaries,
especially if the compiler is clever enough to actually re-write the
GOTO on the fly :)

	-- Daniel

-- 
int getRandomNumber()
{
    return 4; // chosen by fair dice roll.
              // guaranteed to be random.
}

http://xkcd.com/

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D
i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP  http://hackerkey.com/
May 06 2007
parent reply janderson <askme me.com> writes:
Daniel Keep wrote:

 
 Luís Marques wrote:

 BCS wrote:

 // no tests in loop.
 |void* l1 = complex_loop_invariant ? &&a : &&b;
 |void* l2 = complex_loop_invariant2 ? &&c : &&d;
 |
 |for(int i = 1; i<1000000; i++)
 |{
 | goto *l1
 | a:  nothing();
 |     goto l2:
 | b:  that()
 |     goto l2:
 | c:  other();
 |     break;
 | d:  bat();
 |}


 I hope people don't use that except in critical inner-loops or
 encapsulated in some form :-)

 -- 
 Luís


 
 What about this?
 
 |for(int i = 1; i<1000000; i++)
 |{
 | invariant if(complex_loop_invariant)
 |  nothing();
 | else
 |  that()
 | invariant if(complex_loop_invariant2)
 |  other();
 | else
 |  bat();
 |}
 
 Where "invariant if" is defined as "a conditional statement whose result
 is invariant in the current scope, allowing the compiler to optimise and
 elide subsequent evaluations until the scope is left."  Or something
 like that.
 
 It'd be really cool if this could be extended to the general case inside
 of functions, provided there's a way to "reset" the switch.  Maybe
 something like this:
 

 void padd(ubyte[] a, ubyte[] b)
 {
 selectSSE2:
     invariant if( cpuid.hasSSE2 )
     {
         // SSE2 implementation
     }
     else
     {
         // Software implementation
     }
 }

 void reset_padd()
 {
     break padd.selectSSE2;
 }


 
 Which could translate to:
 

 void* padd_selectSSE2 = &&padd.selectSSE2_init;

 void padd(ubyte[] a, ubyte[] b)
 {
     goto *padd_selectSSE2;

 selectSSE2_init:
     if( cpuid.hasSSE2 )
         padd_selectSSE2 = &&selectSSE2_true;
     else
         padd_selectSSE2 = &&selectSSE2_false;
     goto *padd_selectSSE2;

 selectSSE2_true:
         // SSE2 implementation
         goto selectSSE2_end;
 selectSSE2_false:
         // Software implementation
         goto selectSSE2_end;
 selectSSE2_end:
 }

 void reset_padd()
 {
     padd_selectSSE2 = &&padd.selectSSE2_init;
 }


 
 That might even please the people talking about multi-platform binaries,
 especially if the compiler is clever enough to actually re-write the
 GOTO on the fly :)
 
 	-- Daniel
 



What about if the compiler just detected the use of a constant, and you 
didn't have to do anything be specify the variables as const.  Also the 
compiler could do a better optimisation on those loops by taking the 
jump out all together and having 4 separate loops.

-Joel
May 06 2007
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
janderson wrote:

 Daniel Keep wrote:

 void padd(ubyte[] a, ubyte[] b)
 {
 selectSSE2:
     invariant if( cpuid.hasSSE2 )
     {
         // SSE2 implementation
     }
     else
     {
         // Software implementation
     }
 }

 void reset_padd()
 {
     break padd.selectSSE2;
 }




 What about if the compiler just detected the use of a constant, and you
 didn't have to do anything be specify the variables as const.  Also the
 compiler could do a better optimisation on those loops by taking the
 jump out all together and having 4 separate loops.
 
 -Joel


If the contents of the conditional were constant, you could just use
static if and remove the branch altogether.

	-- Daniel

-- 
int getRandomNumber()
{
    return 4; // chosen by fair dice roll.
              // guaranteed to be random.
}

http://xkcd.com/

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D
i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP  http://hackerkey.com/
May 06 2007
parent janderson <askme me.com> writes:
Daniel Keep wrote:

 
 janderson wrote:

 Daniel Keep wrote:

 void padd(ubyte[] a, ubyte[] b)
 {
 selectSSE2:
     invariant if( cpuid.hasSSE2 )
     {
         // SSE2 implementation
     }
     else
     {
         // Software implementation
     }
 }

 void reset_padd()
 {
     break padd.selectSSE2;
 }




 What about if the compiler just detected the use of a constant, and you
 didn't have to do anything be specify the variables as const.  Also the
 compiler could do a better optimisation on those loops by taking the
 jump out all together and having 4 separate loops.

 -Joel


 
 If the contents of the conditional were constant, you could just use
 static if and remove the branch altogether.
 
 	-- Daniel
 


I apologies for not being clear, I was talking about the C++ kind.  They 
can be initiated once every time the function is called.

For instance in C++ you can do:

void foo()
{
	const Y = rand();
	printf("%d\n", Y);
}

...

foo()
foo();

Any you'll get different numbers each time.  You can also do this:

void foo(const int X) ...

Clearly the compiler should be able to figure out that X never changes 
if its a simple type.

-Joel
May 06 2007