ポインタ解析

コンピュータ サイエンスにおいて、ポインタ解析(またはポイントツー解析)は、どのポインタ(ヒープ参照) がどの変数またはストレージの場所を指すことができるかを確立する静的コード解析手法です。これは、エスケープ解析などのより複雑な解析のコンポーネントになることがよくあります。密接に関連する手法として、シェイプ解析があります。

これは、この用語の最も一般的な口語的な用法です。2 つ目の用法では、ポインター分析は、上で定義したポイントツー分析とエイリアス分析の両方の総称です。ポイントツー分析とエイリアス分析は密接に関連していますが、必ずしも同等の問題ではありません。

次の C プログラムを考えてみましょう。

int * id ( int * p ) { return p ; } void main ( void ) { int x ; int y ; int * u = id ( & x ); int * v = id ( & y ); }   
   

  
   
   
     
     

ポインタ解析は、ポインタ式から、ポインタ式が指す可能性のあるオブジェクトの割り当て場所のセットへのマッピングを計算します。上記のプログラムの場合、理想的な完全に正確な解析では、次の結果が計算されます。

(ここで、 は関数内のX::Yローカル変数を保持するスタック割り当てを表します。) YX

ただし、アンダーセンやスティーンスガードのアルゴリズムなどのコンテキストに依存しない分析では、 の呼び出しを分析するときに精度が失われid、次の結果が計算されます。

静的解析の一形態として、完全に正確なポインタ解析は決定不可能であることが示されています。^[1]ほとんどのアプローチは妥当ですが、パフォーマンスと精度には大きなばらつきがあります。多くの設計上の決定は解析の精度とパフォーマンスの両方に影響します。多くの場合（常にではありませんが）、精度が低いほどパフォーマンスが高くなります。これらの選択肢には以下が含まれます。^{[2] [3]}

• フィールド センシティビティ(構造センシティビティとも呼ばれます): 分析では、構造体またはオブジェクトの各フィールドを個別に処理することも、それらをマージすることもできます。
• 配列の感度: 配列を感知するポインター分析は、配列内の各インデックスを個別にモデル化します。その他の選択肢としては、最初のエントリだけを個別にモデル化し、残りを一緒にモデル化するか、すべての配列エントリをマージするかがあります。
• コンテキスト感度または多変量: ポインタ解析では、各プログラム ポイントにつながる制御フローの概要を使用して、ポイント先情報を限定できます。
• フロー感度: 分析では、手順内制御フローがポイントツーファクトに与える影響をモデル化できます。
• ヒープモデリング: 実行時の割り当ては次のように抽象化できます。
  • 割り当て場所（割り当てを実行する文または命令、たとえば呼び出しmallocまたはオブジェクトコンストラクタ）
  • 形状分析に基づくより複雑なモデル、
  • 割り当ての種類、または
  • 1 つの割り当てのみ (これをヒープ非依存と呼びます)。
• ヒープ クローニング: ヒープおよびコンテキスト依存の分析では、割り当てを実行する命令またはステートメントにつながる制御フローの概要によって、各割り当てサイトをさらに限定する場合があります。
• サブセット制約または等価制約: ポイント先ファクトを伝播する場合、異なるプログラム ステートメントによって、変数のポイント先セットに異なる制約が課されることがあります。等価制約 ( Steensgaard のアルゴリズムで使用されるものなど) は、 union-find データ構造を使用して追跡できます。これにより、サブセット制約ベースの分析 (Andersen のアルゴリズムなど) の精度を犠牲にして、高いパフォーマンスが得られます。

ポインタ解析アルゴリズムは、収集された生のポインタの使用状況（あるポインタを別のポインタに割り当てたり、ポインタを別のポインタを指すように割り当てたりすること）を、各ポインタが指すことができるものの有用なグラフに変換するために使用されます。^[4]

SteensgaardのアルゴリズムとAndersenのアルゴリズムは、ポインタ解析のための一般的なコンテキスト非依存、フロー非依存アルゴリズムです。これらはコンパイラでよく使用され、SVF ^[5] とLLVMに実装されています。

フロー非依存のポインタ解析に対する多くのアプローチは、ヒープ割り当てが割り当て場所（つまりプログラムの場所）によって抽象化される抽象解釈の形式として理解できます。 ^[6]

Datalogでは、JavaのSoot分析フレームワークに含まれるものを含め、フロー非依存アルゴリズムが多数指定されています。 ^[7]

コンテキスト依存、フロー依存のアルゴリズムは、各手順をコンテキストごとに 1 回ずつ複数回分析することで、一般にパフォーマンスを犠牲にしてより高い精度を実現します。^[8]ほとんどの分析では、「コンテキスト文字列」アプローチが使用され、コンテキストはエントリのリストで構成されます (コンテキスト エントリの一般的な選択肢には、呼び出しサイト、割り当てサイト、およびタイプが含まれます)。^[9]終了 (およびより一般的にはスケーラビリティ) を保証するために、このような分析では通常、コンテキストの最大サイズが固定され、最近追加された要素が最も古いものが必要に応じて削除されるk制限アプローチが使用されます。^[10]コンテキスト依存、フロー非依存の分析の一般的な 3 つのバリエーションは次のとおりです。^[11]

• コールサイト感度
• 物体感度
• タイプ感度

呼び出しサイト センシティビティでは、各変数のポイント先セット (各変数がポイントできる抽象ヒープ割り当てのセット) は、プログラム内の呼び出しサイトのリストで構成されるコンテキストによってさらに限定されます。これらのコンテキストは、プログラムの制御フローを抽象化します。

次のプログラムは、コールサイト感度が、フロー非依存、コンテキスト非依存の分析よりも高い精度を達成する方法を示しています。

int * id ( int * p ) { return p ; } void main ( void ) { int x ; int y ; int * u = id ( & x ); // main.3 int * v = id ( & y ); // main.4 }   
   

  
   
   
       
       

このプログラムの場合、コンテキストに依存しない分析では、p はxを保持する割り当てまたはyの割り当てのいずれかを指すことができると（健全ではあるが不正確ですが）結論付けられます。そのため、uとv はエイリアスになる可能性があり、どちらもいずれかの割り当てを指す可能性があります。

呼び出し元に依存する分析では、id をに対して 1 回、main.3に対して 1 回、合わせて 2 回分析し、 pmain.4のポイント先ファクトは呼び出し元によって修飾されるため、 main が返されるときに、u はxを保持している割り当てのみを指し、v はy を保持している割り当てのみを指すことが分析によって推測できるようになります。

オブジェクトセンシティブ分析では、各変数のポイント先セットは、メソッド呼び出しの受信オブジェクトの抽象ヒープ割り当てによって修飾されます。呼び出しサイトのセンシティビティとは異なり、オブジェクトセンシティビティは非構文的または非ローカルです。コンテキストエントリは、ポイント先分析自体の間に導出されます。^[12]

型センシティビティはオブジェクトセンシティビティの変形であり、受信オブジェクトの割り当て場所が、受信オブジェクトの割り当て場所を含むメソッドを含むクラス/型に置き換えられます。^[13]これにより、オブジェクトセンシティブ分析で使用されるコンテキストよりも厳密に少ないコンテキストが生成され、通常はパフォーマンスが向上します。

• Zyrianov, Vlas; Newman, Christian D.; Guarnera, Drew T.; Collard, Michael L.; Maletic, Jonathan I. (2019)。「srcPtr: 静的ポインタ解析アプローチを実装するためのフレームワーク」(PDF)。ICPC '19: 第 27 回 IEEE 国際プログラム理解会議の議事録。カナダ、モントリオール: IEEE。
• Smaragdakis, Yannis; Balatsouras, George (2015). 「ポインタ解析」(PDF) .プログラミング言語の基礎と動向. 2 (1): 1–69. doi :10.1561/2500000014. S2CID  207179267 . 2019年5月30日閲覧。
• Li, Yue; Tan/, Tian; Møller, Anders; Smaragdakis, Yannis (2020-05-18). 「ポインタ解析における選択的コンテキスト感度への原理的アプローチ」. ACM Transactions on Programming Languages and Systems . 42 (2): 10:1–10:40. doi :10.1145/3381915. ISSN  0164-0925. S2CID  214812357.
• Michael Hind (2001)。「ポインタ解析: この問題はまだ解決されていないのか?」(PDF)。PASTE '01: ソフトウェア ツールとエンジニアリングのためのプログラム解析に関する 2001 ACM SIGPLAN-SIGSOFT ワークショップの議事録。ACM。pp. 54–61。ISBN 1-58113-413-4。
• Steensgaard, Bjarne (1996)。「ほぼ線形時間でのポイントツー分析」(PDF)。POPL '96: プログラミング言語の原理に関する第 23 回 ACM SIGPLAN-SIGACT シンポジウムの議事録。ニューヨーク、ニューヨーク、米国: ACM。pp. 32–41。doi : 10.1145 / 237721.237727。ISBN 0-89791-769-3。
• Andersen, Lars Ole (1994). C プログラミング言語のプログラム分析と特殊化(PDF) (博士論文).