制御依存

制御依存性とは、プログラムの命令が、前の命令が実行可能な形で評価された場合にのみ実行される状況のことである。

命令 B は、命令 A の結果によって B を実行するかどうかが決まる場合、先行する命令 A に対して制御依存している。次の例では、命令${\displaystyle S_{2}}$命令に対する制御依存性がある${\displaystyle S_{1}}$。 しかし、${\displaystyle S_{3}}$依存しない${\displaystyle S_{1}}$なぜなら${\displaystyle S_{3}}$結果に関係なく常に実行されます${\displaystyle S_{1}}$。

S1. (a == b) の場合 S2. a = a + b S3. b = a + b

直感的に、2 つのステートメント A と B の間には、次のような場合に制御依存性があります。

• BはAの後に実行される可能性がある
• Aの実行結果によって、Bが実行されるかどうかが決まる。

典型的な例としては、if文の条件部分と、その真偽判定部分にある文との間に制御依存関係が存在することが挙げられる。

制御依存性の正式な定義は、以下のように示すことができる。

声明${\displaystyle S_{2}}$別のステートメントに制御依存していると言われている${\displaystyle S_{1}}$もし

• 道が存在する${\displaystyle P}$から${\displaystyle S_{1}}$に${\displaystyle S_{2}}$すべてのステートメントが${\displaystyle S_{i}}$≠${\displaystyle S_{1}}$内で${\displaystyle P}$続いて${\displaystyle S_{2}}$プログラムの終了に至るあらゆる経路において、
• ${\displaystyle S_{1}}$必ずしも続くとは限りません${\displaystyle S_{2}}$つまり、実行パスは${\displaystyle S_{1}}$プログラムの最後まで実行されない${\displaystyle S_{2}}$。

（後）優位性を用いて表現すると、2つの条件は以下と同等である。

• ${\displaystyle S_{2}}$ポストが全てを支配する${\displaystyle S_{i}}$
• ${\displaystyle S_{2}}$後優勢ではない${\displaystyle S_{1}}$

制御依存性は、本質的に制御フローグラフ（CFG）の逆グラフにおける支配フロンティアです。^{[ 1 ]}したがって、それらを構築する1つの方法は、CFGの支配後フロンティアを構築し、それを反転させて制御依存グラフを取得することです。

以下は、ポストドミナンスフロンティアを構築するための擬似コードです。

ポストドミネーターツリーのボトムアップ走査における各Xについて、以下を実行する。 ポストドミナンスフロンティア(X) ← ∅ 各Y ∈ Predecessors(X)に対して、以下を実行する: もしimmediatePostDominator(Y) ≠ X ならば、 PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y} を 実行する。各Z ∈ Children(X)に対して、以下を実行する: 各Y ∈ PostDominanceFrontier(Z)に対して、以下を実行する: もしimmediatePostDominator(Y) ≠ X ならば、 PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y} を実行する。

ここで、Children(X) は CFG においてXによって直後に支配されるノードの集合であり、Predecessors(X) はCFG においてXの直前に位置するノードの集合です。ノードXは、そのすべての Children ノードの処理が完了した後にのみ処理されることに注意してください。支配後境界マップが計算されたら、それを反転することで、CFG 内のノードから、それらに制御依存するノードへのマップが得られます。

• 依存性分析
• データ依存性
• ループ依存性分析 § 制御依存性