Demonstration of Continuation based C
on GCC

Shinji KONO

University of the Ryukyus

Motivation of Continuation on GCC

   Architecture independent Assembler
Controlling Stack
Programming Unit
Progress from Presented one in Continuation Festa 2008


    Eliminate function call from C
goto a code segment with parameter

       __code f() { goto g() ; }
__code f(__code (*g)()) { goto g() ; }

Co-exists with normal C

    int main1(int n)
goto carg1(0,1,2,3,4,
return n;
goto (*exit1)(0,env);

Return to the caller of main1 (return-continuation)

Good point of code segment

Stateless and depends on Input and output only
if we have no global variable
functional in some sense
but it is not a function
no return
splitting code segment is easy
C compatible
any function call in code segment

2 Implementations

Micro C base

    full implementation of C
MIPS, PPC, IA32, Intel64, ARM
GCC base Implementation

    gcc version 4.4,4.5,4.6

Implementation detail

Force fixed stack size
Arguments copy

    to ensure TCE
removed by optimization
Fast call option

    non standard ABI of arguments
conventional one is very slow (especially in i386)
so gcc does inter-functional optimization
less arguments on stack

Implementation of return-continuation

        __return generates something like...

__label__ _cbc_exit0;
int retval;
void _cbc_internal_return(int retval_, void *_envp){
retval = retval_;
goto _cbc_exit0;
if (0) {
return retval;


Simulation and Model checking

    Scheduling code segment
Enumerate all possible execution
Kernel API description

    read write suspension select socket communication
Game Program



describing state machine
    compiling CbC from regular expression
quite fast (My student said it is the world fastest grep)

__code state_2_3_9_13_23_24_25(char* s) {
        switch(*s++) {
case 'y': goto state_14_15(s); break;
case 'H': goto state_10_11(s); break;
case 'e': goto state_4_5(s); break;
case '\0': goto accept(); break;
default: goto reject();

It works as I expected


    So far so good, but easy implementation has its own...


    quite difficult to write
definitely not for human
gcc language issue
recursive type
fast call
code quality
undebuggable (no stack trace)
type conflict on reconnection

GCC type system

    no recursive type on C
some arguments have to be omitted

a4(int i,__code conv())
goto (*conv)(i+1,a6);
a6(int i,int j,int k,__code conv())
goto conv(i+1,j,k,a8);

Argument and prototype

    We have automatic prototype generator, but
we have to write a lot of function types

    __code (*conv)(int,__code (*)());
__code a2(int i,__code conv());
__code a3(int i,__code conv());
__code a4(int i,__code conv());
__code a5(int i,__code conv());
__code a6();
__code a7();
__code a8();
__code a9();

My compiler is faster than gcc

What are you doing, GCC?
copy remains
bad argument ABI
some architecture prohibit TCE (Sparc, PowerPC)
Bug on indirect jump

My compiler is faster than gcc (mc code)

    ## 1702 ## 15:  result *= n;
movq %r15,%rsi
imull %esi,%r14d
## 1703 ## 16: n--;
addl $-1,%r15d
## 1704 ## 17: goto factorial(n,result,orig,print,exit1,exit1env);
jmp _factorial
## 1700 ## 13: goto (*print)(n,result,orig,print,exit1,exit1env);
movq %r12,%rdi
jmp *%rdi

My compiler is faster than gcc (gcc code)

    L12:    imull   %edi, %eax
testl %esi, %esi
.p2align 4,,6
je L5
movl %esi, %edi
L11: leal -1(%rdi), %esi
cmpl $-1, %esi
jne L12
L5: movl %eax, %esi
movq %r10, %rcx
xorl %edi, %edi
xorl %eax, %eax
addq $24, %rsp
jmp *%r10

Implementation difficulty

curses on gcc implementer

        drastic change on each version  hg graph 
Gimple, SAA, RTL
buggy (4.4, 4.5)
not enough information on non optimization mode -O2 is necessary
gcc easyly give up on TCE (Tail call Elimination)
They hate TCE?
Fastcall is eliminated on 4.6!

Return-continuation difficulty

    handling environment
thread safe
some architecture does not support
gcc dependent
slow but acceptable?


    no stack trace
inserting debug segment
It is not C++

    industry people said so

impossibility of reconnection

    type miss match
fix argument type on applications

New direction

data segment
new syntax
new implementation

Data segment

    Dual of code segment
code segment accepts data segments only
no type conflict on reconnection
Describing memory allocation
Data segment is typed

Pipeline Execution


new syntax

completely new something
typedefrec on C
or no syntax

    code data structure only

new implementation

hand made JIT

Thank you

Come to JSSST 2011 on Okinawa! 9/26-9/29

CbC libc/crt0

    continuation base system call
who create it?
should be gcc built-in

    no so popular
TCE forcing may be useful

Simulation and Model checking

code segment scheduler
state enumerator, state memory database

Simulation and Model checking

First, make single process code segments.

Simulation and Model checking

Second, put scheduler among them.

Simulation and Model checking

Enumerate all states and keep it.

Game Program


Shooting Game on PS2

Code Segment as movement and collision

Intended to parallel execution in PS3

We have task manager in PS3 Cell Many Core, but
it is not written in CbC, but in C++.

Programming Unit

    Smaller programming unit than function
Larger programming unit than statement
As Implementation language
no more machine code generation

Co-exists with normal C

If you want to back here, use normal function.

int main( int ac, char *av[])
    int n;
n = main1(123);
return n;

Translation from C

    We know how to do, but
c2cbc is not yet written
Translation results is rather large
We cannot write large code segments by hands

Concurrent Execution

    code segment is atomic
no other way
if code segments are executed in parallel,
atomicity should be maintained by code itself
do it in manually
no hidden type less stack