Clangの深みに飛び込むことなく、高レベルの側面を考慮してください。 C ++の重要な機能については考慮しませんが、Clangの出力が入力にどのように関連するかに注意を払いたいと思います。 この小さな関数を使用します。これは、巡回最適化に関する優れた講義から借りたものです。
bool is_sorted(int *a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; }
Clangは最適化を行わず、LLVM IRはもともとCおよびC ++で動作するように設計されていたため、変換は比較的簡単です。 x86-64でClang 6.0.1（または、これはまだリリースされていないため、近いバージョン）を使用します。
コマンドラインは次のとおりです。
clang++ is_sorted.cpp -O0 -S -emit-llvm
つまり、is_sorted.cppファイルをC ++としてコンパイルし、LLVMツールチェーンに次のことを伝えます。最適化せずに、LLVM IRのテキスト表現としてアセンブラーを出力します。 LLVM IRは膨大であり、迅速に表示または解析することはできません。このコードを見る必要がない場合は、バイナリビットコード形式が常に望ましいです。 完全なLLVM IRを以下に示します。部分的に確認します。
ファイルの先頭から始めましょう：
; ModuleID = 'is_sorted.cpp' source_filename = "is_sorted.cpp" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"
セミコロンと行末の間のテキスト全体はコメントです。つまり、最初の行は何もしませんが、LLVMでは、「モジュール」はコンパイル単位であり、コードとデータのコンテナです。 2行目も気にしないでください。 3行目は、コンパイラーによって行われたいくつかの前提条件を説明します。これらはこの記事では役割を果たしませんが、 ここで詳細を読むことができます 。 ターゲット3はgccの遺産であり、もはや必要ありません。
LLVM関数にはオプションの属性があります。
; Function Attrs: noinline nounwind optnone uwtable
それらの一部（これらのような）はフロントエンドでサポートされ、その他は最適化パスを介して後で追加されます。 これらの属性はコードの意味とは関係ありません。ここでは説明しませんが、興味がある場合はここで読むことができます。
そして最後に、私たちの機能：
define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n) #0 {
「Zeroext」は、関数の戻り値（i1、単一ビット整数）をバックエンドのゼロでABIが必要とする幅まで拡張する必要があることを意味します。 次に、「マングルされた」関数名、パラメータのリストが続きます。i32が32ビット変数を定義することを除いて、基本的にC ++コードと同じです。 ＃0は、ファイルの最後にある関数を属性グループに接続します。
最初の基本ユニットは次のとおりです。
entry: %retval = alloca i1, align 1 %a.addr = alloca i32*, align 8 %n.addr = alloca i32, align 4 %i = alloca i32, align 4 store i32* %a, i32** %a.addr, align 8 store i32 %n, i32* %n.addr, align 4 store i32 0, i32* %i, align 4 br label %for.cond
各LLVM命令は、ベースユニット内に配置する必要があります。最初の入力が1つ、最後の出力が1つの命令セットです。 ベースユニットの最後の命令は終了命令でなければなりません。次のベースユニットに「失敗」することは受け入れられません。 各関数には、このブロックへの遷移を実行する先行タスクがない入力ブロックが必要です。 IRを解析するときに、このプロパティと他のプロパティがチェックされます;これらのチェックは、コンパイルプロセス中に「モジュール検証」によって複数回呼び出されることもあります。 パスが無効なIRを生成する場合、検証はデバッグに役立ちます。
このベースブロックの最初の4つの命令は「alloca」です。つまり、スタックメモリを割り当てます。 最初の3つはコンパイル中に暗黙的に作成された変数を作成し、4番目はループ変数です。 この方法で割り当てられた変数には、ロードおよびストア命令を介してのみアクセスできます。 次の3つの命令は3つのスタックスロットを初期化します。a.addrとn.addrは、関数にパラメーターとして渡された値を使用して初期化され、iはゼロに初期化されます。 戻り値を初期化する必要はありません。CおよびC ++で未定義でないコードは、これを処理する必要があります。 最後の命令は、次のベースユニットへの無条件の遷移です（これについてはまだ心配していません。ほとんどの不要な遷移はLLVMバックエンドによって削除されます）。
あなたは尋ねるかもしれません：なぜClangはaとnにスタックスロットを割り当てるのですか？ なぜ彼はこれらの値を直接使用しないのですか？ この関数では、aとnは変わらないため、このような戦略は機能しますが、このケースはオプティマイザーによって考慮され、Calngの能力の範囲外です。 aとnを変更できる場合、それらはメモリ内にある必要があり、SSA値であってはなりません。SSA値は、定義上、プログラムの1つのポイントでのみ値を取ることができます。 メモリセルはSSAの世界外にあり、いつでも変更できます。 これは奇妙に思えるかもしれませんが、そのようなソリューションを使用すると、コンパイラのすべての部分の作業を自然で効率的な方法で編成できます。
Clangは、SSAのすべての要件を満たしているが、ベースユニット間の情報交換がメモリを介して行われているため、退化したSSAコードのジェネレータと考えています。 非縮退コードの生成には注意と分析が必要であり、Clang開発者はコード生成と最適化の責任を分離するためにこれを行うことを拒否しました。 測定結果は表示されませんでしたが、私の理解では、多くのメモリ操作が生成され、ほとんどすぐに、それらのほとんどがオプティマイザーによって削除され、コンパイル時間の大きなオーバーヘッドを招くことなく、
forループの変換方法を検討してください。 一般的には、次のようになります。
for (initializer; condition; modifier) { body }
これは次のようなものに変換されます。
initializer goto COND COND: if (condition) goto BODY else goto EXIT BODY: body modifier goto COND EXIT:
もちろん、このような翻訳はClangに固有のものではなく、CおよびC ++コンパイラーも同様です。
この例では、ループ初期化子は入力ベースユニットに折りたたみます。 次の基本ユニットはループ状態チェックです。
for.cond: ; preds = %for.inc, %entry %0 = load i32, i32* %i, align 4 %1 = load i32, i32* %n.addr, align 4 %sub = sub nsw i32 %1, 1 %cmp = icmp slt i32 %0, %sub br i1 %cmp, label %for.body, label %for.end
また、Clangは、このベースブロックにfor.incまたは入力ベースブロックのいずれかからアクセスできるという便利なコメントを作成します。 このブロックは、メモリからiとnをロードし、nを減らします（nswフラグは、符号オーバーフローが定義されていないC言語プロパティを反映します;このフラグがなければ、LLVMは追加コードのセマンティクスを使用します）、slt（符号がより小さい、より小さい）に署名してから、最終的にfor.bodyまたはfor.endベースブロックに分岐します。
ループ本体への入り口は、for.condブロックからのみ可能です。
for.body: %2 = load i32*, i32** %a.addr, align 8 %3 = load i32, i32* %i, align 4 %idxprom = sext i32 %3 to i64 %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom %4 = load i32, i32* %arrayidx, align 4 %5 = load i32*, i32** %a.addr, align 8 %6 = load i32, i32* %i, align 4 %add = add nsw i32 %6, 1 %idxprom1 = sext i32 %add to i64 %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1 %7 = load i32, i32* %arrayidx2, align 4 %cmp3 = icmp sgt i32 %4, %7 br i1 %cmp3, label %if.then, label %if.end
最初の2行は、SSAレジスタのaとiをロードします。 次に、64ビットに拡張し、アドレスの計算に参加できます。 getelementptrコマンド（または略してgep）は、その気前の良さで知られるLLVMコマンドであり、独自のヘルプセクションもあります。 機械語とは異なり、LLVMはポインターを整数として扱いません。 これにより、エイリアス分析およびその他のメモリ最適化が容易になります。 このコードは、[i]と[i + 1]をロードし、それらを比較して、結果に応じて分岐を実行します。
if.thenブロックは、関数の戻り値のためにスタックスロットに0を保存し、関数の出力ブロックに無条件にジャンプします。
if.then: store i1 false, i1* %retval, align 1 br label %return
elseブロックは簡単です。
if.end: br label %for.inc
また、ループ変数に1を追加するブロックも非常に簡単です。
for.inc: %8 = load i32, i32* %i, align 4 %inc = add nsw i32 %8, 1 store i32 %inc, i32* %i, align 4 br label %for.cond
このコードは、ループ状態のチェックに戻ります。
ループが正常に完了すると、trueを返します。
for.end: store i1 true, i1* %retval, align 1 br label %return
そして最後に、戻り値のスタックスロットにロードしたものがロードされて返されます。
return: %9 = load i1, i1* %retval, align 1 ret i1 %9
関数の最後に特別なものはありません。 この投稿は私が思っていたよりも長くなりました。次の投稿では、この機能のIRレベルを最適化することを検討します。
（Xi WangとAlex Rosenbergに送られた訂正に感謝します）