kakts-log

programming について調べたことを整理していきます

Goコンパイラによるコンパイル処理について整理

概要

Goのコンパイラにおいて、コンパイル時にいくつかのフェーズに分かれており、各フェーズについてざっと概要を整理します。

github.com

Goコンパイラによるコンパイルでは、主に下記のようなフェーズをたどります。 - 字句解析 - 構文解析 - 型チェック - IR(中間表現)の生成 - IRの生成 - SSA(静的単一代入)形式への変換 - 最適化 - マシンコードの生成

Goコンパイルのフェーズ

字句解析と構文解析

  • cmd/compile/internal/syntax

github.com

コンパイルの最初のフェーズでは、ソースコードトークナイズ(字句解析)とパース(構文解析)され、それぞれのソースファイルに対してシンタックスツリーが構成されます。

シンタックスツリーはそれぞれのソースファイルを正確に表現したもので、ノードはソースのさまざまな表現(式・宣言・文など)に対応しています。

また、シンタックスツリーには位置情報も含まれており、エラーリポートやデバッグ情報の生成に使用されます。

型チェック

  • cmd/compile/internal/types2

github.com

type2 パッケージはgo/typesgo/astの代わりに構文パッケージのASTを使用するように移植したものです。

IR(中間表現)の生成 (”noding”)

  • cmd/compile/internal/types (compiler types)
  • cmd/compile/internal/ir (compiler AST)
  • cmd/compile/internal/noder (create compiler AST)

ここでは、構文解析と型チェックの結果を、コンパイラが理解できる中間表現(IR)に変換するプロセスを扱います。

Goコンパイラmiddle-end は自身のAST定義とCで書かれた時代から引き継いだGoの型の表現を使います。

そのコードの全ては、型チェック後の次のステップがその構文とtype2での表現を 中間表現と型に変換します。

このプロセスは “Noding” と呼ばれます。

Noding ではUnified IRと呼ばれるプロセスを用います。これはステップ2で型チェックが完了したコードをシリアライズしたものを利用して、Nodeを構成します。

Unified IRはパッケージのimport/exportやインライニングに関わります。

IRに対する最適化 (middle-end)

  • cmd/compile/internal/deadcode (dead code elimination)
  • cmd/compile/internal/inline (function call inlining)
  • cmd/compile/internal/devirtualize (devirtualization of known interface method calls)
  • cmd/compile/internal/escape (escape analysis)

中間表現に対して、いくつかの最適化プロセスが実施されます。

  • デッドコード削除
  • 早期の devirtualizeation
  • 関数呼び出しのインライニング
  • エスケース解析

IRに対する最終処理(Wark)

中間表現に対する最終的な処理は Walk と呼ばれ、2つの目的があります

  1. 複雑な文を個々のより単純な文に分解し、一時変数を導入し、評価の順序を尊重します。このステップをorder とも呼ばれます。
  2. 高レベルのGo構造をよりプリミティブな形式にde-sugaring します。 例えば switch 文はバイナリ検索やジャンプテーブルに変換したり、マップやチャネルの場合はランタイム呼び出しに置き換えられます。

SSA(静的単一代入)形式への変換

SSA形式 は、コンパイラの設計における中間表現(IR)の一つです。

各変数が一度のみ代入されるように定義されたものです。

SSAを利用することにより、コンパイラ最適化アルゴリズムを実現したり、改善をすることができます。

このフェーズでは中間表現は静的単一代入(SSA)形式に変換されます。これは低レベルの中間表現で、最適化を実装しやすくし、最終的に機械語を生成する特性を持ちます。

この変換の過程において、関数intrinsicsが適用されます。これはコンパイラがケースバイケースで十分に最適化されたコードに置き換えるように実装された特殊な関数となります。

ASTからSSAへの変換の間において、特定のノードもよりシンプルな低レイヤーコンポーネントに変化されます。これによって、コンパイラの残りの部分が処理できるようになります。

例えば、copyの組み込み関数はメモリ移動に置き換えられrangeループはforループに書き換えられます。

これらの一部は現在歴史的な理由からSSAへの変換前に行われていますが、将来的には全て cmd/compile/internal/配下に移る予定だそうです。

その後、特定のマシンに依存しないパスとルールが適用されます。これらは特定のコンピュータアーキテクチャに関係せず、全てのGOARCH バリアアントで実行されます。

これらのパスにはデッドコード除去、不要なnilチェックの削除、未使用のブランチの削除が含まれます。

ジェネリックな書き換えルールは主に式に関するもので、いくつかの式を定数値に置き換えたり、乗算や浮動小数点演算を最適化したりします。

マシンコードの生成

  • cmd/compile/internal/ssa (SSAへの変換とアーキテクチャに依存したパス)
  • cmd/internal/obj (マシンコードの生成)

コンパイラのマシン依存のフェーズは”低レベル化”パスから始まり、これは汎用的な値をマシン固有のバリアントに書き換えます

この低レベル化パスは全てのマシン固有の書き換えルールを実施するため、多くの最適化も適用されます。

SSA形式のコードが低レベル化され、ターゲットのアーキテクチャに特化した後、最終的なコード最適化パスが実行されます。

これには、さらにもう一度デッドコードの除去や、値を実際の使用箇所に近づけたり、読み取られないローカル変数の削除や、レジスタの割り当てが含まれます。

このステップの一部として行われるその他の重要な作業には、スタックフレームのレイアウト(ローカル変数にスタックオフセットを割り当てること)と、各GCのセーフポイントにおいて、どのスタック上のポインタが利用されているかを計算するポインタのliveness解析が含まれます。

SSA形式の生成フェーズの終わりには、Go関数はobj.Prog 命令に変換されています。

これらはアセンブラ(cmd/internal/obj ) に渡され、マシンコードに変換されて最終的なオブジェクトファイルが出力されます。

オブジェクトファイルには、リフレクトデータや、エクスポートデータ、デバッグ情報も含まれます。

さいごに

ざっとそれぞれのフェーズについて概要を説明すると以上となります。 最適化処理についてはまた別の機会に詳しく整理できたらと思います。