Loading article…
コンピュータサイエンスにおいて、スティーンスガードのアルゴリズムは、スケーラブルでフローに依存しないポインタ解析アルゴリズムです。その速度のため、コンパイラでよく使用されます（たとえば、LLVMコンパイラフレームワークに実装があります）。[ 1 ]このアルゴリズムは、元の定式化では、フィールド、コンテキスト、配列に依存しませんでした。
スティーンスガードのアルゴリズムは等式制約に基づいており、[ 2 ]サブセット制約に基づくアンダーセンのアルゴリズムとは対照的です。これにより、ユニオンファインドデータ構造を使用してポイント情報を追跡できます。この選択により、アルゴリズムは特徴的な速度を持ち、ユニオンファインドデータ構造を使用して実装すると、入力プログラムのサイズに対して線形空間とほぼ線形時間になります。
ビャルネ・スティーンスガードによるアルゴリズムの定式化は、型推論と型チェックの観点から行われた。スティーンスガードは、 C言語のようなポインタを持つ他の一般的な言語の本質的な特性を捉えた、小規模ながら汎用的な命令型ポインタ言語に対して、ポインタ解析を提案した。この解析は、言語の意味論と型付け規則によって構成される。