adam@visix.com (03/28/91)
How can I (efficiently) program in a continuation-passing style in C?
This breaks down into two basic questions:
(1) How do I explicitly jump across functions
(2) How do I keep things in registers across functions
Simple example:
main()
{
register int a, b, c;
a=1; b=2; c=3;
foo( a, b, c );
baz( a, b, c );
bar( a, b, c );
}
I want the compiler to emit code that
(1) jumps directly from the end of foo to the start of baz, instead of
returning to main only to jump to baz
(2) leaves a, b, and c in registers instead of mucking around on a stack
(or leaves them on the stack instead of popping and pushing them)
Are most compilers smart enough to do this? Is it possible to trick
most compilers into doing this (how do I get it to emit the right jump?)
Am I being anal about performance?
More complex example:
main()
{
register int a, b, c;
a=1; b=2; c=3;
foo( a, b, c, baz, bar );
c++;
}
foo( a, b, c, afn, bfn )
register int a, b, c;
int (*afn)();
int (*bfn)();
{
if (a > b)
afn( a, b, c );
else
bfn( a, b, c );
}
Same questions: can I force a jump from the end of afn back to main
(tail recursion)? Can I force a, b, and c to stay in registers?
Should I just trust the compiler? (the compiler is your *friend*...)
I guess I can use setjmp/longjmp for the complex example, except that
if I had a real (long) tail-recursive chain I wouldn't want to be
allocating stack frames in the first place; I should replace them with
each successive call.
But I can't use setjmp/longjmp at all for the simple example.
There are two solutions I can think of.
/* Number 1 */
main()
{
register int r1, r2, r3, r4, r5, continuation;
r1 = 1; r2 = 2; r3 = 3; r4 = BAZ; r5 = BAR;
continuation = FOO
while(1)
{
switch (continuation)
{
case MAIN2:
r3++;
continuation = DONE;
break;
case FOO:
if (r1 > r2)
continuation = r4;
else
continuation = r5;
break;
case BAZ:
continuation = MAIN2;
break;
case BAR:
continuation = MAIN2;
break;
case DONE:
exit(0);
}
}
}
/* Number 2 */
static void (*continuation)()
static int r1, r2, r3, r4, r5;
done()
{
exit(0);
}
main2()
{
r3++;
continuation = done;
}
baz()
{
continuation = main2;
}
bar()
{
continuation = main2;
}
foo()
{
if (r1 > r2)
continuation = r4;
else
continuation = r5;
}
main()
{
r1 = 1; r2 = 2; r3 = 3; r4 = baz; r5 = bar;
continuation = foo;
while(1)
{
(*continuation)();
}
}
Okay, it's twisted. That's the point :-).
Actually, I kind of like Number 2, except that I can't force my
registers to really be registers.
Is there anything better?
Adamadam@visix.com (03/28/91)
Adam, you ignorant slut.
case FOO:
if (r1 > r2)
continuation = r4;
else
continuation = r5;
-> r4 = MAIN2;
break;
case BAZ:
-> continuation = r4;
break;
case BAR:
-> continuation = r4;
break;
baz()
{
-> continuation = r4;
}
bar()
{
-> continuation = r4;
}
foo()
{
if (r1 > r2)
continuation = r4;
else
continuation = r5;
-> r4 = main2;
}
Yes, I should fix the pointer/int conflict, but that's secondary to
the problem at hand.
Adamtorek@elf.ee.lbl.gov (Chris Torek) (03/29/91)
In article <1991Mar28.070649.1667@visix.com> adam@visix.com writes: >How can I (efficiently) program in a continuation-passing style in C? > >This breaks down into two basic questions: > >(1) How do I explicitly jump across functions >(2) How do I keep things in registers across functions The answers are (1) use assembly language, and (2) use assembly language. If you want this level of control over the machine, C is not the place to look. Compilers capable of this sort of optimization are rare. -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov
gwyn@smoke.brl.mil (Doug Gwyn) (03/29/91)
In article <1991Mar28.070649.1667@visix.com> adam@visix.com writes: > foo( a, b, c ); > baz( a, b, c ); >I want the compiler to emit code that >(1) jumps directly from the end of foo to the start of baz, instead of >returning to main only to jump to baz >(2) leaves a, b, and c in registers instead of mucking around on a stack >(or leaves them on the stack instead of popping and pushing them) Really, why do you care? If this is bottleneck code you should perhaps look for other methods of optimizing it. This degree of attention to code generation is almost always pointless; the compiler will do the best it can to optimize the code it generates, and unless you're maintaining the compiler itself there's not much you can do about it. Indeed some compilers perform that kind of optimization and some do not.
adam@visix.com (03/30/91)
In article <15618@smoke.brl.mil>, gwyn@smoke.brl.mil (Doug Gwyn) writes: |> Really, why do you care? Umm... <thinking> <thinking> <smoke> Because it's fun? Adam