Loading article…
コンピュータサイエンスにおいて、制御フローグラフ（CFG）は、関数の実行中、つまり制御フロー中に通過する可能性のあるすべてのパスをグラフ表記を用いて表現したものです。制御フローグラフは、フランシス・E・アレン[ 1 ] [ 2 ]によって考案されました。彼女は、リース・T・プロッサーが以前にフロー解析にブール接続行列を使用していたことを指摘しました[ 3 ]。
CFGは、多くのコンパイラ最適化ツールや静的解析ツールにとって不可欠な要素である。
制御フローグラフとは、関数の基本ブロック（グラフのノード）と、それらの間の制御フロー（グラフのエッジ）を表す有向グラフのことである。
具体的な詳細は表現方法によって異なります。一般的に、基本ブロックは一連の命令またはステートメントが直線状に並んだ構造になっています。各ブロック内で制御フローを実行できるのは最後の命令またはステートメントのみであり、制御フローはブロック内の最初の命令またはステートメントにのみ向けられます。
ほとんどのCFG表現では、2つの特別なブロックが指定されています。1つは、制御が関数に入るエントリブロック、もう1つは、すべての制御が関数から出る（通常は戻ることによって）出口ブロックです。[ 4 ]一部の表現では、特に異なる種類の出口がある場合、複数の出口ブロックを許可したり、到達不可能な場合は出口ブロックを省略したりすることができます。
ブロックAからブロックBへの制御フローエッジが存在する場合、AはBの先行ブロックと呼ばれ、BはAの後継ブロックと呼ばれる。
簡単な例として、次のC言語の関数定義を考えてみましょう。
void print_within_parentheses ( const char * p ) { printf ( "(" ); // 1 if ( p != NULL ) { // 1 printf ( "%s" , p ); // 2 } // 2 printf ( ")" ); // 3 }この関数は、3つの基本的な構成要素から成り立っています。
p != NULLifif。そして、無条件にブロック3に移行することで終了します。if暗黙的な終了まで実行されます。returnソースプログラムの入れ子構造のため、基本ブロックを把握するのは少し困難です。ブロックをより分かりやすく表現する代替手段として、その構造をラベル付きブロックのシーケンスに平坦化することができます。制御フローを明確にするために、各ブロックは、、または（終了ブロックのみ）のいずれかで終わるgoto必要ifがありelseます。gotoreturn
void print_within_parentheses ( const char * p ) { block1 : { printf ( "(" ); if ( p != NULL ) { goto block2 ; } else { goto block3 ; } }block2 : { printf ( "%s" , p ); goto block3 ; }block3 : { printf ( ")" ); return ; } }これはCFGのソースレベル表現です。基本ブロックは、ソースプログラムから直接取得したC言語のステートメントのシーケンスで構成されています。構造化された制御フローのみが削除されています。
次に、ループを含むより複雑な例を考えてみましょう。
void print_as_ordered_tuple ( const char * const * p ) { printf ( "(" ); // 1 bool first = true ; // 1 for (; * p != NULL ; ++ p ) { // 2 if ( ! first ) { // 3 printf ( "," ); // 4 } // 4 first = false ; // 5 printf ( "%s" , * p ); // 5 } // 5 printf ( ")" ); // 6 }この関数は6つの基本ブロックから構成されており、CFGのソースレベル表現で明確に確認できます。
void print_as_ordered_tuple ( const char * p ) { bool first ;block1 : { printf ( "(" ); first = true ; goto block2 ; }block2 : { if ( * p != NULL ) { goto block3 ; } else { goto block6 ; } }block3 : { if ( ! first ) { goto block4 ; } else { goto block5 ; } }block4 : { printf ( "," ); goto block5 ; }block5 : { first = false ; printf ( "%s" , * p ); ++ p ; goto block2 ; }block6 : { printf ( ")" ); return ; } }このスタイルのステートメントレベルのCFG表現は一般的には使用されておらず、ここでは説明のためにのみ示されています。C言語であっても、すべてのプログラムがこのように簡単に表現できるわけではありません。ローカル変数の宣言が関数の先頭に移動され、その初期化が代入になっていることに注目してください。これは、シャドウイングや可変長配列などのスコープ駆動機能に問題を引き起こします。また、、、および演算子block1によって導入されるような式レベルの制御フローを扱うには、ステートメントを大幅に書き直す必要があります。&&||? :
実用的なCFG表現のほとんどは、基本ブロックの構成要素として完全なソースステートメント以外のものを使用します。たとえば、LLVMなどのコンパイラフレームワークは、基本ブロックが抽象的な静的単一代入命令で構成されるCFGを主要なIRとして使用します。以下は、上記の関数をLLVM IRに変換したものです。
define void @print_as_ordered_tuple ( ptr %0 ) { block1: %p = alloca ptr %first = alloca i1 store ptr %0 , ptr %p call i32 ( ptr , ...) @printf ( ptr @"(" ) store i1 1 , ptr %first br label %block2block2: %1 = load ptr 、ptr %p %2 = load ptr 、ptr %1 %3 = icmp ne ptr %2 、null br i1 %1 、label %block3 、label %block4block3: %4 = load i1 、ptr %first br i1 %4 、label %block4 、label %block5block4: call i32 ( ptr , ...) @printf ( ptr @"," ) br label %block5block5: store i1 0 , ptr %first %5 = load ptr , ptr %p %6 = load ptr , ptr %5 call i32 ( ptr , ...) @printf ( ptr @"%s" , ptr %6 ) %7 = load ptr , ptr %p %8 = getelementptr inbounds ptr , ptr %7 , i32 1 store ptr %8 , ptr %p br label %block2block6: call i32 ( ptr , ...) @printf ( ptr @"" ) ret void }ソースレベルとLLVM CFGにおけるブロック構造が同じであることに注目してください。どちらの表現においても、関数は同じ基本的な意味論を持ち、同じ一連の操作と制御フローを実行します。異なるのは、個々の操作の表現方法だけです。
ソース関数から非常に明示的な制御フローグラフを取得するには、各ステートメントをそれぞれ独自の基本ブロックに配置します。ステートメントが制御フローステートメントでない場合は、次のステートメントのブロックへの「フォールスルー」ジャンプがブロックに追加されます。残念ながら、これは多数の不要な基本ブロックとフォールスルージャンプを生成する傾向があり、その後の分析がより煩雑でコストがかかることになります。通常、連続するステートメントは可能な限り同じ基本ブロックに配置することが望ましいです。言い換えれば、CFG全体にわたって、すべてのエッジA→Bは次の特性を持つ必要があります。
このようなグラフは、上記の述語を偽るすべてのエッジに対してエッジ縮約を実行することによって、1ブロックあたり1ステートメントのCFGから導出できます。つまり、ソースブロックが常に宛先ブロックにジャンプし、宛先ブロックはソースブロックからのみジャンプできる場合に、2つのブロックをマージします。ただし、この縮約ベースのアルゴリズムは、初期形式の構築コストが高いため、CFG構築を理解するための視覚化補助として以外には、実用的な重要性はほとんどありません。典型的な実装では、基本ブロック間の必要な境界をプログラムをスキャンするなど、構築によって不要なブロックを最小限に抑える方法で、プログラムから直接CFGが構築されます。[ 5 ]
到達可能性は、最適化において有用なグラフ特性です。エントリブロックからどのパスからもブロックに到達できない場合、そのブロックは実行不可能であり、到達不能コードと呼ばれます。到達不能コードは通常、制御フローグラフから削除しても悪影響はありません。
開始ブロックから終了ブロックへどの経路からも到達できない場合、制御フローはグラフから正常に抜け出すことができません。これは、無限ループが存在するか、あるいはこれらの機能を直接サポートする表現においては、プログラムの異常終了または異常終了を示しています。終了ブロックへ何らかの経路から到達可能であるからといって、プログラムが必ずしもそこに到達するとは限らず、一般的なグラフでは到達することを証明することは不可能です。停止問題を参照してください。
最適化によって、元のプログラムでは明らかではなかった到達不能なコードや無限ループが明らかになることがあります。例えば、次のLLVM関数を考えてみましょう。
define void @double_until_odd ( ptr %p ) { block1: br label %block2block2: %0 = load i32 , ptr %p ; %p から現在の値をロード%1 = mul i32 %0 , 2 ; 2 倍するstore i32 %1 , ptr %p ; %p に格納する%2 = and i32 %1 , 1 ; 積の下位ビットをマスクする%3 = icmp eq i32 %2 , 0 ; 0 かどうかをチェックするbr i1 %3 , label %block2 , label %block3 ; 0 ならループするblock3: ret void }この形式では、この関数のループは無限ループではありません。ループから抜け出す経路が存在するからです。 が%3偽の場合、プログラムは に分岐してblock3戻ります。しかし、数値解析によって、任意の数と 2 の積は偶数になることが証明できます。つまり、 は%2常にゼロであり、%3偽になることは決してありません。したがって、この関数は次のように最適化できます。
define void @double_until_odd ( ptr %p ) { block1: br label %block2block2: %0 = load i32 , ptr %p ; %p から現在の値をロードします%1 = mul i32 %0 , 2 ; 2 倍しますstore i32 %1 , ptr %p ; %p に格納しますbr label %block2block3: ; 到達不能な戻り値void }制御フローグラフに無限ループが発生し、終了ブロックに到達できなくなりました。なお、この最適化によってプログラムの動作自体は変わりません。ループが終了することはないというのは、元々変わらない事実です。変わったのは、制御フローグラフがその事実をより正確に反映するようになったという点だけです。
ブロック M がブロック Nを支配するとは、エントリからブロック N に到達するすべてのパスがブロック M も経由しなければならない場合をいう。エントリ ブロックはすべてのブロックを支配する。M が N を支配し、かつ両者が異なるブロックである場合、M はN を適切に支配すると言う。さらに、個々のステートメントまたは命令 X がステートメントまたは命令 Y を適切に支配するとは、X を含むブロックが Y を含むブロックを支配し、かつ両者が同じブロックである場合、X がブロック内で Y より厳密に先行する場合をいう。
ブロックMがブロックNを支配し、かつMがPを支配し、かつPがNを支配するような中間ブロックPが存在しない場合、MはブロックNを直接支配すると言われる。言い換えれば、Mは入口からNまでのすべての経路における最後の支配ブロックである。到達可能なすべてのブロックには、入口ブロックを除いて、一意の直接支配ブロックが存在する。入口ブロックには直接支配ブロックは存在しない。
ドミネータツリーは、関数内の支配関係を表す有向グラフです。グラフのノードは関数の到達可能な基本ブロックであり、ブロックMがブロックNの直接の支配ブロックである場合、ブロックMからブロックNへのエッジが存在します。各非エントリ到達可能ブロックには一意の直接の支配ブロックが存在するため、これはエントリブロックを根とするツリーです。ドミネータツリーは、Lengauer–Tarjanアルゴリズムを使用して効率的に計算できます。
逆方向では、ブロック M がブロック Nを後支配するとは、N から出口へのすべてのパスがブロック M も通過しなければならない場合をいう。(これはハイフンなしでM postdominates N と表記されることもある。) 出口ブロックはすべてのブロックを後支配する。M がN を後支配し、かつ M と N が異なるブロックである場合、M は N を適切に後支配すると言われる。M が N を後支配し、かつ M が P を後支配し、かつ P が N を後支配するようなブロック P が存在しない場合、M は N の直接の後支配者である。出口ブロックに到達可能なすべてのブロックには、出口ブロックを除いて一意の直接の後支配者が存在する。出口ブロックには直接の後支配者は存在しない。これにより、出口ブロックに到達可能なブロック上に、出口ブロックを根とする後支配者ツリーが生成される。
支配性の標準的な定義には到達不可能なブロックが含まれ、後支配性の標準的な定義には出口ブロックに到達できないブロックが含まれます。しかし、これらの関係において、そのようなブロックは固有の特性を持ちます。到達不可能なブロックはすべてのブロックに支配され、出口に到達できないブロックはすべてのブロックに後支配されます。支配性または後支配性に基づくほとんどの分析では、これらのブロックは無視され、支配者ツリーまたは後支配者ツリーには含まれません。一部の表現では、少なくとも形式的には、これらのブロックが存在しないようにするために、不可能なエッジを追加する必要があります。
クリティカルエッジとは、ソースブロックから出る唯一のエッジでもなく、デスティネーションブロックに入る唯一のエッジでもないエッジのことです。最適化によっては、プログラムの他のパスに影響を与えることなく、クリティカルエッジに沿って命令を挿入するために、クリティカルエッジを分割する必要がある場合があります。エッジの分割は、デスティネーションブロックへのジャンプのみを含む新しいブロックを作成し、元の分岐先を新しいブロックに置き換えることによって行われます。
後退エッジとは、エッジのエントリブロックからソースブロックへの単純なパス（グラフの深さ優先探索で見つかるようなパス）が存在し、そのパスに宛先ブロックが含まれるエッジのことです。後退エッジは、制御フローグラフにサイクルが存在することを示します。宛先ブロックがソースブロックへのすべての可能なパス上に存在する場合、つまり宛先ブロックがソースブロックを支配する場合、後退エッジはバックエッジと呼ばれます。
異常エッジとは、行き先が不明なエッジのことです。例外処理構造によって発生する可能性があります。これらのエッジは最適化を阻害する傾向があります。
不可能なエッジ（偽エッジとも呼ばれる）とは、実行中に実際に通過できないエッジであり、何らかの有用な特性を維持するためにグラフに追加されるものです。例えば、一部の表現では、出口ブロックが常に到達可能であり、かつすべてのブロックに対して後支配的であることを保証するために、不可能なエッジを追加する必要があります。
制御フローグラフの強連結成分（SCC）とは、互いに到達可能な基本ブロックの集合です。ループを構成するブロックは、常に同じ強連結成分に属します。サイクルを構成しないブロックは、常に単独で強連結成分に属します。特に、エントリブロックとエグジットブロックは、それぞれ独立した強連結成分となります。
CFG の強連結成分は、 SCC ツリーと呼ばれる有向非巡回グラフを形成します。ここで、成分 A のいずれかのブロックが成分 B のいずれかのブロックにエッジを持つ場合、成分 A は成分 B にエッジを持ちます。CFG にサイクルがない場合、SCC ツリーは制御フローグラフと同型です。サイクルがある場合、SCC ツリーは基本的にその中のすべてのブロックとエッジを単一のノードに縮約します。これは、サイクル内のすべてのブロックを同等に扱いたい分析に役立ちます。たとえば、使用点のセットをできるだけ狭くカバーするオブジェクトの寿命を見つけようとする場合、使用点の 1 つが巡回 SCC 内にある場合、寿命はその成分内のすべてのブロックを完全にカバーする必要があります。
ループヘッダー（ループのエントリポイントとも呼ばれる）は、ループ形成バックエッジのターゲットとなるドミネータです。ループヘッダーは、ループ本体内のすべてのブロックを支配します。1つのブロックが複数のループのループヘッダーになることもあります。ループには複数のエントリポイントが存在する場合があり、その場合は「ループヘッダー」は存在しません。
ブロック M が、複数の入力エッジを持つドミネータであり、そのうちのいくつかはバックエッジであるとします (つまり、M はループ ヘッダーです)。いくつかの最適化パスでは、M を 2 つのブロック M preと M loopに分割することが有利です。M の内容とバックエッジは M loopに移動され、残りのエッジは M preを指すように移動され、M preからM loopへの新しいエッジが挿入されます (これにより、M preは M loopの直接のドミネータになります)。最初は M pre は空ですが、ループ不変コード移動などのパスによってデータが追加される可能性があります。M preはループ プリ ヘッダーと呼ばれ、M loop はループ ヘッダーと呼ばれます。
制御フローグラフは、後退するエッジがすべてバックエッジである場合、還元可能と呼ばれます。このようなCFGの他のエッジは、フォワードエッジと呼ばれます。[ 6 ]フォワードエッジは有向非巡回グラフを形成し、バックエッジは常に制御フローが既に通過した基本ブロックにつながります。還元可能なCFGは一般的に静的特性が強く、分析や最適化が容易です。たとえば、多くのループ最適化は、還元可能なCFGでのみ動作するように設計されています。
構造化プログラミング言語は、生成されるすべてのCFGが還元可能であるように設計されていることが多く、IF、FOR、WHILE、BREAK、CONTINUEなどの一般的な構造化プログラミング文は、確実に還元可能なグラフを生成します。還元不可能なグラフを直接生成するには、プログラム内の任意の場所にジャンプできるGOTOなどの文が必要ですが、 GOTOのすべての使用が還元不可能なCFGを生成するわけではありません。還元不可能なCFGは、ジャンプスレッドなどのコンパイラ最適化によっても生成されることがあります。還元不可能なCFGは還元可能なCFGに変換できますが、そのためには多くの場合、コードの重複やプログラムへの新しい変数の導入が必要になります。
文脈自由文法（CFG）のループ連結性は、そのCFGの深さ優先探索木（DFST）に基づいて定義されます。このDFSTは開始ノードを根とし、CFGのすべてのノードを網羅する必要があります。
この文脈では、CFGにおいて、あるノードからそのDFST祖先（自身を含む）のいずれかに延びるエッジは、バックエッジと呼ばれます。ただし、DFST祖先がエッジの始点ノードを支配する必要はないため、これは必ずしも通常のバックエッジの定義と一致するとは限りません。
ループ連結度は、CFG のサイクルフリーパスで見つかるバックエッジの最大数です。還元可能な CFG では、ループ連結度は選択された DFST に依存しません。[ 7 ] [ 8 ]
ループ接続性は、データフロー解析の時間計算量について推論するために使用されてきた。[ 7 ]
制御フローグラフは単一のプロシージャの制御フローを表すのに対し、プロシージャ間制御フローグラフはプログラム全体の制御フローを表す。[ 9 ]
ドラゴンブックに書誌情報が記載されている。[ 1 ]
ブック