[新人エンジニアが作る自作OS]コンパイラの仕組み

本投稿、[新卒が作る自作OS]は、我々が自作OSを作るにあたり、詰まったところや、備忘録的に残しておきたいところなどをまとめておこうという趣旨の投稿です。

以前「[新卒が作る自作OS]ソースコードの分割とmakeによる自動コンパイル」という記事で、分割コンパイルやコンパイルの自動化について触れました。今回は「そもそもコンパイルとは何か」という疑問に焦点を当て、コンパイルの仕組みについてまとめました。

この記事ではC言語を例に挙げて解説します。

プログラミング言語が機械語になるまで

コンパイラ型のプログラミング言語が機械語に変換されるまでには以下の過程で処理が行われます。本章ではこれらの処理それぞれについて説明します。以下の図が今回解説する大まかな流れになります。

1. コンパイル
2. アセンブル
3. リンク

コンパイル

高級言語で記述されたソースコードを低級言語であるアセンブリ言語へ変換します。この動作をコンパイル、コンパイルするためのソフトウェアをコンパイラと呼びます。コンパイラはプログラミング言語ごとに異なります。

コンパイルの処理の流れについては次章で詳しく説明します。

アセンブル

コンパイルで生成されたアセンブリ言語を機械語に変換します。コンピュータは物理的には電子回路で構成されているため、認識できるのは電圧の高低のみです。そのためコンピュータに命令するには電圧の高低を0と1で表現できる機械語に変換しなければなりません。

アセンブリ言語を翻訳することをアセンブル、翻訳するソフトウェアをアセンブラと呼びます。多くのコンパイラはアセンブラを含んでいるため、プログラマは普段これらの手順を意識する必要はありません。低級言語であるアセンブリ言語の命令は機械語と1対1で対応しています。そのため、多くのコンパイラは高級言語を直接機械語に変換するプログラムを記述せずアセンブラを使うことで開発の手間を減らしています。

リンク

大規模なソフトウェアを開発する場合、通常ソースコードは一つのファイルではなく複数のファイルに分割された状態で記述されます。そのため、複数のソースコードを一つにまとめる作業が必要です。それぞれのソースコードをアセンブルした中間コードを一つの実行ファイルにまとめることをリンク、リンクを行うソフトウェアをリンカと呼びます。通常リンカもコンパイラに含まれているので、多くのコンパイラではコマンド一つで実行ファイルが生成されます。

コンパイル

ではプログラムが機械語に変換される手順のうちの、コンパイルの部分について見ていきましょう。アセンブリ言語の命令は機械語と1対1で対応しているため変換が容易ですが、高水準言語はそうはいきません。プログラマにとっての可読性を重視しているため、コンピュータにとっては理解しにくいのです。

コンパイラは以下の手順で高水準言語をアセンブリ言語に変換します。

1. 字句解析
2. 構文解析
3. 意味解析
4. 中間コード作成
5. レジスタ割り付け
6. オブジェクト最適化
7. コード生成

字句解析

読み込まれたソースコードに対し、最初に行うのが字句解析です。それぞれの命令の意味を理解するために、字句（単語）ごとにソースコードを分割します。そしてそれぞれの字句の種別を識別します。字句の種別には以下のような分類が挙げられます。

• 変数、関数名
• 数値
• 演算子
• 区切り記号

例えば以下のようなソースコード1行分を字句解析すると、下記の表のように分けることができます。

i = a + b * 2;

構文解析

続いて、字句解析の結果を元に文の構造上の関係を解析します。これを構文解析と呼びます。先程の例のような簡単な演算は人間であれば一瞬で計算できますが、コンピュータは構造の理解から始める必要があります。多くの場合、演算子の構文と優先順位に基づいて構文木と呼ばれる木構造で表現されます。例えば先程の文であれば以下のような構文木に表せます。

意味解析

構文木を作ったら、それぞれの字句の意味を解釈します。これが意味解析です。例えば、演算子はその項の型によって処理が異なります。この場合は各項の型を参照し記号や式の意味を明確化します。これらの情報を記録したものを記号表と呼びます。

中間コード作成

ここまでで用意できた高級言語のソースコードも構文木も人間にはわかりやすいですが、コンピュータにとっては理解しにくいものです。そのため、コンピュータが理解できる機械語の中間コードを作成します。この中間コードと次に述べるレジスタとの対応によってアセンブリ言語へ変換することができます。

レジスタ割り付け

CPUが演算を行う際、一時的なデータの保存領域としてレジスタを使用します。レジスタはメモリと比べて高速低容量な記憶装置です。以下が演算処理の簡単な流れです。

1. メモリからデータをレジスタへ取り出し、
2. レジスタのデータをCPUが読み込み、
3. CPUによる演算処理を行い、
4. その結果がレジスタへ保存されるので、
5. メモリに格納します。

これを実現するためにはどのデータをどのレジスタへ保存するのかを決める必要があります。これがレジスタ割り付けです。

オブジェクト最適化

コンピュータの命令はその内容によって処理速度が異なります。命令の実行順序によっては待ち時間が長くなり、実行速度が遅くなります。これを改善するために、リソースを効率よく利用し実行速度を早めるためにオブジェクトプログラムを変換します。これをオブジェクト最適化と呼びます。厳密な意味での「最適」すなわち最も適したオブジェクトプログラムとなるとは限りませんが、最適化を目指した変換を行うという意味でこの呼称が使われます。

コード生成

最後にこれらの情報を元にアセンブリ言語に変換します。コード生成処理によって出力されたアセンブリ言語をアセンブルすることでプログラミング言語が機械語に変換されます。それらをリンクすることで、コンピュータが処理できる実行ファイルが生成されます。

上記の手順は代表的なものであり、全てのコンパイラがこの順序で処理するとは限りません。いくつかの処理をまとめて行ったり、オブジェクト最適化を複数回行う場合もあります。

インタプリタとJITコンパイル

インタプリタ

高級言語の中にはコンパイルを行わずに実行時にソースコードを解釈するインタプリタ型の言語が存在します。JavaやPython、Rubyなどが代表的なインタプリタ型の言語です。

インタプリタ型の言語は実行の度にインタプリタによってソースコードが翻訳されてその場で実行されます。そのため、実行速度はコンパイラ型の言語には劣ります。しかし、この方式によるメリットも存在します。それは修正が容易である点と、命令アーキテクチャに依存しない点です。

コンパイラ型の言語はプログラムの実行速度は速いですが、ソースコードを修正する度にこれまでに説明したコンパイル処理を行う必要があります。これに対し、インタプリタ型の言語はコンパイルが不要であるため修正後即座に実行することが可能です。このような開発の手軽さがメリットの一つです。

もう一つのメリットは命令アーキテクチャに依存しないことです。コンパイルとアセンブルによって出力される機械語は命令アーキテクチャによって異なります。実行する命令アーキテクチャに依存するので別の命令アーキテクチャで動作させることはできません。それに対しインタプリタ型はインタプリタがその場で命令アーキテクチャに合わせた変換を行うのでアーキテクチャに依存しません。インタプリタさえ用意していればどこでも利用することが可能です。

JITコンパイル

インタプリタの普及に伴い、処理速度の改善の要求が増えました。これを解決するのがJIT（Just In Time）コンパイルです。JITコンパイルはプログラム中で繰り返し行われる処理を実行中にコンパイルする仕組みです。一つのプログラムの中で、実行頻度の高い部分のみコンパイルし処理速度を高めます。これにより、コンパイル型には劣るものの、通常のインタプリタ型よりも高速でアーキテクチャに依存しないプログラムを開発することが可能になります。

まとめ

本記事ではコンパイルの仕組みとインタプリタについてまとめました。コンパイルの処理の流れは以下の図のようになります。

コンパイルの仕組みを知ることで、Makefileの内容の理解が深まりました。

最後までお読みいただきありがとうございます。