This repository has been archived by the owner on Nov 23, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.tex
168 lines (134 loc) · 6.72 KB
/
main.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
\documentclass[uplatex,a4paper]{jsarticle}
\usepackage[dvipdfmx]{graphicx,xcolor}
\usepackage[T1]{fontenc}
\usepackage{otf}
\usepackage{lmodern}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{siunitx}
\usepackage{float}
\usepackage{aliascnt}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage[dvipdfmx,hidelinks,hypertexnames=false]{hyperref}
\usepackage{listings}
\usepackage{subfiles}
\usepackage{caption}
\usepackage{cleveref}
\usepackage{autonum}
\usepackage{morewrites}
\usepackage[pdf,tmpdir]{graphviz}
\graphicspath{{figures/}}
\mathtoolsset{showmanualtags}
\lstset{
basicstyle={\ttfamily},
identifierstyle={\small},
commentstyle={\smallitshape},
keywordstyle={\small\bfseries},
ndkeywordstyle={\small},
stringstyle={\small\ttfamily},
frame={tb},
breaklines=true,
columns=[l]{fullflexible},
numbers=left,
xrightmargin=0zw,
xleftmargin=3zw,
numberstyle={\scriptsize},
stepnumber=1,
numbersep=1zw,
lineskip=-1ex
}
\newcounter{equationset}
\newcommand{\equationset}[1]{
\refstepcounter{equationset}
\noindent\makebox[\linewidth]{\theequationset: #1}
}
\renewcommand{\listfigurename}{\subsection{図一覧}}
\renewcommand{\listtablename}{\subsection{表一覧}}
\renewcommand{\listalgorithmname}{\subsection{アルゴリズム一覧}}
\renewcommand{\lstlistlistingname}{\subsection{コード一覧}}
\renewcommand{\appendixname}{}
\renewcommand{\refname}{\section{参考文献}}
\renewcommand{\figurename}{図}
\renewcommand{\tablename}{表}
\renewcommand{\theequationset}{式~\arabic{equationset}}
\renewcommand{\lstlistingname}{コード}
\makeatletter
\renewcommand{\ALG@name}{アルゴリズム}
\makeatother
\crefname{table}{表}{表}
\crefname{figure}{図}{図}
\crefname{algorithm}{アルゴリズム}{アルゴリズム}
\crefname{listing}{コード}{コード}
\crefformat{section}{#1#2節#3}
\crefformat{enumi}{#1#2.#3}
\usepackage{here}
\title{cccコンパイラのバックエンド}
\author{\href{https://keybase.io/coorde}{\texttt{coord\_e}}}
\date{2019年12月23日}
\begin{document}
\maketitle
%% \thispagestyle{empty}
%% \clearpage
% 本文
\pagenumbering{arabic}
\setcounter{page}{1}
この記事は言語実装 Advent Calendar 2019\footnote{\url{https://qiita.com/advent-calendar/2019/lang_dev}}の23日目です。
\section{はじめに}
実は、この記事の大半の文章は以前に別の目的\footnote{\url{https://twitter.com/coord_e/status/1203620846259933186?s=20}}で執筆したものです。
そういえばcccについて記事を書いていないな、ということで、少し内容を変更しつつ体裁を整えて公開することにしました。
なお、ブログやスライドなどで散々「セルフホストする」「\texttt{gcc -O1}に勝つ」と豪語しておりましたが、そのどちらも達成できていません。残念。
この記事の\LaTeX ソースはGitHubに公開しています。\footnote{\url{https://github.com/coord-e/article-ccc-backend}}
また、誤字や誤謬を発見された方は\href{https://twitter.com/coord_e}{\texttt{@coord\_e}}までご連絡いただくかリポジトリにIssueやPull Requestを送ってくださると幸いです。
\section {概要}
\label{ccc_abstract}
\textbf{ccc}は、自分がセキュリティ・キャンプ2019\cite{seccamp19}に参加した際に開発したコンパイラだ。
C11のサブセットをコンパイルする事ができ、暗黙の型変換や初期化子、宣言子に代表される複雑な言語機能を規格に忠実に実装している。
さて、cccは効率の良いコードに効率よくコンパイルすることをテーマに開発を行った。
そのテーマのもと、出力コードの効率を高めるためにcccに実装した技術についてこの記事では説明する。
最後にベンチマークの結果を示し、実装の効果を確かめる。
\section{cccコンパイラの構成}
\subfile{sections/architecture}
\clearpage
\section{IR}
\label{ccc_ir}
\subfile{sections/ir}
\clearpage
\section{ターゲット固有IRへの変換}
\label{archconv}
\subfile{sections/target}
\clearpage
\section{最適化}
\label{optimization}
\subfile{sections/optimization}
\clearpage
\section{レジスタ割り当て}
\label{ccc_regalloc}
\subfile{sections/reg_alloc}
\clearpage
\section{評価}
\label{ccc_performance}
\subfile{sections/evaluation}
\section{考察と展望}
当然ながらcccはどのベンチマークにおいてもgccよりも速くコンパイルできている。
cccの方が高速なコードを出力しているケースにおいても、最適化を行っていない\texttt{gcc -O0}と比べて最適化を行ったcccの方が高速にコンパイルできている。
効率よくコンパイルするという目標はよく達成できていると思う。\footnote{自己満足の話であり、gccより効率が良いと言いたいわけではない。}
その一方で実行時間については、ほとんどのベンチマークで\texttt{gcc -O0}より遅いという結果になった。しかしmem2regがpiで\texttt{gcc -O0}より高速なコードを出力できている。
これは14queenとsortが配列に対する操作が基本となるベンチマークであるのに対し、piはスカラ変数に対する操作が中心であることに起因すると考えている。
配列操作はどうしてもメモリアクセスが必要となってしまうが、スカラ変数に対する操作はmem2regでレジスタ操作に置き換えることができる。そのためpiではmem2reg最適化の効果が強く出たのではないかと考えられる。
また、\cref{ccc_bench_loc}を見ると実行時間が遅い項目は出力コード行数も多くなっていることがわかる。
したがって、cccをより高性能なコンパイラにするために、今後は出力命令数を減らすためにIR命令セットの再検討を行いたい。
また、まだ実装していないloop unwindingや末尾再帰などの最適化パスも実装し、最終的に\texttt{gcc -O1}に主要なベンチマークで勝利できるコンパイラを目指す。
\section{結論}
本記事ではcccコンパイラの実装について紹介した。
効率の良いコードに効率よくコンパイルするという目標を念頭に、cccのバックエンドにおける最適化やレジスタ割り当てのアルゴリズム、および実装上の工夫について説明した。
最後にベンチマークを示し、本記事で説明したアルゴリズムの実装によってcccの出力コードの効率が向上することを確かめた。
\clearpage
\appendix
\section{図表目次}
\listoffigures
\listofalgorithms
\listoftables
\bibliography{references}
\bibliographystyle{junsrt}
\end{document}