コンパイラの開発は非常に難しい作業です。 しかし、幸いなことに、LLVM のようなプロジェクトの開発により、この問題の解決策は大幅に簡素化され、XNUMX 人のプログラマでも C に近いパフォーマンスの新しい言語を作成できるようになりました。LLVM の使用は、これが複雑であるという事実によって複雑になります。システムは膨大な量のコードで表され、ドキュメントはほとんどありません。 この欠点を修正するために、今日私たちがその翻訳を公開する資料の著者は、Go で書かれたコードの例を示し、それらが最初にどのようにして Go に翻訳されるかを示す予定です。 次にコンパイラを使用して LLVM IR で 。 Go SSA および LLVM IR コードは、説明をより理解しやすくするために、ここでの説明に関係のないものを削除するためにわずかに編集されています。
最初の例
ここで取り上げる最初の関数は、数値を加算するための単純なメカニズムです。
func myAdd(a, b int) int{
return a + b
}この関数は非常にシンプルで、おそらくこれ以上にシンプルなものはありません。 これは、次の Go SSA コードに変換されます。
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0このビューでは、データ型のヒントが右側に配置され、ほとんどの場合無視できます。
この小さな例では、SSA の一側面の本質をすでに理解できています。 つまり、コードを SSA 形式に変換するとき、各式はそれを構成する最も基本的な部分に分割されます。 私たちの場合、コマンドは return a + bは、実際には、XNUMX つの数値を加算し、結果を返すという XNUMX つの操作を表します。
さらに、ここではプログラムの基本ブロックを確認できます。このコードには、エントリ ブロックというブロックが XNUMX つだけあります。 ブロックについては以下で詳しく説明します。
Go SSA コードは LLVM IR に簡単に変換できます。
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
ここでは異なる構文構造が使用されていますが、関数の構造は基本的に変わっていないことがわかります。 LLVM IR コードは、C に似た Go SSA コードよりも少し強力です。ここでは、関数宣言で、最初に関数が返すデータ型の説明があり、引数の型が引数名の前に示されます。 さらに、IR 解析を簡素化するために、グローバル エンティティの名前の前に記号が付けられます。 @、ローカル名の前に記号があります % (関数はグローバル エンティティともみなされます)。
このコードで注意すべき点の XNUMX つは、Go の型表現の決定です。 intは、コンパイラとコンパイルのターゲットに応じて 32 ビット値または 64 ビット値として表すことができ、LLVM が IR コードを生成するときに受け入れられます。 これは、多くの人が考えているように、LLVM IR コードがプラットフォームに依存しない多くの理由の XNUMX つです。 あるプラットフォーム用に作成されたこのようなコードは、(この問題を解決するのに適している場合を除き) 別のプラットフォーム用に単純に取得してコンパイルすることはできません。 ).
注目に値するもう XNUMX つの興味深い点は、 i64 は符号付き整数ではありません。数値の符号を表すという点では中立です。 命令に応じて、符号付き数値と符号なし数値の両方を表すことができます。 加算演算の表現の場合、これは問題ではないため、符号付きの数値と符号なしの数値を扱うことに違いはありません。 ここで、C 言語では、符号付き整数変数をオーバーフローすると未定義の動作が発生するため、Clang フロントエンドが操作にフラグを追加することに注意してください。 nsw (符号付きラップなし)。これは、加算が決してオーバーフローしないと仮定できることを LLVM に伝えます。
これは一部の最適化にとって重要な場合があります。 たとえば、XNUMX つの値を加算すると、 i16 32 ビット プラットフォーム (32 ビット レジスタを使用) では、加算後に範囲内にとどまるために符号拡張演算が必要です i16。 このため、多くの場合、マシン レジスタ サイズに基づいて整数演算を実行する方が効率的です。
この IR コードで次に何が起こるかは、現時点では私たちにとって特に興味深いことではありません。 コードは最適化され (ただし、この例のような単純な例の場合は何も最適化されません)、マシンコードに変換されます。
XNUMX番目の例
次に見る例はもう少し複雑です。 つまり、整数のスライスを合計する関数について話しています。
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}このコードは、次の Go SSA コードに変換されます。
func sum(numbers []int) int:
entry:
jump for.loop
for.loop:
t0 = phi [entry: 0:int, for.body: t6] #n int
t1 = phi [entry: 0:int, for.body: t7] #i int
t2 = len(numbers) int
t3 = t1 < t2 bool
if t3 goto for.body else for.done
for.body:
t4 = &numbers[t1] *int
t5 = *t4 int
t6 = t0 + t5 int
t7 = t1 + 1:int int
jump for.loop
for.done:
return t0ここでは、SSA フォームでコードを表現するための一般的な構造をさらに確認できます。 おそらく、このコードの最も明白な特徴は、構造化されたフロー制御コマンドがないという事実です。 計算の流れを制御するには、条件付きジャンプと無条件ジャンプ、そしてこのコマンドをフローを制御するコマンドとして考えるとリターン コマンドしかありません。
実際、ここでは、プログラムが (C 言語ファミリーのように) 中括弧を使用してブロックに分割されていないという事実に注目することができます。 アセンブリ言語を思わせるラベルによって分割され、基本ブロックの形式で表示されます。 SSAでは、基本ブロックは、ラベルで始まり、次のような基本ブロック完了命令で終わる連続したコードシーケンスとして定義されます- return и jump.
このコードのもう XNUMX つの興味深い詳細は、次の命令で表されます。 phi。 説明はかなり特殊なので、理解するのに時間がかかるかもしれません。 覚えておいてください、それを 静的単一割り当ての略です。 これはコンパイラによって使用されるコードの中間表現であり、各変数には XNUMX 回だけ値が割り当てられます。 これは、関数のような単純な関数を表現するのに最適です myAdd上に示したものですが、このセクションで説明する関数のようなより複雑な関数には適していません。 sum。 特に、変数はループの実行中に変更されます。 i и n.
SSA は、いわゆる命令を使用して変数値を割り当てる制限を回避します phi （その名前はギリシャ語のアルファベットから取られています）。 実際のところ、C などの言語でコードの SSA 表現を生成するには、いくつかのトリックに頼る必要があります。 この命令を呼び出した結果は、変数の現在値です (i または n)、基本ブロックのリストがパラメータとして使用されます。 たとえば、次の命令について考えてみましょう。
t0 = phi [entry: 0:int, for.body: t6] #n
その意味は次のとおりです: 前の基本ブロックがブロックだった場合 entry (入力)、その後 t0 定数です 0、そして前の基本ブロックが for.body、その後、値を取得する必要があります t6 このブロックから。 これはすべて非常に謎に思えるかもしれませんが、このメカニズムが SSA を機能させるものです。 人間の観点から見ると、これらすべてがコードを理解するのを難しくしていますが、各値が XNUMX 回だけ割り当てられるという事実により、多くの最適化がはるかに簡単になります。
独自のコンパイラを作成する場合、通常はこの種の処理を行う必要がないことに注意してください。 Clang でもこれらすべての命令を生成できるわけではありません phiという仕組みを使っています。 alloca (これは通常のローカル変数の操作に似ています)。 次に、LLVM 最適化パスを実行するときに、 、 説明書 alloca SSA形式に変換されます。 ただし、TinyGo は Go SSA から入力を受け取ります。Go SSA は都合よくすでに SSA 形式に変換されています。
検討中の中間コードのフラグメントのもう XNUMX つの革新は、インデックスによるスライス要素へのアクセスが、アドレスを計算する操作と結果として得られるポインターを逆参照する操作の形式で表現されることです。 ここでは、IR コードに定数を直接追加していることがわかります (例: 1:int）。 関数を使用した例では myAdd これは使用されていません。 これらの機能は説明したので、このコードが LLVM IR 形式に変換されるとどうなるかを見てみましょう。
define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
%2 = icmp slt i64 %1, %len
br i1 %2, label %for.body, label %for.done
for.body: ; preds = %for.loop
%3 = getelementptr i64, i64* %ptr, i64 %1
%4 = load i64, i64* %3
%5 = add i64 %0, %4
%6 = add i64 %1, 1
br label %for.loop
for.done: ; preds = %for.loop
ret i64 %0
}
ここでも、以前と同様に、他の構文構造を含む同じ構造が確認できます。 たとえば、通話では phi 値とラベルが交換されました。 ただし、ここで特に注意すべき点があります。
まず、ここではまったく異なる関数シグネチャを確認できます。 LLVM はスライスをサポートしていないため、最適化として、この中間コードを生成した TinyGo コンパイラーは、このデータ構造の記述を複数の部分に分割しました。 XNUMX つのスライス要素 (ptr, len и cap) は構造体 (struct) として扱われますが、これらを XNUMX つの別個のエンティティとして表すことで、いくつかの最適化が可能になります。 他のコンパイラは、ターゲット プラットフォームの関数の呼び出し規則に応じて、他の方法でスライスを表す場合があります。
このコードのもう XNUMX つの興味深い特徴は、次の命令を使用していることです。 getelementptr (GEP と略されることがよくあります)。
この命令はポインターを操作し、スライス要素へのポインターを取得するために使用されます。 たとえば、C で記述された次のコードと比較してみましょう。
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}または、これと同等の次のコードを使用します。
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
ここで最も重要なことは、指示が getelementptr 逆参照操作は実行しません。 既存のポインターに基づいて新しいポインターを計算するだけです。 指示として受け取ることもできる mul и add ハードウェアレベルで。 GEP の手順について詳しくは、こちらをご覧ください。 .
この中間コードのもう XNUMX つの興味深い特徴は、次の命令を使用していることです。 icmp。 これは、整数比較を実装するために使用される汎用命令です。 この命令の実行結果は常に次の型の値になります。 i1 — 論理値。 この場合、キーワードを使用して比較が行われます。 slt (符号付き小なり)、以前に型で表された XNUMX つの数値を比較しているためです。 int。 XNUMX つの符号なし整数を比較する場合は、次のようにします。 icmp、比較に使用されるキーワードは次のようになります。 ult。 浮動小数点数を比較するには、別の命令が使用されます。 fcmp、同様の方法で機能します。
結果
この資料では、LLVM IR の最も重要な機能を説明したと思います。 もちろん、ここには他にもたくさんあります。 特に、コードの中間表現には、IR では表現できない、コンパイラーに既知のコードの特定の機能を最適化パスで考慮できるようにする多くの注釈が含まれる場合があります。 たとえば、これはフラグです inbounds GEP 命令またはフラグ nsw и nuw、説明書に追加できます add。 キーワードも同様です private、マークを付けた関数が現在のコンパイル単位の外部から参照されないことをオプティマイザーに示します。 これにより、未使用の引数を削除するなど、多くの興味深いプロシージャ間の最適化が可能になります。
LLVM について詳しくは、以下を参照してください。 独自の LLVM ベースのコンパイラを開発するときによく参照します。 ここ では、非常に単純な言語のコンパイラの開発について説明します。 これらの情報源はどちらも、独自のコンパイラを作成するときに役立ちます。
親愛なる読者！ LLVM を使用していますか?
出所： habr.com