LLVMにおける依存グラフ¶
はじめに¶
依存グラフは、コンパイラにおいて、最適化を導くために様々なプログラム要素間の関係を分析するのに役立つツールです。これらのグラフの背後にあるアイデアは、論文 [1] と [2] で説明されています。
LLVMにおけるこれらのアイデアの実装は、論文で述べられている内容とわずかに異なる場合があります。これらの違いについては、実装の詳細で説明されています。
データ依存グラフ¶
最も単純な形式では、データ依存グラフ（またはDDG）は、個々の命令間のデータ依存関係を表します。このようなグラフの各ノードは、単一の命令を表し、「アトミック」ノードと呼ばれます。また、単純な定義-使用依存関係を持ついくつかのアトミックノードを、複数の命令を含むより大きなノードに結合することも可能です。
[1] で説明されているように、DDGは、グラフの強連結成分の一部であるノードを、pi-ブロックと呼ばれる特別なノードにグループ化するために、グラフ抽象化を使用します。pi-ブロックは、並べ替え変換を妨げるデータ依存関係のサイクルを表します。グラフの任意の強連結成分は、サイクルを形成するすべてのノードの最大部分グラフであるため、pi-ブロックは最大でも1レベルの深さです。言い換えれば、pi-ブロックが別のpi-ブロック内にネストされることはなく、最大でも1レベルの深さの階層的な表現になります。
たとえば、次の例を考えてみましょう。
for (int i = 1; i < n; i++) {
b[i] = c[i] + b[i-1];
}
このコードには、DDGにサイクルを作成するループ内依存性を持つステートメントが含まれています。下の図は、依存関係のサイクルが複数の定義-使用関係とメモリアクセス依存関係を介してどのように伝播されるかを示しています。
この例に対応するDDGには、以下に示すように、サイクルに参加するすべてのノードを含むpi-ブロックがあります。
プログラム依存グラフ¶
プログラム依存グラフ（またはPDG）は、DDGと同様の構造を持っていますが、命令、命令のグループ、基本ブロック、または基本ブロックのグループなどのプログラム要素間のデータ依存関係と制御フロー依存関係の両方を表現できます。
高レベル設計¶
DDGとPDGはどちらも有向グラフであり、DirectedGraphクラスを拡張しています。各実装は、対応するノード型とエッジ型を拡張し、以下のUML図に示すような継承関係になります。
グラフの構築¶
グラフ構築アルゴリズムは、指定された命令または基本ブロックのセットの要素間の依存関係を考慮します。その範囲に属さない命令に出入りする依存関係は無視されます。DDGの構築アルゴリズムの手順は、PDGの構築アルゴリズムの手順と非常に似ています。そのため、設計目標の1つは、構築アルゴリズムのコードを再利用して、DDGとPDGの両方の表現を作成できるようにすることです。同時に、2つの実装が独自の個別の独立したノード型とエッジ型を定義できるようにします。これは、よく知られているビルダーデザインパターンを使用して、依存グラフの構築を具体的な表現から分離することで実現されます。
次のUML図は、依存グラフの実装に適用されるデザインパターンの全体的な構造を示しています。
2種類のグラフを構築するための共通コードは、DependenceGraphBuilderクラスで提供され、DDGBuilderとPDGBuilderは、DependenceGraphBuilderで定義された仮想メソッドをオーバーライドすることで、グラフの構築方法のいくつかの側面を制御することに注意してください。
また、この図で使用されている手順と名前は説明のためであり、実際の実装とは異なる場合があることに注意してください。
設計上のトレードオフ¶
利点:¶
ビルダーを使用すると、グラフ構築コードをDDGとPDGで再利用できます。
ビルダーを使用すると、DDGとPDGを別々のグラフとして作成できます。
DDGのノードとエッジは、PDGのノードとエッジから完全に分離されているため、簡単に独立して変更できます。
欠点:¶
ビルダーは、最初は過剰な設計と見なされる可能性があります。
DDGのノードとエッジとPDGのノードとエッジの間にはいくつかの類似点がありますが、クラス定義の再利用はほとんどありません。
ノード型とエッジ型はかなり単純であり、コード再利用の機会がほとんどないため、これは許容範囲です。
実装の詳細¶
現在のDDGの実装は、[1] で説明されている依存グラフと次の点でわずかに異なります。
論文のグラフノードは、主に代入文、forループヘッダー、whileループヘッダーの3つのプログラムコンポーネントを表しています。この実装では、DDGノードは自然にLLVM IR命令を表します。この実装における代入文は、通常、
store命令を表すノードと、代入の右辺を計算する複数の個々のノードが、定義-使用エッジを介してstoreノードに接続されていることを意味します。ループヘッダー命令は、使用が限られており、たとえばLoopAnalysisを通じて簡単に識別できるため、この実装では特別なノードとして表現されません。この論文では、ノード間の依存エッジの5つのタイプ、すなわちループ依存、フロー、アンチ、出力、および入力依存が説明されています。この実装では、メモリエッジはフロー、アンチ、出力、および入力依存関係を表します。ただし、ループ依存関係は、主にループ構造とループ内のプログラム要素との間の関連を表しており、この関連はLLVM IR自体ではかなり明らかであるため、明示的には表現されていません。
この論文では、2種類のpi-ブロックが説明されています。本体がSCCである再帰と、本体がSCCの一部ではないINノードです。この実装では、pi-ブロックは再帰に対してのみ作成されます。INノードは、グラフ内の単純なDDGノードのままです。