MergeFunctions パス、その仕組み¶

はじめに ¶

コードには、等しい関数、または IR レベルでは等しくないが（例：2の乗算と「shl 1」）、まったく同じことを行う関数が含まれている場合があります。これは、主にテンプレートの使用と自動コードジェネレーターが原因で発生する可能性があります。ただし、ユーザー自身が同じことを2回書くこともあります :-)

このパスの主な目的は、このような関数を認識してマージすることです。

このドキュメントは、パスのコメントの拡張であり、パスのロジックを説明します。関数を比較するために使用されるアルゴリズムを説明し、モジュールを有効な状態に保つために等しい関数を正しく結合する方法を説明します。

資料はトップダウン形式で提供されているため、読者は高レベルのアイデアからパスの学習を開始し、低レベルのアルゴリズムの詳細で終わることができます。これにより、ソースを読む準備ができます。

主な目標は、アルゴリズム、ロジック、および概念をここで説明することです。ソースコードを読みたくないが、パスのアルゴリズムを理解したい場合は、このドキュメントが適しています。著者は、ソースコードを繰り返さないようにし、小さなコード変更後にこのドキュメントを更新する必要性を避けるために、一般的なケースのみを対象としています。

このドキュメントを理解するために何を知っておくべきですか？¶

読者は、一般的なコンパイルエンジニアリングの原則と LLVM コードの基本に精通している必要があります。この記事では、読者はSingle Static Assignmentの概念に精通しており、IR構造を理解していることを前提としています。

「モジュール」、「関数」、「基本ブロック」、「ユーザー」、「値」、「命令」などの用語を使用します。

良い出発点として、Kaleidoscopeチュートリアルを使用できます

LLVMチュートリアル：目次

特にチュートリアルの第3章を理解することが重要です

Kaleidoscopeチュートリアル

読者は、LLVMでパスがどのように機能するかも知っておく必要があります。彼らはこの参考文献を参考にして、ここから始めることができます

LLVMパスの作成（レガシーPMバージョン）

他に何か？おそらく、読者はLLVMパスのデバッグとバグ修正の経験も必要でしょう。

構成 ¶

この記事は3つの部分で構成されています。最初の部分では、パスの機能をトップレベルで説明します。2番目の部分では、比較手順自体について説明します。3番目の部分では、マージプロセスについて説明します。

すべての部分で、著者はコンテンツをトップダウン形式にしようとします。トップレベルのメソッドが最初に説明され、その後に各パートの末尾にあるターミナルメソッドが続きます。読者がまだ説明されていないメソッドへの参照を見つけた場合、その説明を少し下に見つけることができます。

基本 ¶

どのように行うのか？¶

関数をマージする必要があるでしょうか？明らかな答えは「はい」です。これは非常にあり得るケースです。通常、重複があり、それらを削除することは良いことです。しかし、どのように重複を検出するのでしょうか？これがアイデアです。関数をより小さなブロックまたはパーツに分割し、「ブロック」の量を比較します。等しい場合、「ブロック」自体を比較し、関数自体について結論を出します。

違いは何でしょうか？たとえば、64ビットポインタを持つマシン（アドレス空間が1つしかないと仮定します）では、ある関数が64ビット整数を格納し、別の関数がポインタを格納します。ターゲットが上記のマシンであり、関数がパラメーター型を除いて（関数型の一部と考えることができます）同一である場合、uint64_tとvoid*を等しいものとして扱うことができます。

これはほんの一例にすぎません。詳細については少し下に記載されています。

別の例として、読者はさらに2つの関数を想像するかもしれません。最初の関数は2による乗算を実行し、2番目の関数は1による論理左シフトを実行します。

考えられる解決策 ¶

完全な機能を備えた関数のマージを作成するために、どのように、そして何を実装する必要があるのか、またそれが私たちにとってどのような意味を持つのかについて、可能な選択肢を簡単に検討してみましょう。

等しい関数検出は、明らかに「検出器」メソッドを実装する必要があり、後者は「関数が等しいかどうか」という質問に答える必要があります。この「検出器」メソッドは、それぞれがまったく同じ質問に答える、ただし関数のパーツに対して答える小さな「サブ検出器」で構成されています。

2番目のステップとして、等しい関数をマージする必要があります。したがって、それは「マージャー」メソッドである必要があります。「マージャー」は、2つの関数 *F1* と *F2* を受け入れ、マージの結果である *F1F2* 関数を生成します。

このようなルーチンを手元に用意すれば、モジュール全体を処理し、等しい関数をすべてマージできます。

この場合、すべての関数を別のすべての関数と比較する必要があります。読者が気付くかもしれませんが、この方法は非常にコストがかかるようです。もちろん、ハッシュやその他のヘルパーを導入することもできますが、それは単なる最適化であり、したがって O(N*N) の複雑さのレベルです。

別のレベルに到達できますか？対数探索やランダムアクセスルックアップを導入できますか？答えは「はい」です。

どのように行われるのでしょうか？各関数を数値に変換し、それらをすべて特別なハッシュテーブルに集めるだけです。等しいハッシュを持つ関数は等しいです。適切なハッシュとは、すべての関数パーツを考慮に入れる必要があることを意味します。つまり、すべての関数パーツを何らかの数値に変換し、それをハッシュに追加する必要があります。ルックアップ時間は短くなりますが、このようなアプローチでは、ハッシュルーチンによる遅延が発生します。

対数探索 ¶

関数セット間で完全な順序を導入し、順序付けたら対数探索を実装できます。ルックアップ時間はまだ N に依存しますが、わずかな遅延 ( *log(N)* ) が追加されます。

現状 ¶

両方のアプローチ（ランダムアクセスと対数）が実装およびテストされており、どちらも非常に優れた改善を示しています。最も驚くべきことは、対数探索が高速であったことです。場合によっては最大 15％高速でした。ハッシュ方法は、追加のCPU時間を必要としますが、これは動作が遅くなる主な理由です。ほとんどの場合、合計「ハッシュ」時間は合計「対数探索」時間よりも長くなります。

そのため、「対数探索」が優先されました。

ただし、必要に応じて、*対数探索*（「完全順序付け」と読む）を、*ランダムアクセス*の実装への道のりのマイルストーンとして使用できます。

すべての比較は、数値またはフラグの比較に基づいています。*ランダムアクセス*アプローチでは、同じ比較アルゴリズムを使用できます。比較中、違いが見つかるとすぐに終了しますが、ここでは毎回関数本体全体をスキャンする必要がある場合があります（注意、遅くなる可能性があります）。「完全順序付け」のように、すべての数値とフラグを追跡しますが、比較する代わりに、数値シーケンスを取得してからハッシュ数値を作成する必要があります。したがって、繰り返しになりますが、*完全順序付け*は、理論上はさらに高速なランダムアクセスアプローチのマイルストーンと見なすことができます。

MergeFunctions、主なフィールドと runOnModule ¶

クラスには2つの主要な重要なフィールドがあります。

FnTree – すべての一意の関数のセット。相互にマージできなかった項目を保持します。次のように定義されます。

std::set<FunctionNode> FnTree;

ここで、FunctionNode は、llvm::Function クラスのラッパーであり、関数セット間の「<」演算子が実装されています（以下で、これがどのように正確に機能するかを説明します。これは、高速な関数比較における重要なポイントです）。

Deferred – マージプロセスは、すでに FnTree にある関数の本体に影響を与える可能性があります。明らかに、このような関数は再度チェックする必要があります。この場合、FnTree から削除し、再スキャンされるようにマークし、つまり、Deferred リストに入れます。

runOnModule ¶

アルゴリズムは非常に単純です。

モジュールのすべての関数をワークリストに入れます。

2. ワークリストの関数を2回スキャンします。最初に強い関数のみを列挙し、次に弱い関数のみを列挙します。

2.1. ループ本体：ワークリストから関数（FCurと呼びます）を取得し、FnTreeに挿入しようとします。FCurがFnTree内の関数の1つと等しいかどうかを確認します。FnTreeに等しい関数がある場合（FExistsと呼びます）：関数FCurをFExistsとマージします。それ以外の場合は、ワークリストからFnTreeに関数を追加します。

3. ワークリストのスキャンとマージ操作が完了したら、Deferredリストを確認します。空でない場合は、ワークリストの内容をDeferredリストで再入力し、ステップ2をやり直します。Deferredリストが空の場合は、メソッドから終了します。

比較と対数検索 ¶

タスクを思い出してみましょう。モジュールMのすべての関数Fについて、可能な限り短い時間で等しい関数F`を見つけ、それらを単一の関数にマージする必要があります。

関数セット間で完全な順序を定義すると、関数を二分木に編成できます。この場合、ルックアップ手順の複雑さはO(log(N))と推定されます。しかし、完全な順序をどのように定義するのでしょうか。

すべての関数のペアに適用可能な単一のルールを導入し、このルールに従って、どちらが大きいかを評価する必要があります。どのようなルールが考えられるでしょうか？それを3つの可能な値を返す「比較」メソッドとして宣言しましょう。

-1、左は右より小さい。

0、左と右は等しい。

1、左は右より大きい。

もちろん、これは厳密かつ非厳密な順序関係のプロパティを維持する必要があることを意味します。

反射性（a <= a、a == a、a >= a）、
反対称性（a <= b かつ b <= a の場合、a == b）、
推移性（a <= b かつ b <= c の場合、a <= c）
非対称性（a < b の場合、a > b または a == b）。

前述のように、比較ルーチンは「サブ比較ルーチン」で構成され、それぞれも「サブ比較ルーチン」で構成されています。最後に、プリミティブな比較で終わります。

以下では、次の操作を使用します。

cmpNumbers(number1, number2) は、左が右より小さい場合は-1、左と右が等しい場合は0、それ以外の場合は1を返すメソッドです。
cmpFlags(flag1, flag2) は、2つのフラグを比較する仮説的なメソッドです。ロジックは、cmpNumbers と同じであり、true は1、false は0です。

この記事の残りの部分は、MergeFunctions.cpp ソースコード（<llvm_dir>/lib/Transforms/IPO/MergeFunctions.cpp にあります）に基づいています。読者の皆様には、このファイルを開いたままにして、今後の説明の参考として使用できるようにすることをお勧めします。

これで、次の章に進み、それがどのように機能するかを確認する準備ができました。

関数の比較 ¶

まず、複雑なオブジェクトを正確にどのように比較するかを定義しましょう。

複雑なオブジェクトの比較（関数、基本ブロックなど）は、主にサブオブジェクトの比較結果に基づいています。次の「ツリー」オブジェクトの比較に似ています。

2つのツリーT1とT2について、深さ優先探索を実行し、結果として「T1Items」と「T2Items」の2つのシーケンスを取得します。
次に、チェーン「T1Items」と「T2Items」を、最上位の項目を最初に比較する順序で比較します。項目の比較の結果は、T1とT2の比較自体の結果になります。

FunctionComparator::compare(void)¶

ソースコードを簡単に見てみると、比較が「int FunctionComparator::compare(void)」メソッドで開始されることがわかります。

1. 最初に比較される部分は、関数の属性と、「属性」という用語の範囲外にあるものの、その本体を変更せずに関数を異ならせる可能性のあるいくつかのプロパティです。この比較の部分は、通常、単純なcmpNumbersまたはcmpFlags操作（例：cmpFlags(F1->hasGC(), F2->hasGC())）内で行われます。以下は、この段階で比較される関数のプロパティの完全なリストです。

属性（これらはFunction::getAttributes()メソッドによって返されます）。

GC。同等性のために、RHSとLHSの両方が、GCがないか、同じものである必要があります。

セクション。GCと同様に、RHSとLHSは同じセクションで定義されている必要があります。

可変引数。LHSとRHSの両方が、var-argsがあるか、ない必要があります。

呼び出し規約は同じである必要があります。

2. 関数型。FunctionComparator::cmpType(Type*, Type*) メソッドでチェックされます。戻り型とパラメータ型をチェックします。メソッド自体については後で説明します。

3. 関数の仮パラメータを相互に関連付けます。次に、関数の本体を比較するとき、LHSの本体でLHSのi番目の引数の使用が見られる場合は、RHSの本体の同じ場所でRHSのi番目の引数の使用を確認する必要があります。そうでない場合は、関数が異なります。この段階では、関数の本体で後で会ったものに優先順位を付けます（最初に会った値は小さいになります）。これは、「FunctionComparator::cmpValues(const Value*, const Value*)」メソッドで行われます（後で説明します）。

関数の本体の比較。メソッドのコメントに記載されているように

「リンクされたリスト内のブロックの実際の順序は重要ではないため、CFG順のウォークを実行します。ウォークは両方の関数のエントリブロックから開始し、次に各ターミネータから各ブロックを順に取得します。アーティファクトとして、これは到達不能なブロックが無視されることも意味します。」

したがって、このウォークを使用して、leftとrightから同じ順序でBBを取得し、「FunctionComparator::compare(const BasicBlock*, const BasicBlock*)」メソッドで比較します。

また、関数の仮引数で行ったように、BBを相互に関連付けます（以下のcmpValuesメソッドを参照）。

FunctionComparator::cmpType ¶

型の比較がどのように機能するかを考えてみましょう。

1. ポインタを整数に強制変換します。左の型がポインタの場合は、整数型に強制変換しようとします。アドレス空間が0の場合、またはアドレス空間が完全に無視される場合は、これを行うことができます。右の型についても同じことを行います。

2. 左と右の型が等しい場合は、0を返します。それ以外の場合は、どちらかに優先順位を付ける必要があります。したがって、次のステップに進みます。

3. 型が異なる種類の場合（異なる型ID）。型IDの比較の結果を返し、それらを数値として扱います（cmpNumbers操作を使用）。

4. 型がベクトルまたは整数の場合は、それらのポインタの比較結果を返し、それらを数値として比較します。

型IDが次のグループ（同等のグループと呼びます）に属するかどうかを確認します。
- Void
- Float
- Double
- X86_FP80
- FP128
- PPC_FP128
- Label
- Metadata。
IDが上記のグループに属する場合は、0を返します。型に同じTypeIDがあることがわかれば十分だからです。追加の情報は必要ありません。

6. 左と右がポインタです。アドレス空間の比較結果を返します（数値の比較）。

7. 複雑な型（構造体、配列など）。複雑なオブジェクトの比較手法に従います（この章の最初の段落を参照してください）。leftとrightの両方を展開し、要素の型を同じ方法でチェックします。ある段階で-1または1を取得した場合は、それを返します。それ以外の場合は、0を返します。

8. ステップ1〜6は、考えられるすべてのケースを説明しています。ステップ1〜6を通過して結論が得られなかった場合は、llvm_unreachableを呼び出します。これは非常に予期しないケースであるためです。

cmpValues(const Value, const Value)¶

ローカル値を比較するメソッド。

このメソッドは、非常に興味深い疑問、つまり、ローカルな値を等しいものとして扱うことができるか、そうでない場合はどちらの値が大きいか、という疑問に答えます。例から始めるのが良いでしょう。

左側の関数「FL」と右側の関数「FR」で同じ場所を見ている状況を考えてみましょう。left の場所のすべての部分は、対応する right の場所の部分と等しく、そして（！）両方の部分が Value インスタンスを使用しています。例えば、次のようになります。

instr0 i32 %LV   ; left side, function FL
instr0 i32 %RV   ; right side, function FR

したがって、結論は Value インスタンスの比較に依存します。

このメソッドの主な目的は、このような値の関係を決定することです。

等しい関数に何を期待できるでしょうか？関数「FL」と「FR」の同じ場所では、等しい値、または「FL」と「FR」の同じ場所で定義された値が表示されることを期待します。

ここで簡単な例を考えてみましょう。

define void %f(i32 %pf0, i32 %pf1) {
  instr0 i32 %pf0 instr1 i32 %pf1 instr2 i32 123
}

define void %g(i32 %pg0, i32 %pg1) {
  instr0 i32 %pg0 instr1 i32 %pg0 instr2 i32 123
}

この例では、pf0 は pg0 に関連付けられ、pf1 は pg1 に関連付けられ、さらに pf0 < pf1 であると宣言します。したがって、pg0 < pf1 です。

オペコード「instr0」を持つ命令は、型とオペコードが等しく、値が関連付けられているため、等しいと見なされます。

f のオペコード「instr1」を持つ命令は、g のオペコード「instr1」を持つ命令よりも大きいです。ここでは、型とオペコードは等しいですが、「pf1」は「pg0」よりも大きいです。

オペコード「instr2」を持つ命令は、オペコードと型が等しく、同じ定数が値として使用されているため、等しいです。

cmpValuesで何を関連付けるか？¶

関数の引数。左側の関数の i 番目の引数は、右側の関数の i 番目の引数に関連付けられます。
BasicBlockインスタンス。基本ブロック列挙ループでは、左側の関数の i 番目の BasicBlock を、右側の関数の i 番目の BasicBlock に関連付けます。
命令。
命令のオペランド。ここで、これまで見たことのない Value に出会う可能性があります。この場合、それは関数の引数でも、BasicBlock でもなく、Instruction でもない、グローバルな値です。これは定数です。なぜなら、ここでは唯一想定されるグローバル値だからです。このメソッドはまた、同じ型の定数を比較し、右側の定数が左側の定数に損失なくビットキャストできる場合も比較します。

cmpValuesをどのように実装するか？¶

関連付けは、私たちにとって等価性のケースです。このような値を等しいものとして扱いますが、一般的には、反対称関係を実装する必要があります。前述のように、何がより小さいかを理解するために、値に出会う順序を使用できます。両方の値が関数内で同じ順序（同時に出会った）を持っている場合、それらの値を関連付けられているものとして扱います。そうでない場合は、どちらが最初だったかによって異なります。

トップレベルの比較メソッドを実行するたびに、2つの同一のマップを初期化します（1つは左側用、もう1つは右側用）。

map<Value, int> sn_mapL, sn_mapR;

マップのキーは Value 自体であり、value はその順序（シリアル番号と呼びます）です。

値 V を追加するには、次の手順を実行する必要があります。

sn_map.insert(std::make_pair(V, sn_map.size()));

最初の Value の場合、マップは 0 を返し、2番目の Value の場合は 1 を返す、というようになります。

次に、簡単な比較で、左側と右側の値が同時に出会ったかどうかを確認できます。

cmpNumbers(sn_mapL[Left], sn_mapR[Right]);

もちろん、挿入と比較を組み合わせることもできます。

std::pair<iterator, bool>
  LeftRes = sn_mapL.insert(std::make_pair(Left, sn_mapL.size())), RightRes
  = sn_mapR.insert(std::make_pair(Right, sn_mapR.size()));
return cmpNumbers(LeftRes.first->second, RightRes.first->second);

メソッド全体がどのように実装できるかを見てみましょう。

1. まず悪い知らせから始めなければなりません。関数自体と相互参照のケースを考えてみましょう。

// self-reference unsigned fact0(unsigned n) { return n > 1 ? n
* fact0(n-1) : 1; } unsigned fact1(unsigned n) { return n > 1 ? n *
fact1(n-1) : 1; }

// cross-reference unsigned ping(unsigned n) { return n!= 0 ? pong(n-1) : 0;
} unsigned pong(unsigned n) { return n!= 0 ? ping(n-1) : 0; }

この比較は、初期の MergeFunctions パスのバージョンで実装されました。しかし、残念ながら、それは推移的ではありません。そして、これが、より小さい、等しい、大きい比較に変換できない唯一のケースです。これはまれなケースであり、10000個の関数のうち4〜5個（テストスイートで確認済み）であり、O(log(N))のパス時間を達成するために、読者はそのような犠牲を許してくれることを願っています。

2. 左/右の Value が定数の場合、それらを比較する必要があります。同じ定数である場合は0を返し、それ以外の場合は cmpConstants メソッドを使用します。

3. 左/右が InlineAsm インスタンスの場合。Value ポインタの比較の結果を返します。

4. L（左側の値）と R（右側の値）の明示的な関連付け。値が同時に出会ったかどうか、したがって関連付けられているかどうかを調べる必要があります。または、L < R として扱うルールを置く必要があります。ここで、それは簡単です。数値の比較結果を返すだけです。

std::pair<iterator, bool>
  LeftRes = sn_mapL.insert(std::make_pair(Left, sn_mapL.size())),
  RightRes = sn_mapR.insert(std::make_pair(Right, sn_mapR.size()));
if (LeftRes.first->second == RightRes.first->second) return 0;
if (LeftRes.first->second < RightRes.first->second) return -1;
return 1;

さて、cmpValues が0を返す場合、比較手順を進めることができます。それ以外の場合、(-1または1)が得られた場合は、この結果をトップレベルに渡し、比較手順を終了する必要があります。

cmpConstants ¶

次のように定数比較を実行します。

1. cmpType メソッドを使用して、定数の型を比較します。結果が -1 または 1 の場合、ステップ 2 に移動し、それ以外の場合はステップ 3 に進みます。

2. 型が異なる場合でも、定数がお互いに損失なくビットキャストできるかどうかを確認できます。これに関する詳しい説明は、canLosslesslyBitCastTo メソッドの修正です。

2.1 定数が第一級型であるかどうかを確認します（isFirstClassType チェック）。

2.1.1. 両方の定数が第一級型でない場合：cmpType の結果を返します。

2.1.2. それ以外の場合、左側の型が第一級型でない場合は -1 を返します。右側の型が第一級型でない場合は 1 を返します。

2.1.3. 両方の型が第一級型である場合は、次のステップ (2.1.3.1) に進みます。

2.1.3.1. 型がベクターの場合、cmpNumbers を使用してそれらのビット幅を比較します。結果が 0 でない場合は、それを返します。

2.1.3.2. 型は異なるが、ベクターではない。

両方がポインタの場合、それは私たちにとって都合が良く、ステップ 3 に進むことができます。

型の1つがポインタの場合、isPointer フラグの比較結果（cmpFlags 操作）を返します。

それ以外の場合は、ビットキャスト可能性を証明する方法がないため、型の比較結果（-1または1）を返します。

以下のステップは、型が等しい場合、または定数がビットキャスト可能な場合のケースです。

3. 定数の1つが「null」値です。cmpFlags(L->isNullValue, R->isNullValue) 比較の結果を返します。

値IDを比較し、0でない場合は結果を返します。

if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))
  return Res;

5. 定数の内容を比較します。比較は定数の種類によって異なりますが、この段階では単なる辞書式の比較です。「関数比較」段落の冒頭で説明した方法を参照してください。数学的には、次のケースに等しくなります。左側の定数と右側の定数を（bitcode-writer が行うのと同様の方法で）エンコードします。次に、左側のコードシーケンスと右側のコードシーケンスを比較します。

compare(const BasicBlock, const BasicBlock)¶

2つの BasicBlock インスタンスを比較します。

左側の BB と右側の BB から命令を列挙します。

1. cmpValues メソッドを使用して、左側と右側の命令にシリアル番号を割り当てます。

2. 左側または右側のいずれかが GEP（GetElementPtr）の場合、GEP を他の命令よりも大きいものとして扱います。両方の命令が GEP の場合は、cmpGEP メソッドを比較に使用します。結果が -1 または 1 の場合は、トップレベルの比較に渡します（それを返します）。

3.1. 操作を比較します。cmpOperation メソッドを呼び出します。結果が -1 または 1 の場合は、それを返します。

3.2. オペランドの数を比較します。結果が -1 または 1 の場合は、それを返します。

3.3. オペランド自体を比較し、cmpValues メソッドを使用します。結果が -1 または 1 の場合は、それを返します。

3.4. cmpType メソッドを使用して、オペランドの型を比較します。結果が -1 または 1 の場合は、それを返します。

3.5. 次の命令に進みます。

次の3つのケースで命令列挙を終了できます。

4.1. 左側と右側の基本ブロックの両方の最後に到達しました。ステップ 1〜3 で終了しなかったため、内容は等しいです。0を返します。

4.2. 左側の基本ブロックの最後に到達しました。-1 を返します。

4.3. 1 を返します（右側の基本ブロックの最後に到達しました）。

cmpGEP ¶

2つの GEP（getelementptr 命令）を比較します。

通常の操作比較との違いは、accumulateConstantOffset メソッドを使用できる点のみです。

したがって、左側と右側の両方の GEP の定数オフセットを取得する場合は、それを数値として比較し、比較結果を返します。

それ以外の場合は、通常の操作のように扱います（前の段落を参照）。

cmpOperation ¶

命令のオペコードといくつかの重要な操作プロパティを比較します。

オペコードを比較します。異なる場合は結果を返します。
オペランドの数を比較します。異なる場合は結果を返します。

3. 操作の型を比較します。cmpType を使用します。すべて同じです。型が異なる場合は結果を返します。

4. subclassOptionalData を比較します。getRawSubclassOptionalData メソッドで取得し、数値として比較します。

オペランドの型を比較します。

6. 特定の命令については、いくつかの重要な属性の等価性（この場合は関係性）をチェックします。たとえば、load 命令のアラインメントを比較する必要があります。

O(log(N))¶

上記の方法は、順序関係を実装しています。そして後で、二分木でのノードの比較に使用できます。したがって、関数のセットを二分木に編成し、ルックアップ手順のコストをO(N*N)からO(log(N))に削減できます。

マージ処理、mergeTwoFunctions ¶

MergeFunctions が現在の関数（G）が以前に分析された関数（関数F）と等しいことを検出すると、mergeTwoFunctions(Function*, Function*) を呼び出します。

この操作は、FnTree の内容に次のように影響します。F は FnTree に残ります。G は F と等しいため、FnTree には追加されません。G の呼び出しは別のものに置き換えられます。これにより、呼び出し元の本体が変更されます。そのため、G を呼び出す関数は Deferred セットに入れられ、FnTree から削除され、再度分析されます。

アプローチは次のとおりです。

1. 最も望ましいケース：エイリアスを使用でき、F と G の両方が弱い場合です。両方を3番目の強い関数 H へのエイリアスにします。実際、H は F です。これがどのように行われるかについては以下を参照してください（ただし、ソースコードを直接見た方が良いでしょう）。これは、単にG をどこでも F に置き換えることができるケースで、ここでは replaceAllUsesWith 操作（RAUW）を使用します。

2. F はオーバーライドできませんが、G はオーバーライドできます。次のことを行うのが良いでしょう：オーバーライド可能な関数が使用されていた場所をマージした後でも、オーバーライド可能なスタブを使用します。したがって、G を F のエイリアスにするか、F の周りにオーバーライド可能な末尾呼び出しラッパーを作成し、G をその呼び出しで置き換えるようにします。

3. F も G もオーバーライドできません。RAUW は使用できません。呼び出し元を変更するだけで済みます。G の代わりに F を呼び出します。これが replaceDirectCallers が行うことです。

以下に、詳細な本文の説明を示します。

「F」がオーバーライド可能な場合 ¶

mayBeOverridden のコメントからわかるように、「このグローバルの定義がリンク時に同等でないものに置き換えられるかどうか」です。もしそうなら、それは問題ありません：G の代わりに F のエイリアスを使用するか、呼び出し命令自体を変更できます。

HasGlobalAliases、removeUsers ¶

まず、ある関数名から別の関数名へのグローバルエイリアスがある場合を考えてみます。私たちの目的は、両方を3番目の強い関数へのエイリアスにすることです。ただし、F を生かし、大幅な変更を加えない場合は、FnTree に残すことができます。これら2つの目標を組み合わせるように試みてください。

F 自体を F へのエイリアスでスタブ置換します。

1. 関数 F と同じ名前と属性を持つスタブ関数 H を作成します。これは、F と G の最大のアラインメントを取ります。

2. 関数 F のすべての使用箇所を関数 H の使用箇所に置き換えます。これは2段階の手順です。まず、F が呼び出されるすべての関数が変更されることを考慮する必要があります。呼び出し引数を（F から H に）変更するためです。もしそうなら、この手順の後、これらの呼び出し元関数を再度確認する必要があります。呼び出し元を FnTree から削除します。名前 removeUsers(F) のメソッドがそれを行います（replaceAllUsesWith と混同しないでください）。

2.1. Inside removeUsers(Value* V) では、値 V（またはコンテキスト内の F）を使用するすべての値を調べます。値が命令の場合、この命令を保持する関数に移動し、再度分析するようにマークします（Deferred セットに入れます）。また、呼び出し元を FnTree から削除します。

2.2. これで置換を行うことができます。F->replaceAllUsesWith(H) を呼び出します。

3. H（現在は「正式に」F の役割を果たしています）は F へのエイリアスに置き換えられます。G についても同じことを行います。F へのエイリアスに置き換えます。したがって、最終的には、F が使用されていた場所すべてで H が使用され、F のエイリアスであり、G が使用されていた場所すべてでも F のエイリアスがあります。

F のリンケージをプライベートに設定します。強くしてください:-)

グローバルエイリアスなし、replaceDirectCallers ¶

グローバルエイリアスがサポートされていない場合。私たちは replaceDirectCallers を呼び出します。単に G のすべての呼び出しを調べ、F の呼び出しに置き換えます。メソッドを調べると、G のすべての使用箇所もスキャンし、使用箇所が呼び出し先の場合（ユーザーが呼び出し命令であり、G が呼び出されるものとして使用されている場合）、F の使用箇所で置き換えます。

「F」がオーバーライドできない場合、修正します！¶

私たちは writeThunkOrAlias(Function *F, Function *G) を呼び出します。ここでは、最初に G を F へのエイリアスに置き換えることを試みます。次の条件が重要です。

ターゲットがグローバルエイリアスをサポートしている必要がある。
G のアドレス自体が重要ではなく、名前がなく、どこからも参照されていない必要がある。
関数は、外部、ローカル、または弱いリンケージを持っている必要がある。

それ以外の場合は、サンクを記述します。G のインターフェイスを持ち、F を呼び出すいくつかのラッパーです。そのため、G をこのラッパーで置き換えることができます。

writeAlias

llvm リファレンスからわかるように

「エイリアスは、エイリアシー値の2番目の名前として機能します」。したがって、F の2番目の名前を作成し、G の代わりに使用するだけです。

グローバルエイリアス自体 (GA) を作成し、
F のアラインメントを調整して、現在のアラインメントと G のアラインメントの最大値にする必要があります。
G の使用箇所を置き換えます。

3.1. まず、removeUsers メソッドを使用して（上記の章を参照）、G のすべての呼び出し元を再度分析するようにマークします。

3.2. G->replaceAllUsesWith(GA) を呼び出します。
G を取り除きます。

writeThunk

メソッドのコメントに書かれているように

「G を bitcast(F) への単純な末尾呼び出しに置き換えます。また、G の直接の使用箇所を bitcast(F) に置き換えます。G を削除します。」

一般的に、呼び出し先を置き換えたい場合と同じことを行いますが、最初の点を除きます。

1. F の周りに末尾呼び出しラッパーを生成しますが、G の代わりに使用できるインターフェイスを備えています。

「通常どおり」：removeUsers と replaceAllUsesWith を行います。
G を取り除きます。

ドキュメント

参加する

追加リンク

このページ