Implementating Continuation based language in Clang and LLVM

Objective

• Reliable computation
• Concurrent execution
• Reliable improvement
• 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 in the traditional units.

New programing 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 segmnets 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

Meta code segments are executed right after the goto.

Meta data segments are kinds of process data.

Continuation based C (CbC)

• An implementation of code segments.
• CbC stands for Continuation based C.
• Basic syntax is the same as the C.
• Code segments are set of C statements with goto.
• Data segments are inplemented as C structures.

CbC sample

__code f() {
    goto g();
}

__code g() {
    goto h();
}
              

CbC sample with data segments

__code code(struct Context* context, struct Allocate* allocate,
            struct Element* element) {
    allocate->after_append = Code2;
    element ->value        = 10;
    goto meta(context, Append);
}

__code append(struct Context* context, 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 meta(context, allocate->after_append);
}

__code meta(struct Context* context, enum Code next) {
    goto (context->code[next])(context);
}
              

CbC compilers

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

What are LLVM and Clang?

• Compiler frameworks.
• has a intermidiate language which is called LLVM IR, LLVM language or LLVM bitcode.
• Translates LLVM IR to assembly language.
• Many kinds of optimization.
• Clang is C, C++ and Obj-C compiler frontend.
• Clang uses LLVM for compiler backend.

Why?

• Apple supported.
• OS X default compiler.
• LLVM IR has readable documents.
• More readable and modifiable than GCC.

LLVM and Clang's compilation flow

• Clang translate C/C++/Obj-C into LLVM IR.
• LLVM translate LLVM IR into assembly code.
• LLVM optimize all of intermidiate representation.

LLVM and Clang's intermidiate representations

• clang AST
• LLVM IR
• SelectionDAG
• Machine Code
• MC Layer

Intermidiate representations are not modified.

Clang AST

• Abstract Syntax Tree.
• Representation of the source codes structure.
• Basic node type: Stmt, Decl, Expr.

LLVM IR

• The main intermidiate representation.
• LLVM translate it into assembly codes.
• Three forms: in-memory compiler IR, on-disk bitcode, assembly language.

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

Basic strategy of implementating

• Code segments are implemented by C functions.
• Data segments are implemented by C structs.
• Transition is implemented by tail call elimination.
• Goto with environment is implemented by setjmp and longjmp.
  • Goto with environment enable code segments to return C functions.

Parser

• __code type
• Prototype declaration generating
• Goto syntax for transitions

__code type

• Code segments as __code type functions.
• Handled like void functions.

Prototype declaration generating

• In CbC, programmer write a lot of code segments.
• When function pointer's arguments are omitted, TCE was failed sometimes.
• Automatically prototype declaration generating saves a lot of effort.
• When parser meet a code segment call, it stop current parsing and search called code segment declaration.
• If the declaration was not found, search definision 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

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

TCE is enabled at CodeGen.

TCE is act at SelectionDAGISel.

What is tail call elimination?

• Tail call is immediately followed by return.
• Tail call elimination replace tail call's call instructions with jmp instructions.
• Transitions are implemented by forced tail call elimination.

Forcing Tail Call Elimination

• LLVM IR has function call flags.
• tail mean it is tail call.
• Calling convention tell compiler how callee functions receive parameters from their caller.

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

Forcing Tail Call Elimination

Tail Call Elimination requirements

• Set tail flag at the code segments call.
• Tailcallopt is enabled.
• The caller and calle'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.

What is a Goto with environment?

• Code segments can reutn C functions by Goto with environment.
  Code segment do not have return.
• In the GCC, use nested functions.
• In the LLVM and Clang, use setjmp and longjmp.

Sample code 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;
}      

Implementing goto with environment

• Include setjmp.h always.
• 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.
• Automitic data segment generator.
• Signature for data segment.

LLVM and Clang's intermidiate representations