Explore "Full-Stack" in depth!

情報系の専門学校で、今は機械学習に的を絞って学習中。プログラミングを趣味でやりつつ、IT系のあらゆる知識と技術を身に付けるべく奮闘中。

Go Compilerの実装を読む2(Readmeを読んでgcの概観をする編)

目次

概要

Go Compilerの実装を読もう第二弾。

今回は cmd/compileに記載された、
Introduction to the Go compilerの翻訳を行います。

私と同じくGoの実装を読みたい、
コンパイラの勉強をしたい人はこの内容を読むことをおすすめします。

ライセンス

Copyright (c) 2009 The Go Authors. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

   * Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
   * Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following disclaimer
in the documentation and/or other materials provided with the
distribution.
   * Neither the name of Google Inc. nor the names of its
contributors may be used to endorse or promote products derived from
this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

ここから cmd/compile の翻訳を行いますが、
長いので引用文は使いません。

ここから下の文章は基本的に訳文だと思ってください。

Introduction to the Go compiler

cmd/compileはGo Compiler(以後gc)を形成する主要なパッケージを含んでいます。
gcは論理的に 4フェイズに分割 する事ができます。
以下簡単にパッケージリストを説明していきます。

貴方はコンパイラについて参照している(調べている)時、
フロントエンドバックエンド という単語を聞いた事があるかもしれません。
大まかに話すと、
これらの単語は先程話した4フェイズのうち、
最初の2つと最後の2つに分割されます。

3つ目の単語 ミドルエンド はしばしば2フェイズ目に起こる事・その仕事を示しています。

ここで気をつけてほしいことは、
go/* パッケージ群、例えば go/parsergo/typesコンパイラと関係ない という事です。
C言語によって書かれた初期のコンパイラの時から、
go/*パッケージは gofmtvet のようなツールをGoで作れるように開発されてきたものです。

わかりやすくするために、
gcという表記は Go Compilerを示し、
GCと表記した場合には ガベージコレクション を示します。

Parsing

cmd/compile/internal/syntax (字句解析器,構文解析器、構文木等)

コンパイルの第1段階は、
- ソースコードトークン化(字句解析) - パース(構文解析) - 各プログラムで構文木を構成

することになります。

構文木は各ソースファイルを 正確に表現するものです。
定義・宣言 等様々な要素に対応する
ノードを持っています。

構文木デバッグ情報の生成・エラー情報の報告に使われる、
位置情報も併せ持っています。

Type-checking and AST Transformations

cmd/compile/internal/gc (コンパイラASTの生成、型チェック、ASTへの変換)

gcパッケージは C言語で書かれていたときから使い回され続けている
ASTの定義を含んでいます。
このパッケージ内のコードは全てASTの定義について書かれており、
gcパッケージの責務はsyntaxパッケージの構文木コンパイラAST表現 に変換することです。
この段階は将来的にリファクタリング対象になるかもしれません。

その後ASTは型をチェックされます。
まずは名前解決と型推論が行われます。
どのオブジェクト( OOPにおけるオブジェクトではない値という意味だと思う) がどの識別子に属していて、
各式がどの型を持っているかということを決定します。
型チェックだけでなく他にも、
declared and not used チェックや、
関数が終了したかどうかの判定等を行います。

ASTで行われる特定の変換も存在します。
算術加算ノードによって分割した文字列を結合するなど、
いくつかのノードは型情報に基づいて最適化されます。

その他の例としては、
デッドコードの削除、
関数呼び出しのインライン化
エスケープの解析等 があります。

Generic SSA

cmd/compile/internal/gc (SSAへの変換)
cmd/compile/internal/ssa

このフェイズでは、
ASTを Static Single Assignment(SSA)形式に変換します。
最適化の実装と、機械語の生成を簡単に行えるようにする
低レベルな中間表現です。

( SSAについてはここ )

SSA形式への変換時、
Ffunction intrinsics(後述)が適用されます。
いくつかの特別な関数を対象に、
ケースバイケースで、高度に最適化された機械語に置き換えるような最適化手法のことです。

特定のノードはASTからSSA形式に変換される時、
よりシンプルなコンポーネントに置き換えられ、
コンパイラの残りがそれらを扱います。

例えば、
組み込み関数の copy() は、
メモリ移動(コピーではなく再割当て)に置き換えられます。
また、 range ループはforループに書き直されます。

これらのうちいくつは現在SSA形式に変換する前に発生します
歴史的な理由によるものですが、
将来的には全てをSSA形式への変換時に発生するようにします。

そして、
マシンに依存しない一連のパス・ルールが適用されます。
単一のマシンアーキテクチャによるものではないため、
GOARCHに属する全てのアーキテクチャで同様に動作します。

一般的な最適化の例には、 デッドコードの削除、不必要なnilチェックの除去、使用されないブランチの除去等が挙げられます。
これら置き換えは、基本的に式に関連しています。
一部の式を 定数に置き換え したり、
乗算と浮動小数点演算を最適化 したり等です。

Generating machine code

cmd/compile/internal/ssa (SSA形式の変換・アーキテクチャ依存の最適化)
cmd/internal/obj (機械語の生成)

lower pass から始まるマシン依存のフェーズです。
一般的な値をマシン固有のものに書き換えたりします。
例えば、
amd64でメモリオペランドが可能なために、
多くのロード/ストア命令を組み合わせる等です。

lower pass では全てのマシン依存の置き換え規則が実行されるため、
現在も多くの最適化が適用されている事を知っておいてください。

SSA形式が 低く なり、対象のアーキテクチャ固有のものになると、
最後のコード最適化パス が実行されます。
これは 先程とは異なるデッドコード削除
用途に即した値の変換
決してロードされないローカル変数の削除
そして レジスタ割り当て が含まれます。

このステップに含まれるその他重要な仕事としては、
スタックフレームのレイアウト があります。
ローカル変数へのスタックのオフセットを定め、
ポインター"生存" を解析し、
GCのセーフポイントで、
スタックポインタが生存しているかどうかを計算します。

SSA生成フェーズの終わりに、
Goの機能の一つによって 一連の obj.Prog 命令に変換されます。
アセンブラ( cmd/internal/obj )を通過して、
マシンコードに変換し、最終的なオブジェクトファイルを出力します。

このオブジェクトファイルには
参照するデータ・出力するデータ・デバッグ情報が含まれています。


総評

Go Compilerの実装の大まかな流れがつかめる内容になっていました。
次回の Introduction to the Go compiler's SSA backend を読んだ後、
実際にコードリーディングを深めていきたいと思います。

コンパイラの動作の概観が出来たという意味で、
この文章の翻訳には意味がありました。