Mercurial > hg > Papers > 2015 > kaito-lola

comparison cfopm.tex @ 3:c50a033e6635

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
create presentation slide
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Wed, 01 Jul 2015 19:06:07 +0900
parents 771136eae970
children 117760bfcae9
comparison
equal deleted inserted replaced
2:771136eae970 3:c50a033e6635
78 \maketitle 78 \maketitle
79 79
80 % As a general rule, do not put math, special symbols or citations 80 % As a general rule, do not put math, special symbols or citations
81 % in the abstract 81 % in the abstract
82 \begin{abstract} 82 \begin{abstract}
83 The proposed programming paradigm uses data segments and code segments. This paradigm uses Continuation based C (CbC), which is an extension and subset of C. 83 The programming paradigm which use data segments and code segments are proposed. CbC is a slight modified C for this paradigm. CbC has standalone compiler and GCC(GNU Compiler Collection) version. GCC based CbC compiler is developed in 2008\cite{DBLP:journals/corr/abs-1109-4048} and nested function based goto with environment is implemented in 2011\cite{CbC2011}. In this study, we report a latest CbC compiler which is inplemented in LLVM and Clang 3.7. The detail of implementation and evaluation are shown.
84 CbC has a standalone compiler and the GNU Compiler Collection (GCC). This study details and evaluates the implementation of a CbC compiler for LLVM and Clang 3.7.
85 \end{abstract} 84 \end{abstract}
86 85
87 % no keywords 86 % no keywords
88 87
89 88
104 Code segments are units of calculation which have no state. 103 Code segments are units of calculation which have no state.
105 Data segments are sets of typed data. 104 Data segments are sets of typed data.
106 Code segments are connected to data segments by a meta data segment called a context. 105 Code segments are connected to data segments by a meta data segment called a context.
107 After the execution of a code segment and its context, the next code segment (continuation) is executed. 106 After the execution of a code segment and its context, the next code segment (continuation) is executed.
108 107
109 Continuation based C (CbC) \cite{DBLP:journals/corr/abs-1109-4048}, hereafter referred to as CbC, is an extension and subset of C which supports code segments. It is compatible with C and has continuation as a goto statement. 108 Continuation based C (CbC) \cite{DBLP:journals/corr/abs-1109-4048}, hereafter referred to as CbC, is a slight modified C which supports code segments. It is compatible with C and has continuation as a goto statement.
110 109
111 Code segments and data segments are low level enough to represent computational details, 110 Code segments and data segments are low level enough to represent computational details,
112 and are architecture independent. They can be used as architecture independent assemblers. 111 and are architecture independent. They can be used as architecture independent assemblers.
113 112
114 CbC has standalone compiler and GCC version. Here we report new partial implementation of CbC compiler based on LLVM and Clang 3.7. 113 CbC has standalone compiler and GCC version. Here we report new partial implementation of CbC compiler based on LLVM and Clang 3.7.
133 \end{lstlisting} 132 \end{lstlisting}
134 \caption{CbC Example} 133 \caption{CbC Example}
135 \label{src:example} 134 \label{src:example}
136 \end{table} 135 \end{table}
137 136
138 In this example, the code segment {\bf f} takes the input data segment {\bf allocate} (allocate is the data segments identifier) and sends f's outuput to the code segment {\bf g}. The Cbc compiler generates the data segment definition automatically, so writing it is unnecessary. There is no return from code segment {\bf g}. {\bf G} should call another continuation using {\bf goto}. Code segments have one input data segment and several output data segments, and their dependency is proved by the data segments. 137 In this example, the code segment {\bf f} takes the input data segment {\bf allocate} (allocate is the data segments identifier) and sends f's outuput to the code segment {\bf g}. The CbC compiler generates the data segment definition automatically, so writing it is unnecessary. There is no return from code segment {\bf g}. {\bf G} should call another continuation using {\bf goto}. Code segments have input data segments and output data segments. Data segments have two kind of dependency with code segments.
138 First, Code segments access the contents of data segments using field names. So data segments should have the named fields.
139 The second dependency is a data dependency, that is all input data segments should be ready before their execution.
139 140
140 \begin{figure}[htp] 141 \begin{figure}[htp]
141 \begin{center} 142 \begin{center}
142 \scalebox{0.5}{\includegraphics{fig/csds.pdf}} 143 \scalebox{0.5}{\includegraphics{fig/csds.pdf}}
143 \end{center} 144 \end{center}
153 goto hello("Hello World\n", __return, __environment); 154 goto hello("Hello World\n", __return, __environment);
154 } 155 }
155 156
156 __code hello(char *s, __code(*ret)(int, void*), void *env) { 157 __code hello(char *s, __code(*ret)(int, void*), void *env) {
157 printf(s); 158 printf(s);
158 goto (*ret)(0); 159 goto (*ret)(123);
159 } 160 }
160 \end{lstlisting} 161 \end{lstlisting}
161 \caption{Call C Functions in a Code Segment} 162 \caption{Call C Functions in a Code Segment}
162 \label{src:example} 163 \label{src:example}
163 \end{table} 164 \end{table}
164 165
165 In this hello world example, the environment of {\bf main}() and its continuation is kept in the variable {\bf \_\_environment}. The environment and the continuation can be accessed using {\bf \_\_environment} and {\bf \_\_return}.The arbitrary mixing of code segments and functions is allowed. The continuation of a {\bf goto} statement never returns to the original function, but goes to the caller or the original function. In that case, it returns the result 0 to the operating system. This continuation is called {\bf goto with environment}. 166 In this hello world example, the environment of {\bf main}() and its continuation is kept in the variable {\bf \_\_environment}. The environment and the continuation can be accessed using {\bf \_\_environment} and {\bf \_\_return}.The arbitrary mixing of code segments and functions is allowed. The continuation of a {\bf goto} statement never returns to the original function, but goes to the caller or the original function. In that case, it returns the result 123 to the operating system. This continuation is called {\bf goto with environment}.
166 167
167 \section{LLVM and Clang} 168 \section{LLVM and Clang}
168 The LLVM Project is a collection of modular and reusable compilers and toolchain technologies, and the LLVM Core libraries provide a modern source and target independent optimizer, along with code generation support for many popular CPUs. Clang is an LLVM native C/C++/Objective-C compiler. Figure \ref{fig:structure} shows Clang and LLVM's compilation flow. 169 The LLVM Project is a collection of modular and reusable compilers and toolchain technologies, and the LLVM Core libraries provide a modern source and target independent optimizer, along with code generation support for many popular CPUs. Clang is an LLVM native C/C++/Objective-C compiler. Figure \ref{fig:structure} shows Clang and LLVM's compilation flow.
169 170
170 \begin{figure}[htp] 171 \begin{figure}[htp]
191 Forcing a tail call requires many conditions be met. For example, there should not be a statement after a tail call, the caller and callee's calling conventions must be the same and their types should be cc10, cc11 or fastcc and the callee's return value type has to be the same as the caller's. 192 Forcing a tail call requires many conditions be met. For example, there should not be a statement after a tail call, the caller and callee's calling conventions must be the same and their types should be cc10, cc11 or fastcc and the callee's return value type has to be the same as the caller's.
192 193
193 All code segments have the void return type and writing statements after continuation is not allowed. As a result, type problems and after statement problems are solved. 194 All code segments have the void return type and writing statements after continuation is not allowed. As a result, type problems and after statement problems are solved.
194 195
195 Tail call elimination passes are enabled in {\bf BackendUtil.cpp}. In Clang, when the optimization level is two or more, tail call elimination passing is enable. Here it has been modified to be enabled anytime, however if the optimization level is one or less, tail call elimination passes only work for code segments. 196 Tail call elimination passes are enabled in {\bf BackendUtil.cpp}. In Clang, when the optimization level is two or more, tail call elimination passing is enable. Here it has been modified to be enabled anytime, however if the optimization level is one or less, tail call elimination passes only work for code segments.
196 A calling convention problem was also solved. fastcc was selected for a code segment's calling convention. In Clang, calling conventions are managed by the CGFunctionInfo class and its information is set in {\bf CGCall.ccp}, which is where cod segments calling conventions were set to fastcc. 197 A calling convention problem was also solved. fastcc was selected for a code segment's calling convention. In Clang, calling conventions are managed by the CGFunctionInfo class and its information is set in {\bf CGCall.ccp} ( a part of CodeGen ), which is where code segments calling conventions were set to fastcc.
197 198
198 Goto with environment is implemented by code rearranging. If the {\bf \_\_environment} or {\bf \_\_return} is declared, the CbC compiler rearranges the code for goto with environment. Setjmp and longjmp are used to do this. setjmp to save the environment before continuation and longjmp to restore it. 199 Goto with environment is implemented by code rearranging. If the {\bf \_\_environment} or {\bf \_\_return} is declared, the CbC compiler rearranges the code for goto with environment. Setjmp and longjmp are used to do this. setjmp to save the environment before continuation and longjmp to restore it.
199 200
200 \section{Result} 201 \section{Result}
201 Table \ref{src:example} shows the benchmark program. 202 Table \ref{src:example} shows the benchmark program.
221 \label{src:example} 222 \label{src:example}
222 \end{table} 223 \end{table}
223 224
224 It is written in C and CbC and there are several optimizations possible. 225 It is written in C and CbC and there are several optimizations possible.
225 When the argument is 1, CbC continuation is used. When the argument is 2 or 3, optimization is enabled. 226 When the argument is 1, CbC continuation is used. When the argument is 2 or 3, optimization is enabled.
227 In this benchmark, inline optimization was omitted.
226 The benchmark results are shown in TABLE \ref{result}. 228 The benchmark results are shown in TABLE \ref{result}.
227 229
228 \begin{table}[htpb] 230 \begin{table}[htpb]
229 \centering 231 \centering
230 \begin{tabular}{|l|r|r|r|} \hline 232 \begin{tabular}{|l|r|r|r|} \hline
236 \end{tabular} 238 \end{tabular}
237 \caption{Execution time(s)} 239 \caption{Execution time(s)}
238 \label{result} 240 \label{result}
239 \end{table} 241 \end{table}
240 242
241 LLVM and Clang compilers are faster than Micro-C when optimization is enabled. This means LLVM's optimization is powerful and useful. The LLVM and Clang complier is slower than GCC, but GCC cannot compile safely without optimization. This means LLVM can compile more reliably than GCC. 243 LLVM and Clang compilers are faster than Micro-C when optimization is enabled. This means CbC get benefits from LLVM optimizations. The LLVM and Clang complier is slower than GCC, but GCC cannot compile safely without optimization. This means LLVM can compile more reliably than GCC.
242 244
243 \section{Conclusion} 245 \section{Conclusion}
244 This Continuation based language has been designed and implemented for practical use. CbC has been partially implemented using LLVM and Clang 3.7. 246 This Continuation based language has been designed and implemented for practical use. CbC has been partially implemented using LLVM and Clang 3.7.
245 CbC can use LLVM's optimization. LLVM IR was not modified to implement CbC's compiler. 247 CbC can use LLVM's optimization. LLVM IR was not modified to implement CbC's compiler.
246 248