Mercurial > hg > Papers > 2015 > kaito-lola

annotate cfopm.tex @ 2:771136eae970

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
proofread
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Mon, 22 Jun 2015 19:44:08 +0900
parents 97e85476344e
children c50a033e6635
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \documentclass[conference]{IEEEtran}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 \usepackage[cmex10]{amsmath}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 \usepackage{url}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 \usepackage{listings}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 \usepackage[dvipdfmx]{graphicx}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 \lstset{
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 frame=single,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 keepspaces=true,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 stringstyle={\ttfamily},
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 commentstyle={\ttfamily},
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 identifierstyle={\ttfamily},
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 keywordstyle={\ttfamily},
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 basicstyle={\ttfamily},
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 breaklines=true,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 xleftmargin=0zw,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 xrightmargin=0zw,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 framerule=.2pt,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 columns=[l]{fullflexible},
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 numbers=left,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 stepnumber=1,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 numberstyle={\scriptsize},
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 numbersep=1em,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 language=c,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 tabsize=4,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 lineskip=-0.5zw,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 escapechar={@},
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 \ifCLASSINFOpdf
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 % \usepackage[pdftex]{graphicx}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 % declare the path(s) where your graphic files are
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 % \graphicspath{{../pdf/}{../jpeg/}}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 % and their extensions so you won't have to specify these with
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 % every instance of \includegraphics
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 \else
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 % will default to the driver specified in the system graphics.cfg if no
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 % driver is specified.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 % \usepackage[dvips]{graphicx}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 % declare the path(s) where your graphic files are
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 % \graphicspath{{../eps/}}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 % and their extensions so you won't have to specify these with
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 % every instance of \includegraphics
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 % \DeclareGraphicsExtensions{.eps}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 \fi
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 % correct bad hyphenation here
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 \hyphenation{op-tical net-works semi-conduc-tor}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 \begin{document}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 %
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 % paper title
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 % Titles are generally capitalized except for words such as a, an, and, as,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 % at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 % not capitalized unless they are the first or last word of the title.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 % Linebreaks \\ can be used within to get better formatting as desired.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 % Do not put math or special symbols in the title.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 \title{Implementing Continuation based language in LLVM and Clang}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 % author names and affiliations
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 % use a multiple column layout for up to three different
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 % affiliations
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 \author{
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 \IEEEauthorblockN{Kaito TOKUMORI}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 \IEEEauthorblockA{University of the Ryukyus \\ Email: kaito@cr.ie.u-ryukyu.ac.jp}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 \and
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 \IEEEauthorblockN{Shinji KONO}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 \IEEEauthorblockA{University of the Ryukyus \\ Email: kono@ie.u-ryukyu.ac.jp}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 % make the title area
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 \maketitle
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 % As a general rule, do not put math, special symbols or citations
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 % in the abstract
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 \begin{abstract}
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 \end{abstract}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 % no keywords
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 % For peer review papers, you can put extra information on the cover
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 % page as needed:
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 % \ifCLASSOPTIONpeerreview
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 % \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 % \fi
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 %
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 % For peerreview papers, this IEEEtran command inserts a page break and
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 % creates the second title. It will be ignored for other modes.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 \IEEEpeerreviewmaketitle
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 \section{A Practical Continuation based Language}
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
103 The proposed units of programming are named code segments and data segments.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
104 Code segments are units of calculation which have no state.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
105 Data segments are sets of typed data.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
106 Code segments are connected to data segments by a meta data segment called a context.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
107 After the execution of a code segment and its context, the next code segment (continuation) is executed.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
111 Code segments and data segments are low level enough to represent computational details,
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
112 and are architecture independent. They can be used as architecture independent assemblers.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 CbC has standalone compiler and GCC version. Here we report new partial implementation of CbC compiler based on LLVM and Clang 3.7.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 \section{Continuation based C}
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
117 CbC's basic programming unit is the code segment. These are not subroutines, but they look like functions because they take input and produce output. Both input and output should be data segments. Table \ref{src:example} details the definition of the data segment.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 \begin{table}[html]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 \begin{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 __code f(Allocate allocate){
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 allocate.size = 0;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 goto g(allocate);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
125
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 // data segment definition
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 // (generated automatically)
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 union Data {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 struct Allocate {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 long size;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 } allocate;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 };
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 \end{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 \caption{CbC Example}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 \label{src:example}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
136 \end{table}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
137
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
139
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 \begin{figure}[htp]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 \begin{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 \scalebox{0.5}{\includegraphics{fig/csds.pdf}}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 \end{center}
1
97e85476344e fix typos
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
144 \caption{Code Segments and Data Segments on CbC}
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 \label{fig:csds}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 \end{figure}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
147
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
148 Shifting completely, from C to CbC is unnecessary as in CbC we can go to code segments from C functions and call C functions in code segments The latter is straightforward but the former needs further extensions.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 \begin{table}[html]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 \begin{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 int main() {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 goto hello("Hello World\n", __return, __environment);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
155
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
156 __code hello(char *s, __code(*ret)(int, void*), void *env) {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 printf(s);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 goto (*ret)(0);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 \end{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 \caption{Call C Functions in a Code Segment}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 \label{src:example}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 \end{table}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
164
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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}.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
166
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 \section{LLVM and Clang}
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
169
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 \begin{figure}[htp]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 \begin{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 \scalebox{0.25}{\includegraphics{fig/clang_llvm_structure.pdf}}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 \end{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
174 \caption{LLVM and Clang structure}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
175 \label{fig:structure}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 \end{figure}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
177
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
178 LLVM has an intermediate representation which is called LLVM IR\cite{LLVMIR}. This part remains unmodified so that the optimization part does not need to be modified.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
179
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
180 \section{Implementation in LLVM and Clang}
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
181 The CbC compiler is implemented in LLVM and Clang using the following ideas.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
183 \begin{itemize}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 \item Code segments are implemented by C functions.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
185 \item Transition is implemented by forced tail call.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 \item Goto with environment is implemented by setjmp and longjmp.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 \end{itemize}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
188
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
189 {\bf \_\_code} is implemented as a new type keyword in LLVM and Clang. {\bf \_\_code} is similar to an attribute of a function, which means that the function can only be called in tail call elimination. Because of this implementation, code segments can actually be called as C function calls.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
190
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
192
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
194
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
197
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
199
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
200 \section{Result}
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
201 Table \ref{src:example} shows the benchmark program.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
202
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 \begin{table}[html]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 \begin{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 int f0(int i) {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 int k,j;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
207 k = 3+i;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 j = g0(i+3);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 return k+4+j;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
211
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 int g0(int i) {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
213 return h0(i+4)+i;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
214 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
215
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 int h0(int i) {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 return i+4;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
218 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
219 \end{lstlisting}
1
97e85476344e fix typos
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
220 \caption{benchmark program conv1}
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 \label{src:example}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 \end{table}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
223
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
224 It is written in C and CbC and there are several optimizations possible.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
225 When the argument is 1, CbC continuation is used. When the argument is 2 or 3, optimization is enabled.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
226 The benchmark results are shown in TABLE \ref{result}.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
227
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 \begin{table}[htpb]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
229 \centering
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
230 \begin{tabular}{|l|r|r|r|} \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
231 & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 Micro-C & 6.875 & 2.4562 & 3.105 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
233 GCC -O2 & 2.9438 & 0.955 & 1.265 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
234 LLVM/clang -O0 & 5.835 & 4.1887 & 5.0625 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
235 LLVM/clang -O2 & 3.3875 & 2.29 & 2.5087 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 \end{tabular}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
237 \caption{Execution time(s)}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
238 \label{result}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
239 \end{table}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
240
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
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.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
242
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
243 \section{Conclusion}
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
244 This Continuation based language has been designed and implemented for practical use. CbC has been partially implemented using LLVM and Clang 3.7.
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
245 CbC can use LLVM's optimization. LLVM IR was not modified to implement CbC's compiler.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
246
2
771136eae970 proofread
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
247 In the future, data segments, meta code segments and meta data segments for meta computation will be designed and implemented.
0
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
248 \nocite{opac-b1092711, LLVMIR, LLVM, clang}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
249 \bibliographystyle{IEEEtran}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
250 \bibliography{IEEEabrv,reference}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
251
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
252
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
253
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
254 % that's all folks
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
255 \end{document}