# HG changeset patch # User Shinji KONO # Date 1276717109 -32400 # Node ID b6c8eda48e39150b10678993401afd5b3394cbc6 first try diff -r 000000000000 -r b6c8eda48e39 CbC and Test.mm --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/CbC and Test.mm Thu Jun 17 04:38:29 2010 +0900 @@ -0,0 +1,96 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff -r 000000000000 -r b6c8eda48e39 cbc.ind --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cbc.ind Thu Jun 17 04:38:29 2010 +0900 @@ -0,0 +1,149 @@ +-title: Testing and Equivalence using Continuation based C + +--abstract: + +Continuation based C (CbC) is a language without function call. We have implemented +the language in GCC. This language is suitable for embedded systems or +many core architecture such as Cell, GPGPU or Core i7 architecture. In order +to achieve high performance, special features are necessary like vector processing, +stream arithmetic or Open CL like parallel processing, +which is usually difficult to use and its correctness is uncertain. +In CbC, these special features themselves can be expressed. +We show how to use CbC in Testing and +Equivalence when we use special features. + +--Programming Language for Code Generation + +Today, quite large size softwares are written and working. +Many of them are half generated by computer itselves. +For an example, GCC (GNU compiler collection)\cite{gcc} generates many insn-*.c +file from machine description. Another example is Scala\cige{scala}, which +generates Java Byte Code. Ruby on rails generates ruby scripts. + +We are developping Continuation based C, here after CbC \cite{cbc}, which is suitable for +state machine description, which is also good for compiler target language. +CbC has two basic elements, code segment and data segment. Code segements are +connected by parameterised goto statements. Data segments are exchanged among code segments. Data segment is designed to fit in various Many Core Architecture such as Cell\cite{cell}. + +Generated code is supposed to work efficiently, but it have to running on sepcial +hardware sometimes. Often generated code is modified or is implemeted in a hardware +to achieve high performance. We can use any programming language as a generation +target, but we focus on these points, + + Effective usage of special architecture, + Representation of behavior, + Modularity, + Testability, + Memory awareness. + +In CbC, a large software is divided into units which roughly equal basic block +of compiler. Since CbC has no implicit environment, that is stack, code state +is fully represented in an input interface of the code segment. Of course, +the input interface may have complex state, for example, simulated stack, +but we can insert test code between two code segments. This is our basic +idea. + +In this paper, we describe Continuation based C and its code segment and data +segment system and its implementation on gcc. We will discuss the software +architecture of CbC and Cerium Task Manager for PS3\cite{ps3}, then we +discuss our testing method for CbC. + +--Continuation based C + +A code segment in CbC is a normal C function actually. It has no return value and +no return statement, if it has it it will be an error. To exit the code segment, +goto statement to other or same code segment is used. Besides return statement, +any C statement can be used, normal C function is allowed also. + + __code code1(int a, int b) { + goto code2(a,b); + } + +\verb+__code+ is a type of function. Arguments of code segment arel called input +interface and arguments of goto statement are called output interface. In our +system, input / output interfaces are usually a set of data segments, which we +discuss it later. + +It is possible to convert C program into CbC with no funcion calls, using a +kind of CPS transformation \cite{cbc-c} (in Japanese). + +A pointer to a code segment is a light weight continuation, since it has no +environment. This is becase code segment has no return. In this way code +segment is different from normal C function. + +Unfortunately, ANSI-C has no recursive type, we cannot write exact type +of continuation, but it is not a seriaus problem. It is written like this. +Detailed parameter definitions are ommited. + + __code code1(int a, int b, __code (*cont)(int a, int b, __code (*cont1)()) ) ; + goto (*cont1)(a,b, cont1); + } + +In many case, many forward reference requires many prototype declaration. In CbC, +these definitions are automatically generated (by scripts). + +---Interaction with C function + +Since CbC is a C, any C function can be called in a code segment. To enter a +code segment from a C function, a parameterised goto is used, but it has +no return. To return from a code segment, full continuation ( continuation +with full environment) is used. A buitl-in function \verb+__CbC_return+ and +\verb+__CbC_environment+. + + typedef __code (*return_type)(int, void*); + __code f(return_type cont,void *env) { + goto (*cont)(10,env); + } + + int + main(int argc, char **argv) + { + return_type cont = _CbC_return; + void *env = _CbC_environment; + goto f(cont,env); + } + +In a function \verb+f+, cont contains a code segment to return value +from \verb+main()+. \verb+env+ is a pointr to the environment, that is +a frame pointer or stack pointer. + +If you want to return to a middle of a fuction, put a function call. + +Of course, in Unix, you can simply \verb+exit()+ from a code segment. +This is much simpler. + +--Langugage Implementation + +We have to implementation of CbC, one is a hand writtern compiler and +the other one is a patched gcc. + +The modification of GCC is not so large. In a \+verb+c-parse.c+ and +\verb+exapnd_call.c+. In a parse, \verb+__code+ type , CbC_return, +CbC_environment+ is added. CbC_return geneartes a code segment using +a nested function in GCC. + +In call.c, a code segment is handle as a forced tail call eliminaton. +In GCC, tail call elimination is easily gave up, which is not allowed +in CbC. So some modification is necessary. + +In GCC, CbC code segment has fixed stack frame size. If called +stack frame size is small than caller, no TCE is performed. +Argmeents in goto statement parmeter must not overrapped. +In order to assure this, we simplly copy argments to newly +created variable at the parse level. + +If we use normal C sype ABI (argument passing convention), +i386 version runs very slow, becase all arguments have to +be in a stack. To avoid this, FASTCAlL option is +forced in all code segments. This is quite good in EMT64 modee +which has more register. + +--Data Storage Implemantation + +--Software Architecture + +--Execution Model + +--Testing method +--Comparison +