\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfmx]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\input{dummy.tex}
\begin{document}
\title{LLVM/clang 上の CbC コンパイラの改良と Gears OS サポート}
\author{135756F 氏名 宮城光希 {}{} 指導教員 : 河野 真治}
\date{}
\maketitle
\thispagestyle{fancy} 

\section{メタ計算の重要性}

プログラムを記述する際に通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等、記述しなければならない処理が存在する。これらの計算を Meta Computation と呼ぶ。

Meta Computation を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。
そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Segment、Data Segment という単位を提案している。  

Code Segment は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
Code Segment、Data Segment にはそれぞれメタレベルの単位である Meta Code Segment、Meta Data Segment が存在し、これらを用いて Meta Computation を実現する。

また、Code Segment 単位を用いたプログラミング言語 Continuation based C (CbC)を開発している。
CbCは軽量継続による遷移を行うので、継続前の Code Segment に戻ることはなく、状態遷移ベースのプログラミングに適している。

Data Gear は CbC で記述された Gears OS によって管理される。Gears OS では一つのスレッドは Data Gears と Code Gears を管理する Context をただ一つ持つ。
Context は Meta Data Gears の一つである。

本研究では、LLVM/clang 上での CbC コンパイラの改良と Gears OS の構文のサポートを行う。

\section{Continuation based C (CbC)}

CbC では Code Segment は \_\_code という型を持つ関数の構文で定義される。

Code Segment は 戻り値を持たないので、return 文は存在しない。goto の後に Code Segment 名と引数を並べて、次の Code Gears の遷移を記述する。

この goto の行き先を継続と呼ぶ。Scheme の継続と異なり CbC には環境がないので、この継続は単なる行き先である。したがってこれを軽量継続と呼ぶこともある。図\ref{fig:codesegment} は Code Segment 間の処理の流れを表している。

\begin{figure}[htpb]
    \centering
    \includegraphics[width=70mm]{pic/codesegment.pdf}
    \caption{gotoによる Code Segment 間の接続}
    \label{fig:codesegment}
\end{figure}

\section{LLVM/clang による CbC の実装}
LLVM とは、モジュラー構成および再利用可能なコンパイラとツールチェーン技術等を開発するプロジェクトの名称である。
LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語に変換することができる。また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。

clang は LLVM をバックエンドとして利用する C/C++/Objective-C のコンパイラである。

LLVMでは、最適化や中間表現の変換を何段階か行う。多くの pass は最適化のために存在し、そのなかから任意のものを利用することができる。
pass には以下のようなものがある。
  
\subsubsection*{SelectionDAG Instruction Selection (SelectionDAGISel)}
    LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し、最適化を行う。その後 Machine Code を生成する。
\subsubsection*{SSA-based Machine Code Optimizations}
    SSA-based Machine Code に対する最適化を行う。各最適化はそれぞれ独立した pass になっている。
\subsubsection*{Register Allocation}
    仮想レジスタから物理レジスタへの割り当てを行う。ここで PHI 命令が削除され、SSA-based でなくなる。
\subsubsection*{Prolog/Epilog Code Insertion}
    Prolog/Epilog Code の挿入を行う。どちらも関数呼び出しに関わるものであり、Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理、Epilog は呼び出し元の関数に戻る際に行う処理である。
\subsubsection*{Late Machine Code Optimizations}
    Machine Code に対してさらに最適化を行う。
\subsubsection*{Code Emission}
    Machine Code を MC Layer での表現に変換する。その後さらにターゲットのアセンブリ言語へ変換し、その出力を行う。

\begin{figure}[ht]
    \centering
    \includegraphics[width=90mm]{pic/llvmProcess.pdf}
    \caption{LLVM の 処理過程}
    \label{fig:llvmProcess}
\end{figure}

\section{LLVM/clang のデバッグ}
LLVM/clang で CbC をコンパイルした際 Code Segment 内の局所変数でポインタを参照すると tail call されないという不具合があることがわかった。

局所変数でポインタを参照していると clang は生成する LLVM IR に オブジェクトの寿命を示す lifetime.start と lifetime.end を書き出す。

ここでオブジェクトの lifetime の終わりを示す lifetime.end が tail call の後に書き出されてしまうことにより、tail call の際に局所変数が解放されておらず lifetime が残っているので tail call が無視されてしまう。

しかしCbC では継続を行った後、継続前の Code Segment に戻ることはないので局所変数の解放は継続前に行っても良い。
そこで lifetime.end を tail call の直前で生成を行うことで tail call を出すようにした。

\section{Gears OS の構文サポート}
Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
Gears OS は Input/Output Data Gear の依存関係が解決された Task を並列実行する。

Gears OS では Meta Computation を Meta Code Gear、Meta Data Gear で表現する。Meta Code Gear は通常の Code Gear の直後に遷移され、Meta Computation を実行する。

CbC では処理を Code Segment を用いたプログラミング言語であるため、 Gears OS の Code Gear を記述するのに適している。
そこで Gears OS の構文のサポートが必要になる。現在は python を用いたプログラム変換で実現されている。

Gears OS では Context という接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Dara Gear である。Gears OS では必要な Code/Data Gear に参照したい場合、Context を通す必要がある。
Context の自動生成を行うようにする。

\section{今後の課題}
今後の課題は現状の Gears OS のコードをリファクタリングし通常計算とメタ計算の分離を明確にする。
必要なメタ計算部分の CbC による実装を統一する。
Context 、 Meta Code Gear 、 Meta Data Gear を生成するプログラム変換系を作成する。
これを用いて Gears OS の記述を行う。
これにより Gears OS のメタ計算を柔軟に行うことができるようになり、 Gears OS 自体の信頼性を向上し, Gears OS の拡張性を実現することができると考えられる。

\begin{thebibliography}{9}
    \bibitem{1}
        徳森 海斗 : LLVM Clang 上の Continuation based C コンパイラ の改良,
    \bibitem{2}
        伊波立樹, 東恩納琢偉, 河野真治 : Code Gear、 Data Gear に基づく OS のプロトタイプ, 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)(2016).
    \bibitem{3}    
        大城 信康, 河野真治 : Continuation based C の GCC 4.6 上の実装について, 第53回プログラミング・シンポジウム(2012)
    \bibitem{4}
        与儀健人, 河野真治 : Continuation based c コンパイラの gcc-4.2 による実装, 情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)(2008).
    \bibitem{5}
        The LLVM Compiler Infrastructure
    \bibitem{6}
        LLVM Language Reference Manual

\end{thebibliography}
\end{document}