Mercurial > hg > Papers > 2011 > nobu-thesis

annotate nobu-midthesis.tex @ 7:24b02780ca8f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify midthesis
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 19 Nov 2011 16:22:19 +0900
parents a0bf68477575
children 60c8ce5eb0e0
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}
3
ef5f7c93074a modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
6 \usepackage{listings}
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 \pagestyle{fancy}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 \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
9 \rhead{}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 \cfoot{}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 \setlength{\headheight}{0mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 \setlength{\headsep}{5mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 \setlength{\textwidth}{181mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 \setlength{\textheight}{261mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 \setlength{\footskip}{0mm}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 \pagestyle{empty}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 \begin{document}
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
23 \title{Continuation based C コンパイラのGCC-4.6における実装}
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 \author{学籍番号:085711E 氏名:大城信康 {}{} 指導教員 : 河野真治}
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
25 %\date{H23 11/18 fri}
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 \maketitle
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 \thispagestyle{fancy}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 \section{研究背景と目的}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
30 当研究室ではプログラムをコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
31 コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
32 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
34 GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
35 本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 %\subsection{研究内容}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
38 %今回 GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へとアップデートを行った.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
40 %現在の GCC ベースの CbC (以下CbC-GCC) コンパイラには幾つかのバグが見られる.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
41 %特に Code Segmtne への処理移動が jmp でなく call で行われる部分あげられる.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
42 %現在 CbC を実装した GCC コンパイラのバージョンは,初めに実装が行われた GCC-4.2 よりバージョンを上げた GCC-4.5 となる.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
43 %本研究では,CbC-GCC を GCC-4.6 へのバージョンアップすると共に実装を突き詰めることを目的とする.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
44 %また,GCC に変わるコンパイラとして注目されてきている LLVM への CbC の実装の考察も行う.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 \section{Continuation basede C (CbC)}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
46 CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
47 構文は C と同じであるが, ループ制御や関数コールが取り除かれる.
0
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{コードセグメント}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
50 コードセグメントの記述は C の関数の構文と同じで, 型に“\_\_code” を使うことで宣言できる.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
51 コードセグメントへの移動は“goto” の後にコードセグメント名と引数を並べて記述することで行える.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
52 図\ref{fig:cs}はコードセグメント間の処理の流れを表している.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 \begin{figure}[htpb]
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 \begin{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 \scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 \end{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 \caption{コードセグメント間の継続(goto)}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 \label{fig:cs}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 \end{figure}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
62 %また,コードセグメント間の移動は軽量継続によって行われる.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
63 %プログラムの末尾に次のコードセグメントを記述し処理を続けていく.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 %コードセグメントの記述の仕方は C の関数の記述と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
65 %コードセグメントへの処理の移りは call ではなく jmp で行われ,その為 C の関数の様に呼び出し元への復帰がない.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
66 %構文では“\_\_code”で関数を宣言することでコードセグメントとして扱うようにしている.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 \subsection{軽量継続(light-weight continuation)}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
69 コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
70 C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
71 だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
73 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
75
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
76 %だが,返り値を持たないコードセグメントではスタックに積まれる値は1つのコードセグメントの引数の分だけですむ.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 \section{GCC-4.6 への実装}
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
79 % \subsection{軽量継続の実装}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
80 GCCでの計量継続を Tail Call Ellimination (末尾除去)を強制することで実装する.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
81 これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
82 コードセグメント自体には戻値はない.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
84 %「caller側とcallee側の返り値の型が同じ」といった,幾つかのの条件下において行われる最適化になる.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
85 図\ref{fig:continue}は Tail Call Elimination によるプログラムの処理の流れを表す.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 \begin{figure}[htpb]
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 \begin{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 \scalebox{0.30}{\includegraphics{figure/continuation.eps}}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 \end{center}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 \caption{Tail Call Elimination の例}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 \label{fig:continue}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 \end{figure}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
93
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
94 \subsection{expand\_call 関数}
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
95 GCCでは, ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で以下の条件で判断される.
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
96
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
97 \begin{itemize}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
98 \item caller 側と callee 側の戻値の型が一致している.
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
99 \item 関数呼び出しがリターンの直前に行われている.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
100 \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
101 \item 引数の並びのコピーに上書きがない.
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
102 \end{itemize}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
103
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
104 CbC の実装では上記の条件を, 以下の様にして解決させている.
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
105
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
106 \begin{itemize}
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
107 \item コードセグメントは void 型で統一する
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
108 \item Cの関数からコードセグメントにgotoする場合は返す値の型チェックを行わない.
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
109 \item goto の直後に retrun を置く．
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
110 \item スタックサイズは関数宣言時に決まったサイズにする．
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
111 \item 引数は一旦, 一時変数にコピーして重なりがないようにする．
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
112 \end{itemize}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
113
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
114 GCCでは, この他にもTCEを禁止しするルールがあり, GCC-4.5, 4.6 でも
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
115 Tail Call Elimination にかからないコードセグメントがある.
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
116 この点を改善する必要がある.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
118
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 %\subsubsection{try_tail_call フラグ}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
120 %Tail Call Elimination が可能である場合,try_tail_call フラグが立てられる.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
121 %コードセグメントへの jmp は Tail Call Elimination を受けることで実装される.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
122 %軽量継続において重要なのは上記でも述べた Tail Call Elimination に必要な幾つかの条件をクリアすることであった.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
123 %最初に開発された CbC-GCC ではコードセグメントの場合は上記の『ある特定の条件』をクリアするよう実装されていた.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
124 %しかし,CbC のコードをアセンブラに出力してみると幾つか call で呼び出されていることが分かった.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
125 %この問題を解決し,全てのコードセグメントは jmp によって呼びされるようにする必要がある.
0
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
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
128 %\begin{figure}[htpb]
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
129 % \begin{center}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
130 %\scalebox{0.35}{\includegraphics{figure/cs_stack.eps}}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
131 % \end{center}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
132 % \caption{継続による引数のスタック格納の様子}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
133 % \label{fig:cs_stack}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
134 %\end{figure}
3
ef5f7c93074a modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
135
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
136
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 %\subsubsection{typedefrec の実装方法}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 %typedefrec
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
139
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
140 %GCC における C の構文解析では,関数名はハッシュテーブルによって管理される.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
141 %ここで問題となるのが,関数の宣言を全て読んだ後にハッシュテーブルに追加されるということである.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
142 %その為,関数の引数に自身の関数名がでるとそのような関数はないとエラーにされてしまう.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
143 %そこで typedefrec の付いた関数は先行して宣言を行うことにする.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
144 %すると,宣言中でもハッシュテーブルから関数の情報をとることができるようになる.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
145
1
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
146 %\subsection{\_\_return 変数}
fc26e9b8551f modify tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
147 \subsection{環境付き継続}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
148 CbC には通常の C の関数からコードセグメントに継続する際,
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
149 その関数から値を戻す処理への継続を得ることができる.
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
150 これを環境付き継続という.
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
151 これらは, 以下の二種類の CbC で定義した特殊変数である.
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
152 \_\_environment は, 環境を表す情報である.
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
153 \_\_return は, これを環境付き継続の行き先であり, 関数の戻値と \_\_environment の二つの引数を持つ
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
154 コードセグメントである. 例えば, 以下のように使うと, \verb+main()+ は 1 を返す.
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
155
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
156 \begin{verbatim}
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
157 __code c1(__code ret(int,void *),void *env) {
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
158 goto ret(1,env);
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
159 }
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
160
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
161 int main() {
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
162 goto c1(__return, __environment);
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
163 }
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
164 \end{verbatim}
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
165
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
166 GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す.
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
167 戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(Listing\ref{code:_ret_val}).
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
168
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
169 \begin{figure}[h]
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
170 \begin{minipage}[b]{.45\textwidth}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
171 \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
172 __label__ _cbc_exit0;
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
173 static int retval; // should be thread local
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
174 void _cbc_internal_return(int retval_, void *_envp){
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
175 retval = retval_;
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
176 goto _cbc_exit0;
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
177 }
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
178 if (0) {
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
179 _cbc_exit0:
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
180 return retval;
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
181 }
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
182 _cbc_internal_return;
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
183 \end{lstlisting}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
184 \end{minipage}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
185 \hfill
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
186 \end{figure}
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
187
5
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
188 \subsubsection{環境付き継続の問題}
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
189 現在環境付き継続は
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
190 このコードを GCC 内部で生成することで実現している. これは正しく動作しているが,
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
191 \verb+retval+に static を指定してしまうと,
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
192 スレッドセーフな実装でなくなる.
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
193 これを通常の変数にすると, 関数内の関数は closure として実装される. しかし, GCC 4.6 と Lion の
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
194 組合せでは closure は正しく動作してないことがわかった.
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
195 Thread local 変数を用いると, やはり closure が出力されてしまう.
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
196 本来は, 戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず,
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
197 浮動小数点や構造体自体である可能性があり複雑である.
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
198 一つの解決策はレジスタ渡しと考えているが, 他の方法もありえる. 少し重いが setjmp を用いた実装方法もある.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
199
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
200
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 \section{現状と今後の課題}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
202 %アセンブラ出力を見ることができ,gdb を使ってのデバッグが可能になったことである.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
203 %CbC-GCC により CbC のプログラム開発が行いやすくなった.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
204 %CbC-GCC は GCC に合わせてアップデートされてきた.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
205 %しかし,アップデートに伴い幾つか実装を見直す必要がでてきた.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
206 %同時に,現時点で見つかっている問題以外にもバグが無いかを調べていく.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
207 今後は本稿でも述べたとおり CbC コンパイラの実装を行なっていく.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
208 また, 実装後は, 32ビット, 64ビットそれぞれでコンパイルしたプログラムの比較,
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
209 それと Micro-C による実装との性能比較も行う予定である.
6
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
210
a0bf68477575 fix by kono
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
211 時間があれば, LLVM での実装, コードセグメントの宣言に便利な \verb+typedefrec+ の実装,
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
212 あるいは, Google go 言語での実装などの研究も行う予定である.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
213
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
214
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
215 %今後は本稿で述べた CbC-GCC の問題点を改善していく必要がある.
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
216 %また,CbC を GCC だけでなく LLVM での実装や,C 言語以外の言語への変更も検討していく.
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
217
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
218 \thispagestyle{fancy}
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
219 \begin{thebibliography}{3}
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
220
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
221 \bibitem{1}{河野真治}:
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
222 “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
223
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
224 \bibitem{2}{与儀健人,河野真治}:
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
225 “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
226
7
24b02780ca8f modify midthesis
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
227 \bibitem{3}{GNU Compiler Collection (GCC) Internals}:
0
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
228 “http://gcc.gnu.org/onlinedocs/gccint/”
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
229
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
230
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
231 \end{thebibliography}
857b03a6ff06 add nobu-graduation
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 \end{document}