Mercurial > hg > Papers > 2015 > kaito-lola

annotate cfopm.tex @ 0:c0d36568602d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
1st commit
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Sun, 10 May 2015 22:54:12 +0900
parents
children 97e85476344e
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}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 A programming paradigm which use data segments and
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 code segments is proposed. CbC is a lower language of C for this paradigm.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 CbC has standalone compiler and GCC version.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 In this study, we add an implement CbC compiler on LLVM/clang-3.7.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 The detail of implementation and evaluation are shown.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 \end{abstract}
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 % no keywords
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
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 % 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
96 % page as needed:
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 % \ifCLASSOPTIONpeerreview
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 % \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 % \fi
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 %
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 % 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
102 % 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
103 \IEEEpeerreviewmaketitle
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 \section{A Practical Continuation based Language}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 We proposed units of program named code segment and data segment.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 Code segment is a unit of calculation which has no state.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 Data segment is a set of typed data.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 Code segments are connected to data segments with a context, which is a meta data segment.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 After an execution of a code segment and its context, next code segments (Continuation) is executed.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 We had developed a programming language ``Continuation based C (CbC)'' \cite{DBLP:journals/corr/abs-1109-4048}.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 Hear after we call it CbC, which supports code segments.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 CbC is compatible with C language and it has continuation as a goto statement.
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 Code segments and data segments are low level enough to represent computation details,
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 and it is architecture independent.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 It can be used as an architecture independent assembler.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 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
121
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 First we show CbC language overview.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 \section{Continuation based C}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 CbC's basic programing unit is a code segment. It is not a subroutine, but it looks like a function, because it has input and output. These interfaces should be data segments and we are currently designing data segments part.
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 \begin{table}[html]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 \begin{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 __code f(Allocate allocate){
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 allocate.size = 0;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 goto g(allocate);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 }
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 // data segment definition
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 // (generated automatically)
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 union Data {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
136 struct Allocate {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 long size;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 } allocate;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 };
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 \end{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 \caption{CbC Example}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 \label{src:example}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 \end{table}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
144
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 In this example, a code segment {\bf f} has input datasegment {\bf allocate} (Allocate is a data segment identifier) and sends output it to a code segmnet {\bf g}. CbC compiler generates data segment definition automatically so we do not have to write it. There is no return from code segment {\bf g}, {\bf g} should call another continuation using {\bf goto}. Code segments has one input data segment and several output data segment, and their dependency is proved by data segments.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 \begin{figure}[htp]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 \begin{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 \scalebox{0.5}{\includegraphics{fig/csds.pdf}}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 \end{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 \caption{Code Segmnets and Data Segments on CbC}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 \label{fig:csds}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 \end{figure}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 In CbC, we can go to a code segment from a C function and we can call C functions in a code segment. So we don't have to shift completely from C to CbC. The later one is straight forward, but the former one needs further extensions.
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 \begin{table}[html]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 \begin{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 int main() {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 goto hello("Hello World\n", __return, __environment);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
161
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 __code hello(char *s, __code(*ret)(int, void*), void *env) {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 printf(s);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 goto (*ret)(0);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
165 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 \end{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 \caption{Call C Functions in a Code Segment}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 \label{src:example}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
169 \end{table}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
170
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 In this hello world example, the environment of {\bf main}() and its continuation is kept in a variable {\bf \_\_environment}. The environment and the continuation can be get using {\bf \_\_environment} and {\bf \_\_return}.Arbitrary mixture of code segments and functions are allowed. The continuation of {\bf goto} statement never returns to original function, but it goes to caller of original function. In this case, it returns result 0 to the operating system. This cotinuation is called {\bf goto with environment}.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
172
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 \section{LLVM and Clang}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
174 The LLVM Project is a collection of modular and reusable compiler 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} is Clang and LLVM's compile flow.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
175
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 \begin{figure}[htp]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 \begin{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
178 \scalebox{0.25}{\includegraphics{fig/clang_llvm_structure.pdf}}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 \end{center}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
180 \caption{LLVM and Clang structure}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
181 \label{fig:structure}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 \end{figure}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
183
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 LLVM has a intermediate representation which called LLVM IR\cite{LLVMIR}. Importantly, we do not modify it so we do not have to modifiy optimize part.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
185
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 \section{Implementation in LLVM and Clang}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 So how to implement CbC compiler in LLVM and Clang. Here we show our idea.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
188
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 \begin{itemize}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
190 \item Code segments are implemented by C functions.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 \item Transition is implemented by forced tail call.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
192 \item Goto with environment is implemented by setjmp and longjmp.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 \end{itemize}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
194
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 {\bf \_\_code} is implemented as a new type keyword in LLVM and Clang. You may think {\bf \_\_code} is an attribute of a function, which means that the function can call in tail call elimination only.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
196 Because of this implementation, we can actually call code segmnet as a C function call.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
197
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 Forcing tail call require many condisions. For example, there should be no statement after tail call, caller and callee's calling convention have to be the same and type is cc10, cc11 or fastcc, callee's return value type have to be the same as caller's it, add tail call elimination pass, and so on.
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 All code segment has the void return type and we do not allow to write statement after continuation, so type problem and after statement problem is solved.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
201
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 Tail call elimination pass is enabled in {\bf BackendUtil.cpp}. In the clang, when optimize level is two or more, tail call elimination pass is enabled. We modify it to enable anytime and if optimize level is one or less, tail call elimination pass work for only code segment.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
203
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
204 Next, we solve a calling convention problem. We select fastcc for code segment's calling convention. In the clang, calling convention is managed by CGFunctionInfo class and its infomations are set in {\bf CGCall.cpp}. We modify here to set fastcc to code segmnets.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
205
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 Goto with environment is implemented by code rearranging. If the {\bf \_\_environment} or {\bf \_\_return} is declared, CbC compiler rearrange code for goto with environment. We use setjmp and longjmp for it. Setjmp save environment before continuation, and longjmp restore it.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
207
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
208 \section{Result}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 Here is our bench mark program.
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 \begin{table}[html]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 \begin{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
213 int f0(int i) {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
214 int k,j;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
215 k = 3+i;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 j = g0(i+3);
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
217 return k+4+j;
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
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
220 int g0(int i) {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 return h0(i+4)+i;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
223
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
224 int h0(int i) {
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 return i+4;
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
226 }
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
227 \end{lstlisting}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 \caption{bench mark program conv1}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
229 \label{src:example}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
230 \end{table}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
231
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 It is written in C and CbC and there are several optimization is possible.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
233 When argument is 1, use CbC continuation. When argument is 2 or 3, optimization is enabled.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
234
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
235 Here we show bench mark result (TABLE \ref{result}).
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
236
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
237 \begin{table}[htpb]
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
238 \centering
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
239 \begin{tabular}{|l|r|r|r|} \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
240 & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 Micro-C & 6.875 & 2.4562 & 3.105 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
242 GCC -O2 & 2.9438 & 0.955 & 1.265 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
243 LLVM/clang -O0 & 5.835 & 4.1887 & 5.0625 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
244 LLVM/clang -O2 & 3.3875 & 2.29 & 2.5087 \\ \hline
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
245 \end{tabular}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
246 \caption{Execution time(s)}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
247 \label{result}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
248 \end{table}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
249
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
250 LLVM and clang compiler is faster than Micro-C when optimization is enabled. It mean LLVM's optimization is powerful and useful. LLVM and clang compiler is slower than GCC but GCC cannot compile safety without optimization. It means LLVM can compile more reliability than GCC.
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 \section{Conclusion}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
253 We have designed and implemented Continuation based language for practical use. We have partial implementation of CbC using LLVM and Clang 3.7. CbC can use LLVM's optimization. We did not modify LLVM IR to implement CbC compiler.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
254
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
255 In future, we design and implement data segmnet and meta code segment, meta data segment for meta computation.
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
256 \nocite{opac-b1092711, LLVMIR, LLVM, clang}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
257 \bibliographystyle{IEEEtran}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
258 \bibliography{IEEEabrv,reference}
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
259
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
260
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
261
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
262 % that's all folks
c0d36568602d 1st commit
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
263 \end{document}