Mercurial > hg > Papers > 2011 > nobu-thesis

annotate nobu-graduation.tex @ 1:fc26e9b8551f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify tex
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Fri, 18 Nov 2011 07:45:29 +0900
parents 857b03a6ff06
children a729fd12d13f
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 \usepackage[dvips]{graphicx}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 \usepackage{url}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 \usepackage{picins}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 \usepackage{fancyhdr}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 \pagestyle{fancy}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 \lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.eps}}琉球大学主催 工学部情報工学科 卒業研究発表会}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 \rhead{}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 \cfoot{}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 \setlength{\headheight}{0mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 \setlength{\headsep}{5mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 \setlength{\textwidth}{181mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 \setlength{\textheight}{261mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 \setlength{\footskip}{0mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 \pagestyle{empty}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 \begin{document}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 \title{Continuation based C コンパイラのGCC-4.6による実装}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 \author{学籍番号:085711E 氏名:大城信康 {}{} 指導教員 : 河野真治}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 \date{H23 11/18 fri}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 \maketitle
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 \thispagestyle{fancy}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 \section{研究背景と目的}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 当研究室ではプログラムをコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 また CbC の開発と共に CbC のコンパイラの開発も行なってきた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 2008年には GCC-4.2 をベースとした CbC のコンパイラ (以下 CbC-GCC) が開発され、GCC の最適化やデバッグ、他アーキテクチャへの対応と言った恩恵を受けられるようになった。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 以降、GCC のアップデートに合わせて CbC-GCC のアップデートも行ってきた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行う。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 %\subsection{研究内容}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 %今回 GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へとアップデートを行った。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 %現在の GCC ベースの CbC (以下CbC-GCC) コンパイラには幾つかのバグが見られる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 %特に Code Segmtne への処理移動が jmp でなく call で行われる部分あげられる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 %現在 CbC を実装した GCC コンパイラのバージョンは、初めに実装が行われた GCC-4.2 よりバージョンを上げた GCC-4.5 となる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 %本研究では、CbC-GCC を GCC-4.6 へのバージョンアップすると共に実装を突き詰めることを目的とする。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 %また、GCC に変わるコンパイラとして注目されてきている LLVM への CbC の実装の考察も行う。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 \section{Continuation basede C (CbC)}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 Continuation based C (以下CbC) は当研究室で開発しているプログラミング言語である。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 CbC のプログラムはコードセグメント毎に記述され、コード間を軽量継続により処理を移るという特徴を持つ。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 構文は C と同じであるが、ループ制御や関数コールが取り除かれる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 \subsection{コードセグメント}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 CbC においてのプログラムの基本単位としてコードセグメントという概念がある。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 記述の仕方は C の構文と同じで、型に“\_\_code” を使うことで宣言できる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 コードセグメントへの移動は“goto” の後にコードセグメント名と引数を並べて記述することで行える。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 図\ref{fig:cs}はコードセグメント間の処理の流れを表している。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 \begin{figure}[htpb]
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 \begin{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 \scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 \end{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 \caption{コードセグメント間の継続(goto)}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 \label{fig:cs}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 \end{figure}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 %また、コードセグメント間の移動は軽量継続によって行われる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 %プログラムの末尾に次のコードセグメントを記述し処理を続けていく。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 %コードセグメントの記述の仕方は C の関数の記述と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 %コードセグメントへの処理の移りは call ではなく jmp で行われ、その為 C の関数の様に呼び出し元への復帰がない。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 %構文では“\_\_code”で関数を宣言することでコードセグメントとして扱うようにしている。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 \subsection{軽量継続(light-weight continuation)}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 コードセグメントは C の関数と違って返り値を持たず、処理が終われば次のコードセグメントへと処理を移る。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 このコードセグメント間の継続制御を軽量継続(light-weight continuation) と呼ぶ。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 C おいて関数呼び出しを繰り返し行う場合、呼び出された関数の引数の数だけスタックに値が積まれていく。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 だが、返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く、最小限のスタックの使用ですむ。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 軽量継続によりループ制御、関数コールとスタックの操作を意識し最適化がソースコードレベルで行えるようになる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 %だが、返り値を持たないコードセグメントではスタックに積まれる値は1つのコードセグメントの引数の分だけですむ。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 \section{GCC-4.6 への実装}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 \subsection{軽量継続の実装}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 CbC はコードセグメント間の処理の移りを軽量継続で行う。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 その実態は、アセンブラでの関数の呼び出しを call ではなく jmp で行うようにするというものである。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
84
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 \subsubsection{Tail Call Elimination}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 GCC には最適化の1つに Tail Call Elimination (末尾除去) がある。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 Tail Call Elimination は関数の呼び出しを call ではなく jmp で行い、
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 返り値を大元の関数に返すというものである。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 %「caller側とcallee側の返り値の型が同じ」といった、幾つかのの条件下において行われる最適化になる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 図\ref{fig:continue}は Tail Call Elimination によるプログラムの処理の流れを表す。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 \begin{figure}[htpb]
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 \begin{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93 \scalebox{0.30}{\includegraphics{figure/continuation.eps}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 \end{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 \caption{Tail Call Elimination の例}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 \label{fig:continue}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 \end{figure}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
98
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 CbC における軽量継続の実装はこの Tail Call Elimination を用いて行われている。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 コードセグメントは全てこの Tail Call Elimination にかからなければならない。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 だが、CbC-GCC-4.5 において Tail Call Elimination にかからないコードセグメントがあることを確認できた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 この点は GCC-4.6 へのアップデートに合わせ改善する。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
103
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 %\subsubsection{try_tail_call フラグ}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 %Tail Call Elimination が可能である場合、try_tail_call フラグが立てられる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 %コードセグメントへの jmp は Tail Call Elimination を受けることで実装される。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 %軽量継続において重要なのは上記でも述べた Tail Call Elimination に必要な幾つかの条件をクリアすることであった。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 %最初に開発された CbC-GCC ではコードセグメントの場合は上記の『ある特定の条件』をクリアするよう実装されていた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 %しかし、CbC のコードをアセンブラに出力してみると幾つか call で呼び出されていることが分かった。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 %この問題を解決し、全てのコードセグメントは jmp によって呼びされるようにする必要がある。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 \subsection{typedefrec の実装}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 C では関数や構造体の宣言の時に自分自身を引数にすることができない。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 そこで“typedefrec” という構文を作り、図\ref{fig:typedefrec}のような宣言を行えるようにしたい。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
116
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 \begin{figure}[htpb]
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 \begin{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 \scalebox{0.40}{\includegraphics{figure/typedefrec.eps}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 \end{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 \caption{typedefrecの例}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 \label{fig:typedefrec}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 \end{figure}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
124
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 より柔軟なプログラミングが行えるように typdefrec を実装したい。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
126
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 %\subsubsection{typedefrec の実装方法}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 %typedefrec
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
129
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 %GCC における C の構文解析では、関数名はハッシュテーブルによって管理される。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
131 %ここで問題となるのが、関数の宣言を全て読んだ後にハッシュテーブルに追加されるということである。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 %その為、関数の引数に自身の関数名がでるとそのような関数はないとエラーにされてしまう。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 %そこで typedefrec の付いた関数は先行して宣言を行うことにする。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 %すると、宣言中でもハッシュテーブルから関数の情報をとることができるようになる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
135
1
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
136 %\subsection{\_\_return 変数}
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
137 \subsection{環境付き継続}
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 CbC では通常の C の関数からコードセグメントに継続する際、
1
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
139 元の C の関数に処理を戻すことがように環境付き継続を実装してある。
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
140 環境付き継続は \_\_return 変数を参照することで用いることができる。
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
141 \_\_return 変数は参照されると、参照した関数のアドレスを覚えておく。
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
142 コードセグメントの継続の際に引数に \_\_return 変数を渡すことで、
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
143 関数の呼び出し元のアドレスも渡すことができる。
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
144 後は引数として渡されたきたアドレスへ飛ぶことでいつでも C の関数に戻ることができる。
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
145
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 \subsubsection{\_\_return 変数の問題}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 しかし現在この \_\_return の値は static で実装されている。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 これではスレッドセーフであるとは言えない。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 マルチスレッドで\_\_returnを扱うと、元の関数に戻る前に \_\_return の値が書き換えられる可能性があるからである。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 そこで、\_\_return をスレッドセーフにする必要がある。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
151
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 \subsection{x86\_64 での fastcall}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 GCC では関数の呼び出しの際に引数はスタックに積まれて渡されるが、
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 レジスタを使って渡すようにする fastcall という拡張機能がある。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 CbC-GCC ではコードセグメントとして宣言された場合 fastcall が自動で付くようにしていた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
156 しかし、x86\_64 においてこの fastcall は標準の機能となっており、コンパイルの際に warning が吐かれた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
157 そこで、x86\_64 の場合は fastcall を付与させないようにした。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
158
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
159 \section{CbC の今後}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
160 現在 CbC は C をベースとして設計されている。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 しかし、C ではプロトタイプ宣言や継続の際に型推論が扱えないなど不便な点があることがわかっている。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 そこで、Go や D 言語と言った言語へ実装を行いたいという要求がでてきた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
163
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
164 また、LLVM ベースの CbC コンパイラについても検討している。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
165
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
166 \section{現状と今後の課題}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 %アセンブラ出力を見ることができ、gdb を使ってのデバッグが可能になったことである。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 %CbC-GCC により CbC のプログラム開発が行いやすくなった。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
169 %CbC-GCC は GCC に合わせてアップデートされてきた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 %しかし、アップデートに伴い幾つか実装を見直す必要がでてきた。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 %同時に、現時点で見つかっている問題以外にもバグが無いかを調べていく。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 今後は本稿でも述べたとおり CbC コンパイラの実装を行なっていく。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 また、実装後は、32ビット,64ビットそれぞれでコンパイルしたプログラムの比較、
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
174 それと Micro-C との性能比較も行う予定である。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
175
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 Go 言語や D 言語への CbC の移植,
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 LLVM ベースの CbC コンパイラについては実装の方法から考えていくことになる。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
178
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
179
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
180
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
181 %今後は本稿で述べた CbC-GCC の問題点を改善していく必要がある。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 %また、CbC を GCC だけでなく LLVM での実装や、C 言語以外の言語への変更も検討していく。
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
183
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
184 \thispagestyle{fancy}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
185 \begin{thebibliography}{9}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
186
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
187 \bibitem{1}{河野真治}:
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
189
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
190 \bibitem{2}{河野真治}:
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
191 “継続を持つ C の回言語によるシステム記述”. 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
192
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 \bibitem{3}{与儀健人,河野真治}:
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
195
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
196 \bibitem{4}{与儀健人,河野真治}:
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
197 “組み込み向け言語Continuation based C のGCC上の実装”. 琉球大学大学院　理工学研究科 学位論文(修士), 2010
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
198
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
199 \bibitem{5}{下地篤樹,河野真治}:
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
200 “線形時相論理を用いたContinuation based C プログラムの検証”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2008
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
201
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 \bibitem{6}{楊挺,河野真治}:
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
203 “Continuation based C の実装”. 琉球大学大学院　理工学研究科 情報工学専攻 学位論文(修士), 2002
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
204
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
205 \bibitem{7}{GNU Compiler Collection (GCC) Internals}:
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 “http://gcc.gnu.org/onlinedocs/gccint/”
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
207
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
208
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
209 \end{thebibliography}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 \end{document}