Implementating Continuation based language in Clang and LLVM

Objective

• Achieve Reliable computation
• Extract Concurrent Execution Automatically
• Modify and Improve software in a Reliable way
• Get more Reusablity

Introducing new units of programming

Traditional units of programming

• Machine instruction
• Statements of programming language
• Function call / Method
• Module / Class / Interface
• Thread / Process
• Object
• Record / Table

What we want to do with programming units?

• Divide large functions into small parts.
• Add hidden arguments without code modification.
• Add meta computation.
• Extract concurrency from programming units.

It is not easy to do this in the traditional units.

New programming units

• Units of programming: code segments, data segments.
• Code segments are units of calculation.
• Data segments are sets of typed data.

Code segments

• Function from input data segments to output data segments.
• Code segments have no states.
• Access in typed data in the data segments by name.
• Specify code segments to be executed using goto.

It is easy to divide or combine.

Data segments

• Set of typed data.
• Type signatures are in meta data segments.
• Variable and extendable data structure.
• Data segments are dominated by connected code segments.
• Code segments atomically access connected data segments.

It is easy to divide or combine.

Meta code / data segments

• Execution contexts: Thread
• Type signatures of data segments.
• Data segment linkages: Pointer
• Machine code of code segments

Continuation based C (CbC)

• An implementation of code segments.
• CbC stands for Continuation based C.
• Basic syntax is the same as the C, except __code and goto.
• __code is a type of code segment
• Code segments end with parameterized goto.
• Data segments are implemented as C structures.

code segment syntax

__code f() {
    goto g();
}

__code g() {
    goto h();
}
              

code segment syntax with data segments

__code code1(struct Allocate* allocate,
            struct Element* element) {
    element ->value        = 10;
    struct List* list = (struct List *)malloc(sizeof( struct List));
    goto append(allocate,list, element);
}

__code append(struct Allocate* allocate, struct List* list, struct Element* element) {
    if(list->head) {
        list->tail->next = element;
    } else {
        list->head = element;
    }
    list->tail       = element;
    list->tail->next = 0;
    goto code2(allocate,list, element);
}
              

CbC compilers

• Micro-C(one pass standalone compiler) 2001
• on GCC(GNU Compiler Collection) 2008
• on LLVM and Clang (Compiler framework) 2014
  • The latest!

LLVM and Clang's compilation flow

• AST : Abstract Syntax Tree (C++ object)
• LLVM IR is Intermediate Representation (bit code).
• Clang translate C/C++/Obj-C into LLVM IR.
• SelectionDAG : Code generator internal
• Machine Code : LLVM Machine code

Advantage of LLVM implementation

• Apple supported (working on OS X).
• OS X default compiler.
• LLVM IR is well documented.
• better than GCC

CbC implementation strategy

• define special type __code for code segments
• no code segment prototyping (otherwise it becomes quite messy )
• code segments are implemented as tail call force functions
• Do not modify IR (Intermediate representations )
• goto statement is actually a function call with following return statement
  goto f() --> { f() ; return; }
• allow mixing code segments and normal function calls ( goto with environment )

LLVM IR

• Intermediate Representation (bit code).
• Three forms: in-memory IR, bitcode stream, human readable language.
• it has precise type, data size, alignment
• function call flags : tail, fastcc, cc10, cc11, Erlang, ghc

define fastcc void @factorial(i32 %x) #0 {
  entry:
  tail call fastcc void @factorial0(i32 1, i32 %x)
  ret void
}
              

CbC implementation strategy

• Code segments are implemented by C functions with return-type __code.
• Data segments are implemented by C structs.
• Goto statement is implemented by setting tail call flag.
• Goto with environment is implemented by setjmp and longjmp.

Prototype declaration generating

• In CbC, programmer write a lot of code segments.
• Automatically prototype declarator support it.
• If the declaration was not found, search definition and generate declaration.
  • Of course you can write declaration yourself too.

__code code1(int a, int b) {
     :
  goto code2(a,b);
}

__code code2(int a, int b){
     :
}
              

__code code2(int a, int b);
__code code1(int a, int b) {
     :
  goto code2(a,b);
}

__code code2(int a, int b){
     :
}
              

goto syntax for transition

• Add return statement after goto transition.
• It is one the requirement force to tail call elimination.

__code code1() {
     :
  goto code2();
}
              

void code1() {
     :
  code2();
  return;
}
              

Forcing Tail Call Elimination

Tail call flag is set in CodeGen.

Ensure TCE in SelectionDAGISel.

What is tail call elimination?

• Tail call is a function call immediately followed by return.
• If stack frame have to be unchanged,
• Tail call elimination replace tail call's call instructions with jmp instructions.
• that is tail call function should have the same arguments and the same return type

Tail Call Elimination requirements

• Set tail flag at the code segments call.
• Tailcallopt path is enabled in the compiler.
• The caller and callee's calling conventions must be the same and their types should be cc10, cc11 or fastcc.
• Return value type has to be the same as the caller's.

Forcing Tail Call Elimination

• Always add tail call elimination pass.
• Tailcallopt is enabled in CbC.
• Fast cc is used consistently in code segments call.
• All the code segments return value type is void.

goto a code segment from a normal C function

• Assume we have code segment g and normal function f
• simply goto g() in C function f()
• goto g() never returns to function f

Goto with environment

We want provide continuation of function f. The continuation is not a simple code segment, because code segment has not state. We represent the continuation with a code segment (__return) and a meta data segment (__environment).

Syntax of Goto with environment

__code code1(int n,__code(*exit_code)(int,void *),void *exit_env){
  printf("code1 : code entry1\n");
  goto exit_code(n,exit_env);
}

int caller(){
  printf("caller : main1 entry\n");
  __code (*__ret)(int, void *) = __return;
  struct __CbC_env *__env = __environment;
  goto code1(1, __ret, __env);
  return 0;
}

int main(){
  int n;
  n = caller();
  printf("return = %d\n",n);
  return 0;
}      

Implementation of goto with environment

• setjmp/longjmp (LLVM)
• nested function closure with thread safe variable (GCC)
• direct manipulation of frame pointer and return value (Micro-C)

LLVM Implementation of goto with environment

• Include setjmp.h internally.
• Generate C struct for saving environment.
  • This struct is __environment.
• Insert setjmp in C function.
• Generate longjmp code segment as return.
  • This code segment is pointed by __return.

Compiling result

__code caller(int x)
{
  goto code1(1, x); // should be jmp
}
              

_caller:                             ## @factorial
        .cfi_startproc
## BB#0:                                ## %entry
        subq    $24, %rsp
Ltmp5:
        .cfi_def_cfa_offset 32
        movl    $1, %eax
        movl    %edi, 20(%rsp)          ## 4-byte Spill
        movl    %eax, %edi
        movl    20(%rsp), %esi          ## 4-byte Reload
        addq    $24, %rsp
        jmp     _code1             ## TAILCALL
        .cfi_endproc
              

• Code1 should called by jmp instruction.
• In assembly code, code1 called by jmp instruction.
• Tail call elimination was forced.
• If tail call elimination was failed, compiler output error messages.

Conclusion

• CbC compiler on LLVM and Clang is implemented.
• LLVM IR is not modified.
• goto with environment is implemented by setjmp and longjmp.
• Automatic prototype generating.

Future works

• Write operating system in CbC.
  • Gears OS
• Meta computation syntax.
• More user friendly syntax.
• Automatic data segment generator.
• Signature for data segment.

LLVM and Clang's intermediate representations