# HG changeset patch # User mir3636 # Date 1477059949 -32400 # Node ID 45bc92a01821241f81978872a8f472c27d68ce69 # Parent 6abb63b73e47e050dff33ec78aed781f66278bfa fix diff -r 6abb63b73e47 -r 45bc92a01821 midterm.tex --- a/midterm.tex Fri Oct 21 22:41:40 2016 +0900 +++ b/midterm.tex Fri Oct 21 23:25:49 2016 +0900 @@ -25,32 +25,31 @@ \maketitle \thispagestyle{fancy} -\section{研究目的} +\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、データを Data Segment とした単位を用いたプログラミング言語 Continuation based C (CbC)を開発している。 - +また、Code Segment 単位を用いたプログラミング言語 Continuation based C (CbC)を開発している。 CbCは軽量継続による遷移を行うので、継続前の Code Segment に戻ることはなく、状態遷移ベースのプログラミングに適している。 -CbCと同様に処理を Code Gear、データを Data Gear とした単位を用いた並列実行をサポートした Gears OS も開発している。 Gears OS は CbC で記述されている。 +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 では C の関数の代わりに Code Segment を用いて処理を記述している。 -Code Segment の宣言は C の関数の構文と同様に記述し、型に \_\_code を使うことで宣言できる。 +CbC では Code Segment は \_\_code という型を持つ関数の構文で定義される。 -Code Segment は C の関数と異なり戻り値を持たず、 Code Segment 間の移動は goto の後に Code Segment 名と引数を並べて記述する独自の構文を用いて行う。 +Code Segment は 戻り値を持たないので、return 文は存在しない。goto の後に Code Segment 名と引数を並べて、次の Code Gears の遷移を記述する。 -この goto による処理の遷移を継続と呼ぶ。図\ref{fig:codesegment} は Code Segment 間の処理の流れを表している。 +この goto の行き先を継続と呼ぶ。Scheme の継続と異なり CbC には環境がないので、この継続は単なる行き先である。したがってこれを軽量継続と呼ぶこともある。図\ref{fig:codesegment} は Code Segment 間の処理の流れを表している。 \begin{figure}[htpb] \centering @@ -59,38 +58,21 @@ \label{fig:codesegment} \end{figure} -C では関数呼び出しを行う際、現在までの位置を環境として保持するが、戻り値を持たない Code Segment は呼び出し元の環境を保持しない。 -ここで環境とは現在のスタックの状態のことを指す。このように呼び出し元の環境を持たない継続を軽量継続と呼ぶ。 -軽量継続によって、並列化、ループ制御、関数コールといったスタックを意識した最適化がソースコードレベルで行うことができる。 - -しかし CbC と C の記述を交える際、CbC の code segment から C の関数への呼び出しは問題なく行えるが、逆の場合呼び出し元の環境に戻るための特殊な継続が必要となる。これを環境付き継続とよぶ。 - -環境付き継続を用いる場合 C の関数から code segment へ接続する際に \_\_return、\_\_environment という変数を渡す。 -\section{LLVM/clang} +\section{LLVM/clang による CbC の実装} LLVM とは、モジュラー構成および再利用可能なコンパイラとツールチェーン技術等を開発するプロジェクトの名称である。 -単に LLVM といった場合は LLVM Core のことを指す。以降は本文でも単に LLVM といった場合は LLVM Core のことを指す。 - -LLVM はコンパイラ基盤であり、コンパイラのバックエンド部分の処理を行う。 -LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語や実行可能なファイルに変換することができる。また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。 - -LLVM のフロントエンドはターゲットの言語を LLVM IR に変換することによって LLVM の最適化機構を利用することができる。 +LLVM IR や LLVM BitCode と呼ばれる独自の中間言語を持ち、それを機械語に変換することができる。また、この言語で書かれたプログラムを実行するための仮想機械としても動作する。 clang は LLVM をバックエンドとして利用する C/C++/Objective-C のコンパイラである。 -フロントエンドとして clang を使用し、与えられたコードから LLVM IRを生成し、LLVM はこれを最適化し機械語に変換を行う。 - -LLVM は LLVM IR を直接的にターゲットのアセンブリ言語へ変換を行うわけではなく、中間表現を何度か変えその度に最適化を行い、最終的にターゲットのアセンブリ言語に変換する。 - -LLVMでは、最適化や中間表現の変換といったコンパイラを構成する処理は全てpassが行う。多くの pass は最適化のために存在し、この pass を組み合わせることにより、LLVM の持つ機能の中から任意のものを利用することができる。 - -LLVM ターゲットのアセンブリ言語を生成するまでの過程を記すと以下のようになる。 +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 でなくなる。 + 仮想レジスタから物理レジスタへの割り当てを行う。ここで PHI 命令が削除され、SSA-based でなくなる。 \subsubsection*{Prolog/Epilog Code Insertion} Prolog/Epilog Code の挿入を行う。どちらも関数呼び出しに関わるものであり、Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理、Epilog は呼び出し元の関数に戻る際に行う処理である。 \subsubsection*{Late Machine Code Optimizations} @@ -105,7 +87,7 @@ \label{fig:llvmProcess} \end{figure} -\section{LLVM/clang のリファクタリング} +\section{LLVM/clang のデバッグ} LLVM/clang で CbC をコンパイルした際 Code Segment 内の局所変数でポインタを参照すると tail call されないという不具合があることがわかった。 局所変数でポインタを参照していると clang は生成する LLVM IR に オブジェクトの寿命を示す lifetime.start と lifetime.end を書き出す。 @@ -116,20 +98,23 @@ そこで lifetime.end を tail call の直前で生成を行うことで tail call を出すようにした。 \section{Gears OS の構文サポート} -Gears OS では並列実行するための Task を実行する Code Gear と実行に必要な Input Data Gear 、出力される Output Data Gear の組で表現する。 -Input/Output Data Gear によって依存関係が決定し並列実行を行う。 +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 の構文のサポートを CbC を用いて行う。 +そこで Gears OS の構文のサポートが必要になる。現在は python を用いたプログラム変換で実現されている。 Gears OS では Context という接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Dara Gear である。Gears OS では必要な Code/Data Gear に参照したい場合、Context を通す必要がある。 - -Context は膨大であるためプログラマが記述するには負担であるため CbC では Context の自動生成を行うようにする。 +Context の自動生成を行うようにする。 \section{今後の課題} -本研究では LLVM/clang によるコンパイルの際、Code Segment 内の局所変数で tail call が出ない不具合を修正した。今後の課題としては、まだ Gears OS の構文サポートの実装が行われていないのでこれを実装することが優先される。 +今後の課題は現状の Gears OS のコードをリファクタリングし通常計算とメタ計算の分離を明確にする。 +必要なメタ計算部分の CbC による実装を統一する。 +Context 、 Meta Code Gear 、 Meta Data Gear を生成するプログラム変換系を作成する。 +これを用いて Gears OS の記述を行う。 +これにより Gears OS のメタ計算を柔軟に行うことができるようになり、 Gears OS 自体の信頼性を向上し, Gears OS の拡張性を実現することができると考えられる。 \begin{thebibliography}{9} \bibitem{1}