Papers/2016/kaito-cq: paper.tex annotate

annotate paper.tex @ 2:7cc0be313596

fix

author	Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date	Tue, 01 Mar 2016 17:16:15 +0900
parents	1c933f3a5cb7
children	d9b703be7359

rev	line source
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	1 \documentclass[conference]{IEEEtran}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	2
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	3 \usepackage[cmex10]{amsmath}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	4 \usepackage{url}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	5 \usepackage{listings}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	6 \usepackage[dvipdfmx]{graphicx}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	7
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	8 \lstset{
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	9 frame=single,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	10 keepspaces=true,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	11 stringstyle={\ttfamily},
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	12 commentstyle={\ttfamily},
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	13 identifierstyle={\ttfamily},
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	14 keywordstyle={\ttfamily},
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	15 basicstyle={\ttfamily},
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	16 breaklines=true,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	17 xleftmargin=0zw,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	18 xrightmargin=0zw,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	19 framerule=.2pt,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	20 columns=[l]{fullflexible},
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	21 numbers=left,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	22 stepnumber=1,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	23 numberstyle={\scriptsize},
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	24 numbersep=1em,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	25 language=c,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	26 tabsize=4,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	27 lineskip=-0.5zw,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	28 escapechar={@},
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	29 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	30
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	31 \ifCLASSINFOpdf
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	32 % \usepackage[pdftex]{graphicx}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	33 % declare the path(s) where your graphic files are
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	34 % \graphicspath{{../pdf/}{../jpeg/}}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	35 % and their extensions so you won't have to specify these with
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	36 % every instance of \includegraphics
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	37 % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	38 \else
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	39 % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
8319d82cab07 add files 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
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	41 % driver is specified.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	42 % \usepackage[dvips]{graphicx}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	43 % declare the path(s) where your graphic files are
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	44 % \graphicspath{{../eps/}}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	45 % and their extensions so you won't have to specify these with
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	46 % every instance of \includegraphics
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	47 % \DeclareGraphicsExtensions{.eps}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	48 \fi
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	49
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	50
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	51 % correct bad hyphenation here
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	52 \hyphenation{op-tical net-works semi-conduc-tor}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	53
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	54
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	55 \begin{document}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	56 %
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	57 % paper title
8319d82cab07 add files 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,
8319d82cab07 add files 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
8319d82cab07 add files 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.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	61 % Linebreaks \\ can be used within to get better formatting as desired.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	62 % Do not put math or special symbols in the title.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	63 \title{LLVM と Clang を利用した新しい言語の実装}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	64
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	65 % author names and affiliations
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	66 % use a multiple column layout for up to three different
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	67 % affiliations
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	68 \author{
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	69 \IEEEauthorblockN{徳森海斗}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	70 \IEEEauthorblockA{琉球大学 \\ Email: kaito@cr.ie.u-ryukyu.ac.jp}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	71 \and
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	72 \IEEEauthorblockN{河野真治}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	73 \IEEEauthorblockA{琉球大学 \\ Email: kono@ie.u-ryukyu.ac.jp}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	74 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	75
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	76 % make the title area
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	77 \maketitle
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	78
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	79 % no keywords
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	80
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	81
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	82
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	83
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	84 % For peer review papers, you can put extra information on the cover
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	85 % page as needed:
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	86 % \ifCLASSOPTIONpeerreview
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	87 % \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	88 % \fi
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	89 %
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	90 % For peerreview papers, this IEEEtran command inserts a page break and
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	91 % creates the second title. It will be ignored for other modes.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	92 \IEEEpeerreviewmaketitle
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	93
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	94
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	95
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	96 本章では LLVM と Clang を利用した新しいプログラミング言語のコンパイラの実装を行う方法を Continuaton based C(CbC)\ref{cbc}
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	97 という言語の実装例とともに説明する.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	98 LLVMとClangは、C++ で記述されており、GCCよりも見通し良く書かれている。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	99 LLVMは汎用のコンパイラフレームワークであり、プログラミング言語の構文解析、中間コード生成、機械語生成の各段階で様々なサポートがある。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	100 LLVMで新しい言語を作る方法には様々な方法がある。一つは自作の構文解析器からLLVMの抽象構文木生成のAPI呼び出す方法である。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	101 また、LLVM IRという中間コードを直接生成しても良い。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	102 DSL(ドメイン特化言語)のような場合は、それですむことが多い。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	103 しかし、LLVMの機能を越えたプログラミング言語を作成したい場合は、LLVMの内部に立ち入る必要がある。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	104
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	105 CbCは組み込みシステムやOSなどのメタ計算、あるいは言語処理系そのものの実装に的にするように設計された言語である。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	106 コードセグメントという単位と、それを接続する軽量継続(引数付き大域goto文)を持つ。このように関数呼び出しそのものを
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	107 独自に持つような言語を実装するにはLLVM自体をLLVMの大域的局所的な最適化に干渉しないように修正する必要がある。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	108
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	109 ここではLLVMの内部構造について詳細に説明し、CbCでの修正方法について説明していく。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	110
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	111 % また, この実装では LLVM IR に変更を加えることはしない. LLVM IR に変更を加える事は可能であるが, そうした場合最適化を含む LLVM の全てのパスがその変更の影響を受け, 対応させなければならくなる. これは大変難しく現実的でない.
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	112
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	113 % \section{Continuation based C}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	114 % 今回例として用いる Continuation based C \cite{CbC2011}(以下 CbC) は code segment という処理単位を持つ.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	115 % code segment の宣言は \_\_code という型を用いて行うとする. リスト \ref{code_simple} は最も基本的な CbC のコードの一例で, 図 \ref {fig:code_simple}はそれを図示したものである.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	116 %
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	117 % 現在の code segment から次の code segment への処理の移動は goto のあとに code segment 名と引数を並べて記述することで次の code segment へと処理を移す (これを軽量継続と呼ぶ) .
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	118 % 軽量継続では Secheme の call/cc 等の継続と異なり呼び出し元の環境を持たない.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	119 %
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	120 % \begin{lstlisting}[float=*,frame=lrbt,label=code_simple,caption={\footnotesize code segment の軽量継続}]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	121 % __code cs0(int a, int b){
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	122 % goto cs1(a+b);
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	123 % }
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	124 %
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	125 % __code cs1(int c){
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	126 % goto cs2(c);
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	127 % }
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	128 % \end{lstlisting}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	129 %
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	130 % \begin{figure}[htp]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	131 % \begin{center}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	132 % \scalebox{0.55}{\includegraphics{fig/codesegment.pdf}}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	133 % \end{center}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	134 % \caption{code segment の軽量継続}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	135 % \label{fig:code_simple}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	136 % \end{figure}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	137 %
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	138
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	139 \section{LLVM clang}
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	140 LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本稿でも, 単に LLVM といった場合は LLVM Core を指す.
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	141
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	142 LLVMは、 LLVM IR という独自の中間言語を持つ。これはアーキテクチャ依存でない型付きのアセンブラとなっている。人が読める形式のものと
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	143 LLVM BitCode というビットストリームにエンコードされたものがある。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	144 LLVMはLLVM IRを実行することのできる仮想機械も持ち、もちろん、.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	145 LLVM IR を最適化しながら特定のターゲットの機械語に変換することもできる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	146
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	147 clang はバックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたソースコードを解析し,
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	148 抽象構文木(AST)を生成する。そして、そのASTを LLVM IR に変換し、LLVM Coreによりターゲットマシンの機械語に変換する.
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	149 GCC と比較すると丁寧でわかりやすいエラーメッセージを出力する, コンパイル時間が短いといった特徴を持つ.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	150
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	151 clang は library-based architecture というコンセプトの元に設計されており, 字句解析を行う liblex, 構文解析を行う libparse といったように処理機構ごとに複数のライブラリに分割されている.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	152 clang はこれらのライブラリを与えられた引数に応じて呼び出し, コンパイルを行う.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	153 さらに, 必要な場合は外部のリンカを呼び出してリンクを行い, ソースコードを実行可能な状態まで変換することも可能である.
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	154
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	155 ここで, そのライブラリの中でもclangが使用するコンパイルに関連するものについて説明する.
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	156
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	157 \begin{description}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	158 \item[libast]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	159 Abstract Syntax Tree (AST) や C の型等をクラスとして利用できるようにしたライブラリ. AST の説明は後述する. % AST は ``-Xclang -ast-dump'' オプションを付加することで表示できる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	160 \item[liblex]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	161 字句解析ライブラリ. マクロの展開等の前処理系も担当する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	162 \item[libparse]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	163 構文解析ライブラリ. 解析結果を元に後述するlibsemaを使用して AST を生成する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	164 \item[libsema]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	165 意味解析ライブラリ. parser (libparse) に AST を生成する機能を提供する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	166 \item[libcodegen]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	167 コード生成ライブラリ. 生成された AST を LLVM IR に変換する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	168 \item[clang]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	169 ドライバ. 各ライブラリを用いて求められた処理を行う.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	170 \end{description}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	171
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	172 これを踏まえて clang が C のコードを LLVM IR に変換する処理について説明する. 尚 LLVM IR がアセンブリ言語にコンパイルされる処理の過程については\ref{sec:llvm}節で LLVM の基本構造とともに説明する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	173
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	174 以下の図\ref{fig:clangProcess}は clang が C のコードを LLVM IR に変換する処理の過程を簡潔に図示したものである. clang は C のソースコードを受け取るとまずその解析を libparser による parser を用いて行い, libsema を用いて解析結果から AST を構築する. そしてその AST を libcodegen を用いて LLVM IR に変換する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	175
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	176 \begin{figure}[htpb]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	177 \begin{center}
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	178 \scalebox{0.175}{\includegraphics{fig/clangProcess.pdf}}
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	179 \end{center}
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	180 \caption{clang の処理過程}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	181 \label{fig:clangProcess}
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	182 \end{figure}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	183
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	184 \begin{lstlisting}[float=*,basicstyle=\tiny,frame=tb, label=AST, caption={sample.c の AST}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	185 TranslationUnitDecl 0x102020cd0 <<invalid sloc>>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	186 \|-TypedefDecl 0x1020211b0 <<invalid sloc>> __int128_t '__int128'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	187 \|-TypedefDecl 0x102021210 <<invalid sloc>> __uint128_t 'unsigned __int128'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	188 \|-TypedefDecl 0x102021560 <<invalid sloc>> __builtin_va_list '__va_list_tag [1]'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	189 \|-FunctionDecl 0x102021700 <sample.c:1:1, line:3:1> add 'int (int, int)'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	190 \| \|-ParmVarDecl 0x1020215c0 <line:1:9, col:13> a 'int'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	191 \| \|-ParmVarDecl 0x102021630 <col:16, col:20> b 'int'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	192 \| `-CompoundStmt 0x102021878 <col:22, line:3:1>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	193 \| `-ReturnStmt 0x102021858 <line:2:3, col:14>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	194 \| `-BinaryOperator 0x102021830 <col:10, col:14> 'int' '+'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	195 \| \|-ImplicitCastExpr 0x102021800 <col:10> 'int' <LValueToRValue>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	196 \| \| `-DeclRefExpr 0x1020217b0 <col:10> 'int' lvalue ParmVar 0x1020215c0 'a' 'int'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	197 \| `-ImplicitCastExpr 0x102021818 <col:14> 'int' <LValueToRValue>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	198 \| `-DeclRefExpr 0x1020217d8 <col:14> 'int' lvalue ParmVar 0x102021630 'b' 'int'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	199 `-FunctionDecl 0x1020218f0 <line:5:1, line:9:1> main 'int ()'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	200 `-CompoundStmt 0x1020523c0 <line:5:11, line:9:1>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	201 \|-DeclStmt 0x102052210 <line:6:3, col:10>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	202 \| `-VarDecl 0x1020219a0 <col:3, col:7> res 'int'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	203 \|-BinaryOperator 0x102052338 <line:7:3, col:16> 'int' '='
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	204 \| \|-DeclRefExpr 0x102052228 <col:3> 'int' lvalue Var 0x1020219a0 'res' 'int'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	205 \| `-CallExpr 0x102052300 <col:9, col:16> 'int'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	206 \| \|-ImplicitCastExpr 0x1020522e8 <col:9> 'int (*)(int, int)' <FunctionToPointerDecay>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	207 \| \| `-DeclRefExpr 0x102052250 <col:9> 'int (int, int)' Function 0x102021700 'add' 'int (int, int)'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	208 \| \|-IntegerLiteral 0x102052278 <col:13> 'int' 1
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	209 \| `-IntegerLiteral 0x102052298 <col:15> 'int' 1
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	210 `-ReturnStmt 0x1020523a0 <line:8:3, col:10>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	211 `-ImplicitCastExpr 0x102052388 <col:10> 'int' <LValueToRValue>
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	212 `-DeclRefExpr 0x102052360 <col:10> 'int' lvalue Var 0x1020219a0 'res' 'int'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	213 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	214
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	215
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	216 \section{clangAST について}
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	217 LLVM と clang を用いたコンパイラの実装では基本的に clang の中間表現である clangAST を組み立てていくことになる. clangAST はソースコードの解析結果を保持したツリーである.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	218 AST は \\
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	219 \begin{lstlisting}[basicstyle=\tiny,frame=lrbt, caption={ASTを表示するオプション}]
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	220 -Xclang -ast-dump
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	221 \end{lstlisting}
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	222 というオプションを付加することで表示することもできる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	223 例えば、簡単なCのソースコード(\ref{ASTSampleCode})は、
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	224 リスト\ref{AST}のようになる。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	225
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	226 \begin{lstlisting}[basicstyle=\tiny,frame=lrbt, label=ASTSampleCode, caption={sample.c}]
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	227 int add(int a, int b){
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	228 return a + b;
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	229 }
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	230
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	231 int main(){
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	232 int res;
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	233 res = add(1,1);
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	234 return res;
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	235 }
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	236 \end{lstlisting}
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	237
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	238 出力された AST の各行が AST のノードなっており, 各ノードは Decl, Stmt, Expr といったC++のクラスを継承したものになっている.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	239 それぞれの簡単な説明を以下に記す (各クラスの詳細な実装は clang documentation\cite{clang} を参考に).
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	240
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	241 \begin{description}
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	242 \item[Decl]\mbox{}\\
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	243 宣言や定義を表すクラスであり, 関数の宣言を表す FunctionDecl, 変数の宣言を表す VarDecl 等のサブクラスが存在する.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	244 \item[Stmt]\mbox{}\\
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	245 一つの文に対応するクラスであり, if 文と対応する IfStmt, 宣言文と対応する DeclStmt, return 文と対応する ReturnStmt 等のサブクラスが存在する.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	246 \item[Expr]\mbox{}\\
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	247 一つの式に対応するクラスであり, 関数呼び出しと対応する CallExpr, キャストと対応する CastExpr 等のサブクラスが存在する.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	248 \end{description}
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	249
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	250
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	251
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	252 1行目の TranslationUnitDecl が根ノードに当たる. TranslationUnitDecl は翻訳単位を表すクラスであり, この AST が一つのファイルと対応していることがわかる. 実際にソースコードの内容が反映されているのは5行目以降のノードで, 5行目の FunctionDecl がソースコード\ref{ASTSampleCode}の1行目, add 関数の定義部分に当たる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	253 対応するソースコードの位置が明らかな場合は\verb+sample.c1:1+などと指定されており、そうでない場合は\verb+<<invalid sloc>>+となっている。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	254 型名や変数名などがASTに格納されていることもわかる。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	255 ソースコード\ref{ASTSampleCode}の7行目の add 関数の呼び出しは, AST ではリスト\ref{AST}の21行目, CallExpr で表されている.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	256 この CallExpr の下のノードを見ていくと23行目の DeclRefExpr が関数のアドレス0x102021700を持っており,
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	257 これが add 関数のアドレスと一致することから, CallExpr は呼び出す関数への参照を持っていることがわかる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	258 これらのノード以外についても return 文は ReturnStmt, 変数宣言は VarDecl というように,
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	259 各ノードがソースコードのいずれかの部分に対応していることが読み取れる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	260
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	261
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	262 \section{LLVMでの型の扱い}
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	263
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	264 clangに新しい機能を付け加えるには新しい型が必要となることがある。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	265 clang で新しい型を扱えるようにするためには, まず型の表す予約後(KEYWORD)を登録する,
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	266 そして、それに対応する識別子を登録する,
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	267 それを QualType (Qaulified type)というC++のオブジェクトの扱う Type として登録をするという手順になる。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	268 ここで新しく作られた型はIRレベルでは基本的な型に展開されてしまうので、LLVMの最適化と衝突することはない。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	269
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	270 clang では, 予約語は全て \$(CLANG)\footnote{clang のソースコードを展開したディレクトリのパス}/include/ clang/Basic/TokenKinds.def に定義されている.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	271 ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	272
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	273 ここでは CbC のコードセグメントを表す型である\_\_code を追加してみよう。
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	274 \_\_code という型は実際には\verb+void *+だが、これを関数の戻り値の型と指定することにより、その関数がコードセグメントであることを表す.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	275
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	276 まず、TokenKinds.def のKEYWORDにに\_\_code を追加する.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	277 これで \_\_code に対応する token の id が kw\_\_\_code になる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	278 ここで使われている KEYWORD はCのマクロであり、予約語の定義に用いられる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	279 KEYWORDの第一引数が登録したい予約語, 第二引数のKEYALLはその予約語が利用される範囲を表す.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	280 KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	281 \verb+noCbC+はCbCでの変更部分を示す条件マクロになっている.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	282
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	283 \begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=token,caption={キーワードの登録}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	284 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	285 KEYWORD(__func__ , KEYALL)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	286 KEYWORD(__objc_yes , KEYALL)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	287 KEYWORD(__objc_no , KEYALL)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	288
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	289 #ifndef noCbC // CbC Keywords.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	290 KEYWORD(__code , KEYALL)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	291 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	292 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	293 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	294 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	295
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	296 予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. 次は clang 内部で使用する識別子を作る.
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	297
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	298 clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include /clang/Basic/Specifiers.h で行われており, これを以下のように編集した.
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	299
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	300 \begin{lstlisting}[frame=lrbt,,basicstyle=\tiny,label=TST,caption={TypeSpecTypeの登録}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	301 enum TypeSpecifierType {
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	302 TST_unspecified,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	303 TST_void,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	304 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	305 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	306 TST___code,
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	307 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	308 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	309 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	310 これに加えてさらに QualType が用いる Type を作らなければならない.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	311
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	312 QualType は変数や関数等の型情報を持つクラスで, const, volatile 等の修飾子の有無を示すフラグと, int, char, * (ポインタ) 等の型情報を持つ Type オブジェクトへのポインタを持つ.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	313 QualType の持つ Type オブジェクトは getTypePtr 関数を呼び出すことで取得でき, Type クラスは isIntegerType, isVoidType, isPointerType と言った関数を持つので, これを利用して型を調べることができる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	314 また, ポインタ型である場合には getPointeeType という関数を呼び出すことでそのポインタが指す型の Type を持つ QualType を得ることができ,
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	315 それを通してポインタの指す型を知ることが可能である.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	316 配列や参照等に対しても同様に, それぞれ要素, 参照元の Type へのポインタを持つ QualType を得る関数が存在する.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	317 修飾子の有無は const なら isConstQualified, volatile なら isVolatileQualified といった関数を用いて確認できる.
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	318
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	319 ここで, 以下に一つの例として ``const int *'' 型に対応する QualType を表した図を示す.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	320
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	321 \begin{figure}[htpb]
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	322 \begin{center}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	323 \scalebox{0.2}{\includegraphics{fig/qualType.pdf}}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	324 \end{center}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	325 \caption{const int * に対応する QualType}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	326 \label{fig:qual}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	327 \end{figure}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	328
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	329 図\ref{fig:qual}の QualType A が const int * 型の変数, もしくは関数の持つ QualType である. これの持つ getTypePtr 関数を呼び出すことで, PointerType を得ることができる. この PointerType がどの型に対するポインタかを知るには前述したとおり getPointeeType を呼び出せば良い. そうして呼び出されたのが QualType B である. この例の QualType は const int * 型に対応するものであるので, ここで取得できた QualType B のgetTypePtr 関数を呼び出すと, 当然 IntegerType が得られる. また, この時 int には const がかかっているので, QualType B の isConstQualified 関数を呼ぶと true が返る.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	330
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	331
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	332 このように, clang では複雑な型を持つ関数, 変数でもその型を表すために持つ QualType は一つであり, それが指す Type を辿ることで完全な型を知ることができる.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	333
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	334 この Type の定義は \$(CLANG)/include/ clang/AST/BuiltinTypes.def で行われているので, これを編集する(リスト\ref{clangType}).
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	335 ここで使用されているマクロには符号付き整数であることを示す SIGNED\_TYPE や符号無し整数であることを示す UNSIGNED\_TYPE 等があり, それらは BUILTIN\_TYPE マクロを拡張するものである.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	336 \_\_code 型は符号無し,有りといった性質を保つ必要はないため, 今回は BUILTIN\_TYPE を使うべきである.
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	337
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	338 \begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=clangType,caption={Typeの登録}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	339 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	340 // 'bool' in C++, '_Bool' in C99
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	341 UNSIGNED_TYPE(Bool, BoolTy)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	342
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	343 // 'char' for targets where it's unsigned
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	344 SHARED_SINGLETON_TYPE(UNSIGNED_TYPE(Char_U, CharTy))
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	345
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	346 // 'unsigned char', explicitly qualified
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	347 UNSIGNED_TYPE(UChar, UnsignedCharTy)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	348
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	349 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	350 BUILTIN_TYPE(__Code, __CodeTy)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	351 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	352 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	353 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	354
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	355 ここまでの変更で clang が \_\_code 型を扱えるようになった.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	356 % り, \_\_code 型の関数, 即ち code segment を解析する準備が整った.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	357
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	358
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	359 次は clang が \_\_code 型を解析し clangAST に変換できるようにしなければならない.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	360 clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	361 この関数のもつ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い.
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	362 具体的には switch 文内に以下のように記述を加えた. また, この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われている.
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	363
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	364 \begin{lstlisting}[float=*,frame=lrbt,label=parse__Code,caption={\_\_code の parse}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	365 case tok::kw___code: {
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	366 LangOptions* LOP;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	367 LOP = const_cast<LangOptions*>(&getLangOpts());
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	368 LOP->HasCodeSegment = 1;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	369 isInvalid = DS.SetTypeSpecType(DeclSpec::TST___code, Loc, PrevSpec, DiagID);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	370 break;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	371 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	372 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	373
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	374 重要なのは 5行目である. SetTypeSpecType 関数はその名の通り TypeSpecType を設定する関数であり, ここで \_\_code 型が DeclSpec に登録される. DeclSpec は型の識別子を持つためのクラスであり, 後に QualType に変換される.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	375
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	376 \section{LLVM の基本構造}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	377 \label{sec:llvm}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	378 LLVM は LLVM IR をターゲットのアセンブリ言語に直接的に変換を行うわけではない. 中間表現を何度か変え, その度に最適化を行い, そして最終的にターゲットのアセンブリ言語に変換するのである.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	379 また LLVM では, 最適化や中間表現の変換といったコンパイラを構成する処理は全て pass が行う. 多くの pass は最適化のために存在し, この pass を組み合わせることにより, LLVM の持つ機能の中から任意のものを利用することができる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	380
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	381 LLVM がターゲットのアセンブリ言語を生成するまでの過程を簡潔に記すと以下のようになる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	382
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	383 \begin{description}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	384 \item[SelectionDAG Instruction Selection (SelectionDAGISel)]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	385 LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し, 最適化を行う. その後 Machine Code を生成する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	386 \item[SSA-based Machine Code Optimizations]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	387 SSA-based Machine Code に対する最適化を行う. 各最適化はそれぞれ独立した pass になっている.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	388 \item[Register Allocation]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	389 仮装レジスタから物理レジスタへの割り当てを行う. ここで PHI 命令が削除され, SSA-based でなくなる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	390 \item[Prolog/Epilog Code Insertion]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	391 Prolog/Epilog Code の挿入を行う. どちらも関数呼び出しに関わるものであり, Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理, Epilog は呼び出し元の関数に戻る際に行う処理である.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	392 \item[Late Machine Code Optimizations]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	393 Machine Code に対してさらに最適化を行う.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	394 \item[Code Emission]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	395 Machine Code を MC Layer での表現に変換する. その後さらにターゲットのアセンブリ言語へ変換し, その出力を行う.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	396 \end{description}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	397
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	398 これらの処理の流れを図示したものが以下の図\ref{fig:llvmProcess}である. 前述した通りこれらの処理は全て pass によって行われる. pass にはいくつかの種類があり, 関数単位で処理を行うもの, ファイル単位で処理を行うもの, ループ単位で処理を行うもの等がある.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	399
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	400 \begin{figure}[htpb]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	401 \begin{center}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	402 \scalebox{0.175}{\includegraphics{fig/llvmProcess.pdf}}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	403 \end{center}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	404 \caption{LLVM の処理過程}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	405 \label{fig:llvmProcess}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	406 \end{figure}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	407
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	408
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	409 \section{LLVM の中間表現}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	410 この節では LLVM の中間表現である LLVM IR, SelectionDAG, Machine Code, MC Layer\footnote{ MC Layer は正確には中間表現ではない. 詳しくは本節で後述する. } と LLVM の最適化について簡単に説明する. なお, 詳しくは LLVM Documantation\cite{LLVM}を参照していただきたい.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	411
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	412 LLVM のメインとなる中間表現はフロントエンドの出力, バックエンドの入力に対応する LLVM IR である.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	413
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	414 LLVM IR はLLVM BitCode とも呼ばれ, リファレンスが公開されている\cite{LLVMIR}. この言語で記述したプログラムを LLVM 上で実行することも可能である. 各変数が一度のみ代入される Static Single Assignment (SSA) ベースの言語であり, コンパイラ中のメモリ上での形式, 人が理解しやすいアセンブリ言語形式 (公開されているリファレンスはこの形式に対するものである), JIT 上で実行するための bitcode 形式の三種類の形を持ち, いずれも相互変換が可能で同等なものである. ループ構文は存在せず, 一つのファイルが一つのモジュールという単位で扱われる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	415
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	416 LLVM IR の一例として c 言語の関数を clang を用いて LLVM IR に変換したものをリスト \ref{IRtestC}, \ref{IRtestIR} に示す. LLVM IR に変換された後の関数 test を見ると, while文によるループ構文がなくなっていることがわかる. while文は while.cond, while.body という 2つのブロックに分けられており, while.cond が while文の条件文, while.body が while文の中身を表している. while.end は while という名が付いているが, while文と直接は関係しておらず, これは while文によるループ処理が終わった後の処理が置き換わったものである.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	417
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	418 \begin{lstlisting}[frame=lrbt, label=IRtestC, caption={c での関数 test}]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	419 int test(int a, int b){
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	420 int i, sum = 0;
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	421 i = a;
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	422 while ( i <= b) {
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	423 sum += i;
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	424 i++;
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	425 }
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	426 return sum - a * b;
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	427 }
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	428 \end{lstlisting}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	429
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	430 \begin{lstlisting}[frame=lrbt, label=IRtestIR, caption={LLVM IR での関数 test}]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	431 define i32 @test(i32 %a, i32 %b) #0 {
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	432 entry:
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	433 br label %while.cond
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	434
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	435 while.cond:
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	436 %i.0 = phi i32 [ %a, %entry ], [ %inc, %while.body ]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	437 %sum.0 = phi i32 [ 0, %entry ], [ %add, %while.body ]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	438 %cmp = icmp sle i32 %i.0, %b
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	439 br i1 %cmp, label %while.body, label %while.end
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	440
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	441 while.body:
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	442 %add = add nsw i32 %sum.0, %i.0
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	443 %inc = add nsw i32 %i.0, 1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	444 br label %while.cond
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	445
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	446 while.end:
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	447 %mul = mul nsw i32 %a, %b
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	448 %sub = sub nsw i32 %sum.0, %mul
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	449 ret i32 %sub
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	450 }
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	451 \end{lstlisting}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	452
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	453 SelectionDAG は LLVM IR が SelectionDAG Instruction Selection Pass によって変換されたものである. SelectionDAG は非巡回有向グラフであり, そのノードは SDNode クラスによって表される. SDNode は命令と, その命令の対象となるオペランドを持つ. SelectionDAG には illegal なものと legal なものの二種類が存在し, illigal SelectionDAGの段階ではターゲットがサポートしていない方や命令が残っている. LLVM IR は初め illegal SelectionDAG に変換され, legalization を含む多くの段階を踏んで次の中間表現である Machine Code になる. 以下に SelectionDAG が Machine Code に変換されるまでに行われる処理の過程を示す.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	454
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	455 \begin{description}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	456 \item[Build initial DAG]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	457 LLVM IR を illegal SelectionDAG に変換する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	458 \item[Optimize]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	459 illegal SelectionDAG に対して最適化を行う.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	460 \item[Legalize SelectionDAG Types]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	461 ターゲットのサポートしていない型を除去し, ターゲットのサポートする型だけで構成された SelectionDAG に変換する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	462 \item[Optimize]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	463 最適化. 型変換が行われたことで表面化した冗長性の解消を行う.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	464 \item[Legalize SelectionDAG Ops]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	465 ターゲットのサポートしていない命令を除去し, ターゲットのサポートする命令だけで構成された SelectionDAG に変換する. これで SelectionDAG の legalization が完了となる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	466 \item[Optimize]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	467 最適化. 命令を変更したことによって発生した非効率性を排除する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	468 \item[Select instructions from DAG]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	469 SelectionDAG を元に, 現在の命令をターゲットのサポートする命令に置き換えた DAG を生成する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	470 \item[SelectionDAG Scheduling and Formation]\mbox{}\\
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	471 命令のスケジューリングを行い, DAG を Machine Code に変換する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	472 \end{description}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	473
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	474 SelectionDAG を確認したい場合は clang に ``-mllvm -view-*-dags'' オプションを与えることで生成される dot ファイルを見れば良い. * には legalize などの文字列が入り, どの段階の DAG を出力するか選択することが出来る. 図 \ref{fig:dag} はリスト \ref{IRtestC} の add 関数に対応する legalize 直前の DAG である. この図より, + 演算子に対応する add ノードや return 命令に対応するノードその戻り値を受けるためのレジスタが指定されているのがわかる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	475
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	476
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	477 \begin{figure}[htpb]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	478 \begin{center}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	479 \scalebox{0.50}{\includegraphics{fig/dag.pdf}}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	480 \end{center}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	481 \caption{add 関数に対応する legalize 直前の SelectionDAG}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	482 \label{fig:dag}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	483 \end{figure}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	484
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	485
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	486 Machine Code は LLVM IR よりも機械語に近い形の中間言語であり, 無限の仮装レジスタを持つ Single Static Assignment (SSA) 形式と物理レジスタを持つ non-SSA 形式がある. SSA 形式とは全ての変数が一度のみ代入されるように記述した形式であり. この形式を取ることで LLVM は効率よく最適化を行うことが出来る.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	487
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	488 Machine Code は LLVM IR より抽象度は低いが, この状態でもまだターゲットに依存しない抽象度を保っている. Machine Code は LLVM 上では MachineFunction, MachineBasicBlock, MachineInstr クラスを用いて管理される. MachineInstr は一つの命令と対応し, MachineBasicBlock は MachineInstr のリスト, そして MachineFunction が MachineBasicBlock のリストとなっている.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	489
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	490 Machine Code の一例を以下のリスト \ref{MachineCodeSSA}, \ref{MachineCodeNonSSA}に示す. リスト \ref{MachineCodeSSA} が SSA 形式, リスト \ref{MachineCodeNonSSA} が non-SSA 形式であり, 元となるコードはリスト \ref{IRtestC} である. \%varg1, \%varg2 といったものが仮想レジスタであり, リスト \ref{MachineCodeSSA} に多く存在することが確認できる. しかし, リスト \ref{MachineCodeNonSSA} には1行目を除いてそれが存在しない. 1行目はこの関数の引数に対応する物理レジスタと仮想レジスタを並べて表記しているだけなので, ここに仮想レジスタが残っていることについて問題はなく, non-SSA 形式の Machine Code では仮想レジスタが取り除かれていることがわかる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	491 \begin{lstlisting}[frame=lrbt, label=MachineCodeSSA, caption={Machine Code (SSA)}]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	492 Function Live Ins: %EDI in %vreg4, %ESI in %vreg5
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	493
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	494 BB#0: derived from LLVM BB %entry
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	495 Live Ins: %EDI %ESI
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	496 %vreg5<def> = COPY %ESI
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	497 %vreg4<def> = COPY %EDI
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	498 %vreg6<def> = MOV32r0 %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	499 Successors according to CFG: BB#1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	500
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	501 BB#1: derived from LLVM BB %while.cond
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	502 Predecessors according to CFG: BB#0 BB#2
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	503 %vreg0<def> = PHI %vreg4, <BB#0>, %vreg3, <BB#2>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	504 %vreg1<def> = PHI %vreg6, <BB#0>, %vreg2, <BB#2>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	505 %vreg7<def,tied1> = SUB32rr %vreg0<tied0>, %vreg5, %EFLAGS<imp-def>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	506 JG_4 <BB#3>, %EFLAGS<imp-use>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	507 JMP_4 <BB#2>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	508 Successors according to CFG: BB#2(124) BB#3(4)
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	509
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	510 BB#2: derived from LLVM BB %while.body
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	511 Predecessors according to CFG: BB#1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	512 %vreg2<def,tied1> = ADD32rr %vreg1<tied0>, %vreg0, %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	513 %vreg3<def,tied1> = INC64_32r %vreg0<tied0>, %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	514 JMP_4 <BB#1>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	515 Successors according to CFG: BB#1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	516
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	517 BB#3: derived from LLVM BB %while.end
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	518 Predecessors according to CFG: BB#1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	519 %vreg8<def,tied1> = IMUL32rr %vreg4<tied0>, %vreg5, %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	520 %vreg9<def,tied1> = SUB32rr %vreg1<tied0>, %vreg8<kill>, %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	521 %EAX<def> = COPY %vreg9
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	522 RET %EAX
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	523 \end{lstlisting}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	524
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	525 \begin{lstlisting}[frame=lrbt, label=MachineCodeNonSSA, caption={Machine Code (non-SSA)}]
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	526 Function Live Ins: %EDI in %vreg4, %ESI in %vreg5
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	527
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	528 0B BB#0: derived from LLVM BB %entry
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	529 Live Ins: %EDI %ESI
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	530 48B %EAX<def> = MOV32r0 %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	531 64B %ECX<def> = COPY %EDI
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	532 Successors according to CFG: BB#1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	533
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	534 96B BB#1: derived from LLVM BB %while.cond
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	535 Live Ins: %ESI %EDI %ECX %EAX
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	536 Predecessors according to CFG: BB#0 BB#2
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	537 144B CMP32rr %ECX, %ESI, %EFLAGS<imp-def>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	538 160B JG_4 <BB#3>, %EFLAGS<imp-use,kill>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	539 176B JMP_4 <BB#2>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	540 Successors according to CFG: BB#2(124) BB#3(4)
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	541
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	542 192B BB#2: derived from LLVM BB %while.body
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	543 Live Ins: %ESI %EDI %ECX %EAX
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	544 Predecessors according to CFG: BB#1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	545 224B %EAX<def,tied1> = ADD32rr %EAX<kill,tied0>, %ECX, %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	546 256B %ECX<def,tied1> = INC64_32r %ECX<kill,tied0>, %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	547 304B JMP_4 <BB#1>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	548 Successors according to CFG: BB#1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	549
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	550 320B BB#3: derived from LLVM BB %while.end
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	551 Live Ins: %ESI %EDI %EAX
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	552 Predecessors according to CFG: BB#1
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	553 352B %EDI<def,tied1> = IMUL32rr %EDI<kill,tied0>, %ESI<kill>, %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	554 384B %EAX<def,tied1> = SUB32rr %EAX<kill,tied0>, %EDI<kill>, %EFLAGS<imp-def,dead>
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	555 416B RET %EAX
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	556 \end{lstlisting}
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	557
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	558 MC Layer は正確には中間表現を指すわけではなく, コード生成などを抽象化して扱えるようにした層である. 関数やグローバル変数といったものは失われており, MC Layer を用いることで, Machine Code からアセンブリ言語への変換, オブジェクトファイルの生成, JIT 上での実行と言った異なった処理を同一の API を用いて行うことが可能になる. MC Layer が扱うデータ構造は複数あるが, ここでは MCInst, MCStreamer, MCOperand について説明する.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	559
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	560 MCStreamer はアセンブラ API であり, アセンブリファイルの出力や, オブジェクトファイルの出力はこの API を通して行われる. ラベルや .align 等のディレクティブの生成はこの API を利用するだけで可能になる. しかし MCStreamer は機械語に対応する命令は持っておらず, それらの命令を出力するには MCInst クラスを用いる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	561
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	562 MCInst はターゲットに依存しないクラスである. 一つの機械語の命令を表し, 命令とオペランドから構成される.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	563
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	564 MCOperand はオペランドに対応し, MCInst はこのクラスを用いる.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	565
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	566 MC Layer で用いられる各クラスも ``-mllvm -asm-show-inst'' オプションを用いることで他の中間表現のように確認することが出来る. MCInst はアセンブリの各命令に対応しているので, アセンブリファイルにコメントとして出力される. リスト \ref{MCInst} は\ref{IRtestC} をコンパイルして得られるアセンブリコードの一部である. 各命令の隣にコメントで記されているのが MCInst, 下に記されているのが MCOperand である.
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	567
2 7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	568 % \begin{lstlisting}[frame=lrbt, label=MCInst, caption={アセンブリコードと MCInst}]
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	569 % _add: ## @add
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	570 % .cfi_startproc
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	571 % ## BB#0: ## %entry
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	572 % pushq %rbp ## <MCInst #2300 PUSH64r
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	573 % ## <MCOperand Reg:36>>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	574 % Ltmp0:
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	575 % .cfi_def_cfa_offset 16
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	576 % Ltmp1:
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	577 % .cfi_offset %rbp, -16
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	578 % movq %rsp, %rbp ## <MCInst #1684 MOV64rr
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	579 % ## <MCOperand Reg:36>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	580 % ## <MCOperand Reg:44>>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	581 % Ltmp2:
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	582 % .cfi_def_cfa_register %rbp
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	583 % addl %esi, %edi ## <MCInst #97 ADD32rr
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	584 % ## <MCOperand Reg:23>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	585 % ## <MCOperand Reg:23>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	586 % ## <MCOperand Reg:29>>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	587 % movl %edi, %eax ## <MCInst #1665 MOV32rr
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	588 % ## <MCOperand Reg:19>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	589 % ## <MCOperand Reg:23>>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	590 % popq %rbp ## <MCInst #2178 POP64r
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	591 % ## <MCOperand Reg:36>>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	592 % retq ## <MCInst #2460 RETQ>
7cc0be313596 fix Shinji KONO <kono@ie.u-ryukyu.ac.jp> parents: 1 diff changeset	593 % \end{lstlisting}
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	594
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	595 \section{オプションの追加}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	596 リスト\ref{parse__Code} では新たに作成した HasCodeSegment というオプションを変更する処理を行っている(4行目). このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, 最適化を利用するためである. このオプションは LangOptions というクラスによって管理されている. LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, それらは \$(CLANG)/include/clang/Basic/ LangOptions.def で定義される. これを以下のリスト \ref{langOpt} のように変更して HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明となっている.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	597
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	598 \begin{lstlisting}[float=*,frame=lrbt,label=langOpt,caption={LangOptions の追加}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	599 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	600 LANGOPT(ApplePragmaPack, 1, 0, "Apple gcc-compatible #pragma pack handling")
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	601
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	602 BENIGN_LANGOPT(RetainCommentsFromSystemHeaders, 1, 0, "retain documentation comments from system headers in the AST")
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	603
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	604 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	605 LANGOPT(HasCodeSegment , 1, 0, "CbC")
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	606 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	607 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	608 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	609
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	610 ただしこのオプションは clang 内で有効なもので, LLVM IR の処理以降も有効にしておきたい場合 LLVM 側でもオプションを新設し, 引き継ぐ必要がある.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	611
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	612 clang のオプションの値は \$(CLANG)/lib/CodeGen/BackendUtil.cpp 内の CreateTargetMachine 関数(\ref{option})で行われる.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	613
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	614 \begin{lstlisting}[float=*,frame=lrbt,label=option,caption={clang から LLVM へのオプションの引き継ぎ}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	615 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	616 Options.PositionIndependentExecutable = LangOpts.PIELevel != 0;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	617 Options.EnableSegmentedStacks = CodeGenOpts.EnableSegmentedStacks;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	618 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	619 Options.HasCodeSegment = LangOpts.HasCodeSegment;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	620 Options.GuaranteedTailCallOpt = LangOpts.HasCodeSegment;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	621 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	622 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	623 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	624
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	625 LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)\footnote{LLVMのソースコードをインストールしたディレクトリのパス}/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	626
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	627 \begin{lstlisting}[float=*,frame=lrbt,label=option,caption={clang から LLVM へのオプションの引き継ぎ}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	628 class TargetOptions {
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	629 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	630 /// Emit target-specific trap instruction for 'unreachable' IR instructions.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	631 unsigned TrapUnreachable : 1;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	632
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	633 /// EmulatedTLS - This flag enables emulated TLS model, using emutls
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	634 /// function in the runtime library..
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	635 unsigned EmulatedTLS : 1;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	636 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	637 unsigned HasCodeSegment : 1;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	638 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	639 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	640 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	641
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	642
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	643 \section{新しい構文(軽量継続)の追加}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	644 次は新しい構文の追加について. ここでは CbC の軽量継続のための構文を追加する.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	645
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	646 CbC で軽量継続は goto に code segment 名を添えることで行う. この新しい goto syntax を追加する. 継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. したがって, goto の構文解析を行う際にこの構文も解析できるように変更を加える必要がある. clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, この関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に手を加える. 具体的には以下のように変更した.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	647
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	648
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	649 \begin{lstlisting}[float=*,frame=lrbt,label=ParseStmt,caption={goto 文の構文解析}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	650 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	651 case tok::kw_goto: // C99 6.8.6.1: goto-statement
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	652 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	653 if (!(NextToken().is(tok::identifier) && PP.LookAhead(1).is(tok::semi)) && // C: 'goto' identifier ';'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	654 NextToken().isNot(tok::star)) { // C: 'goto' '*' expression ';'
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	655 SemiError = "goto code segment";
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	656 return ParseCbCGotoStatement(Attrs, Stmts); // CbC: goto codesegment statement
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	657 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	658 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	659 Res = ParseGotoStatement();
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	660 SemiError = "goto";
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	661 break;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	662 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	663 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	664
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	665 ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下のリスト\ref{ParseCbCGotoStmt} に示す. このように, 長い処理を追加する場合には別のファイルを作成し, そこに関数として処理を定義するほうが LLVM, clang のアップデートの際に変更が楽になるため良い.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	666
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	667 \begin{lstlisting}[float=*,frame=lrbt,label=ParseCbCGotoStmt,caption={ParseCbCGotoStatement}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	668 StmtResult Parser::ParseCbCGotoStatement(ParsedAttributesWithRange &Attrs,StmtVector &Stmts) {
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	669 assert(Tok.is(tok::kw_goto) && "Not a goto stmt!");
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	670 ParseScope CompoundScope(this, Scope::DeclScope);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	671 StmtVector CompoundedStmts;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	672
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	673 SourceLocation gotoLoc = ConsumeToken(); // eat the 'goto'.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	674 StmtResult gotoRes;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	675 Token TokAfterGoto = Tok;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	676 Stmtsp = &Stmts;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	677
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	678 gotoRes = ParseStatementOrDeclaration(Stmts, false);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	679 if (gotoRes.get() == NULL)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	680 return StmtError();
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	681 else if (gotoRes.get()->getStmtClass() != Stmt::CallExprClass) { // if it is not function call
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	682 Diag(TokAfterGoto, diag::err_expected_ident_or_cs);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	683 return StmtError();
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	684 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	685
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	686 assert((Attrs.empty() \|\| gotoRes.isInvalid() \|\| gotoRes.isUsable()) &&
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	687 "attributes on empty statement");
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	688 if (!(Attrs.empty() \|\| gotoRes.isInvalid()))
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	689 gotoRes = Actions.ProcessStmtAttributes(gotoRes.get(), Attrs.getList(), Attrs.Range);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	690 if (gotoRes.isUsable())
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	691 CompoundedStmts.push_back(gotoRes.release());
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	692
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	693 // add return; after goto codesegment();
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	694 if (Actions.getCurFunctionDecl()->getResultType().getTypePtr()->is__CodeType()) {
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	695 ExprResult retExpr;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	696 StmtResult retRes;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	697 retRes = Actions.ActOnReturnStmt(gotoLoc, retExpr.get(), getCurScope());
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	698 if (retRes.isUsable())
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	699 CompoundedStmts.push_back(retRes.release());
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	700 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	701 return Actions.ActOnCompoundStmt(gotoLoc, Tok.getLocation(), CompoundedStmts, false);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	702 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	703 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	704
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	705 この関数では, goto の後の構文を解析して関数呼び出しの Stmt を生成する. その後, tail call elimination の条件を満たすために直後に return statement の生成も行う. 関数呼び出しの解析部分は ParseStatementOrDeclaration 関数に任せ, goto の後に関数呼び出しの構文がきていない場合にはエラーを出力する.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	706
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	707 return statement の生成は ActOnReturnStmt 関数を用いることで楽に行うことが出来る. 具体的には, 引数としてソードコードの位置を示す SourceLocation, Expr, 解析中のスコープを示す scope を与えれば良い. SouceLocation は Token から取得できる. Expr は宣言して生成されたものをすぐに利用して良い. そしてスコープは, getCurScope 関数によって取得できる現在のスコープを与えれば良い.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	708
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	709 こうして得られた二つの Stmt を StmtVector に入れ, ActOnCompoundStmt 関数に与えることで適切な Stmt が得られる.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	710
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	711 \section{最適化パスの選択}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	712 LLVM では最適化を含めすべての処理がパスによって行われる. 最適化パスを選択することで任意の最適化を利用することが出来る. パスは PassManager によって管理される. 基本的なパスのセットを追加してくれる populateFunctionPassManager, populateModulePassManager 等が存在し, clang でもそれを用いてパスの追加を行っている. なお, functionPassManager は関数単位で働くパスの PassManager で, modulePassManager はモジュール(ファイル)単位で働くパスの PassManager である.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	713
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	714 CbC では tail call elimination という最適化を強制する. そのためここでは TailCallElimPass の追加を例として示す.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	715
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	716 clang では \$(CLANG)/lib/CodeGen/BackendUtil.cpp の CreatePasses 関数から populateModulePassManager 関数を呼び出してパスの追加を行っている. clang では最適化レベルを 2 以上にした場合に tail call elimination が有効化されるがこれをレベルにかかわらず追加するように変更した (リスト\ref{PassManager}). 変数 MPM が PassManager で, add 関数を用いて pass の登録を行う. add 関数の引数に createTailCallEliminationPass 関数を指定することで tail call elimination pass が追加される.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	717
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	718 \begin{lstlisting}[float=*,frame=lrbt,label=PassManager,caption={tail call elimnation pass の追加}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	719 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	720 if (OptLevel == 0) {
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	721 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	722 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	723 MPM.add(createTailCallEliminationPass(true)); // Eliminate tail calls
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	724 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	725 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	726 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	727 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	728 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	729 MPM.add(createTailCallEliminationPass(false)); // Eliminate tail calls
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	730 #else
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	731 MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	732 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	733 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	734 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	735
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	736 \section{calling convention の選択}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	737 LLVM IR には関数呼び出しに様々なフラグをつけることが出来る. そのうちの一つに呼び出し規約がある. LLVM がサポートする呼び出し規約は ccc, fastcc, cc 10, cc 11 等多数存在する. その一部を簡潔にまとめると以下のようになる (詳しくは LLVM IR Language Reference\cite{LLVMIR}).
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	738
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	739 \begin{description}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	740 \item[ccc]\mbox{}\\
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	741 特に指定されていない場合にはこれになる. C の呼び出し規約に対応し, 可変長引数をサポートする. プロトタイプ宣言と関数の定義の不一致を許す.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	742 \item[fastcc]\mbox{}\\
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	743 この規約を指定すると, 情報をレジスタを用いて渡す等して, 可能な限り高速な呼び出しを試みるようになる. この呼び出し規約は可変引数をサポートせず, 呼び出される関数のプロトタイプと呼び出される関数が正確に一致する必要がある.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	744 \item[cc 10]\mbox{}\\
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	745 Glasgow Haskell Compiler のために実装された呼び出し規約. X86 でのみサポートされており, 引数に関するいくつかの制限をもつ. レジスタ内の値を全て渡し, 呼び出された関数はレジスタの値を保存できない. この呼び出し規約は関数型プログラミング言語を実装する際に使用される register pinning という技術の代わりとして特定の状況でしか使用してはならない.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	746 \item[cc 11]\mbox{}\\
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	747 High-Performance Erlang のために実装された呼び出し規約. 通常の C の呼び出し規約以上に引数を渡すためにレジスタを利用する. X86 でのみサポートされており, cc 10 同様に register pinning を用いる.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	748 \end{description}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	749
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	750 この呼出し規約は LLVM IR 以降で利用されるので clang が clangAST を LLVM IR に変換する前に付加するのが良い. 今回は clang が関数呼び出しの情報を設定する arrangeLLVMFunctionInfo という関数内で行った. この関数は \$(CLANG)/lib/CodeGen /CGCall.cpp にある. この関数に以下のリスト \ref{CC} に示されるコードを加えた. 5 行目が fastcc を設定している箇所である. この CC が後の処理で利用されることで fastcc が設定される. allowsOptionalArgs 関数は可変長引数を持つかどうかを判別するために使用している.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	751
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	752 \begin{lstlisting}[float=*,frame=lrbt,label=CC,caption={fastcc の追加}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	753 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	754 #ifndef noCbC
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	755 if(resultType.getTypePtr()->is__CodeType()){
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	756 if(!required.allowsOptionalArgs())
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	757 CC = llvm::CallingConv::Fast;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	758 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	759 #endif
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	760 :
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	761 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	762
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	763 \section{動作確認}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	764
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	765 ここまでの実装で clang を用いて CbC の基本的な構文を解釈できるようになった. おさらいすると以下の機能を実装した.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	766
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	767 \begin{itemize}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	768 \item \_\_code 型の登録
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	769 \item code segment の構文解析
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	770 \item 軽量継続のための構文の実装
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	771 \item tail call elimination の強制
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	772 \item fastcc 指定
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	773 \end{itemize}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	774
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	775 正しく実装出来ているか確認するために LLVM IR, アセンブリコードの二種を出力する. LLVM IR はコンパイル時に -S -emit-llvm というオプションをつけることで出力できる. リスト \ref{evalCbC} が元のコード, リスト \ref{evalIR} が LLVM IR, リスト \ref{evalAsm} がアセンブリコードである.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	776
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	777 CbC のコードには本来 C には存在しない \_\_code 型, goto による軽量継続の構文が存在するが, 今回の実装によりコンパイルが可能である. 出力された LLVM IR を確認すると, code segment の呼び出し時に tail call であることを示す tail フラグ, fastcc の関数呼び出し規約, 呼び出し直後の return 文が実装したとおりきちんと付加されていることがわかる.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	778
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	779 アセンブリコードの方では code segment f\_g0 への遷移が call 命令でなく jmp 命令で行われており, きちんと tail call elimination が強制されていることがわかる. これはオプションの引き継ぎが正しく行われたことを示す.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	780
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	781 \begin{lstlisting}[float=*,frame=lrbt,label=evalCbC,caption={CbCのコード}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	782 __code f(int i,stack sp) {
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	783 int k,j;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	784 k = 3+i;
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	785 goto f_g0(i,k,sp);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	786 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	787 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	788
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	789 \begin{lstlisting}[float=*,frame=lrbt,label=evalIR,caption={出力された LLVM IR}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	790 define fastcc void @f(i32 %i, i8* %sp) #0 {
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	791 entry:
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	792 %add = add nsw i32 3, %i
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	793 tail call fastcc void @f_g0(i32 %i, i32 %add, i8* %sp)
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	794 ret void
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	795 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	796 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	797
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	798 \begin{lstlisting}[float=*,frame=lrbt,label=evalAsm,caption={出力されたアセンブリコード}]
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	799 .cfi_startproc
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	800 ## BB#0: ## %entry
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	801 subq $24, %rsp
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	802 Ltmp9:
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	803 .cfi_def_cfa_offset 32
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	804 movl %edi, %eax
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	805 addl $3, %eax
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	806 movq %rsi, 16(%rsp) ## 8-byte Spill
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	807 movl %eax, %esi
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	808 movq 16(%rsp), %rdx ## 8-byte Reload
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	809 addq $24, %rsp
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	810 jmp _f_g0 ## TAILCALL
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	811 .cfi_endproc
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	812 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	813
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	814 \section{軽量継続の評価}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	815 今回実装した CbC の軽量継続を評価する. 比較対象は C の関数呼び出しとし, それぞれを大量に行った時の時間の差を確認する. 計測に使用したコードはリスト \ref{calc},\ref{calcCbC} で, 結果は表\ref{comp} である.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	816
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	817 結果より, 軽量継続が関数呼び出しよりも高速であることがわかる. 軽量継続では tail call elimination 等によってスタック操作の処理が省かれるのでその影響だろう.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	818
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	819 \begin{lstlisting}[frame=lrbt,label=calc,caption={Cの計測用コード}]
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	820 int func3(int a, int b){
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	821 return func4(b,b/a);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	822 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	823
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	824 int func2(int a, int b){
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	825 return func3(b,a*b);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	826 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	827 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	828
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	829 \begin{lstlisting}[frame=lrbt,label=calcCbC,caption={CbCの計測用コード}]
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	830 __code code3(int a, int b,
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	831 int loop, int ans){
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	832 goto code4(b,b/a,loop, ans);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	833 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	834
1 1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	835 __code code2(int a, int b,
1c933f3a5cb7 Improve with kono-teacher atton parents: 0 diff changeset	836 int loop, int ans){
0 8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	837 goto code3(b,a*b,loop, ans);
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	838 }
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	839 \end{lstlisting}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	840
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	841 \begin{table}[htpb]
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	842 \centering
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	843 \begin{tabular}{\|l\|r\|} \hline
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	844 & 実行速度 (s) \\ \hline
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	845 関数呼び出し & 4.85 \\ \hline
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	846 軽量継続 & 3.10 \\ \hline
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	847 \end{tabular}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	848 \caption{関数呼び出しと軽量継続の速度比較}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	849 \label{comp}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	850 \end{table}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	851
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	852 \section{まとめ}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	853 本章では LLVM と Clang を利用したオリジナルの言語のコンパイラの実装を行った. 新しい型や構文の実装方法, オプションの作り方, 最適化の追加と強制の方法について説明を行い, 正しくコンパイルできることを確認した. 重要なのは LLVM IR の改変を行わないことで, これによりバックエンドの処理をそのまま利用することが出来る. 今回実装した言語は C ベースな言語であるため clang を利用したが, 必要に応じて他のフロントエンドを利用すること, 一からフロントエンドを書くことを検討するのも良い.
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	854
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	855 \nocite{CbC2011, LLVMIR, LLVM, clang, repo}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	856 \bibliographystyle{IEEEtran}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	857 \bibliography{IEEEabrv,reference}
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	858
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	859 % that's all folks
8319d82cab07 add files Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> parents: diff changeset	860 \end{document}

Mercurial > hg > Papers > 2016 > kaito-cq

annotate paper.tex @ 2:7cc0be313596