コントロール依存

制御依存性とは、前の命令が実行を許可する方法で評価された場合に、プログラム命令が実行される状況です。

命令 B は、先行する命令 A の結果によって B の実行の有無が決定される場合、命令 A に対して制御依存関係を持ちます。次の例では、命令は命令に対して制御依存関係を持ちます。ただし、はの結果に関わらず常に実行されるため、はに依存しません。 $S_{2}$ $S_{1}$ $S_{3}$ $S_{1}$ $S_{3}$ $S_{1}$

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

直感的に、2つの文AとBの間に制御依存関係があるのは、

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

典型的な例としては、if ステートメントの条件部分と、その true/false 本体のステートメントの間に制御依存関係があることが挙げられます。

制御依存性の正式な定義は次のように表すことができます。

ある文が別の文に制御依存していると言われるのは、 $S_{2}$ $S_{1}$

からへのパスが存在し、その中のすべての文≠は、プログラムの終わりまでの各可能なパスでに続く。 $P$ $S_{1}$ $S_{2}$ $S_{i}$ $S_{1}$ $P$ $S_{2}$
$S_{1}$ は必ずしもが続くわけではありません。つまり、からプログラムの最後までを経由しない実行パスが存在します。 $S_{2}$ $S_{1}$ $S_{2}$

（後）優位性を用いて表現すると、2つの条件は次のようになる。

$S_{2}$ ポストはすべてを支配する $S_{i}$
$S_{2}$ ポスト支配しない $S_{1}$

制御依存関係の構築

制御依存関係は、本質的には制御フローグラフ（CFG）の逆グラフにおける支配フロンティアです。^[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 内のノードから、それらに制御依存関係を持つノードへのマップが得られます。

参照

参考文献

^ Cytron, R.; Ferrante, J.; Rosen, BK; Wegman, MN; Zadeck, FK (1989-01-01). 「静的単一代入形式の効率的な計算方法」. Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 . New York, NY, USA: ACM. pp. 25– 35. doi :10.1145/75277.75280. ISBN 0897912942. S2CID 8301431。

[1] Cytron, R.; Ferrante, J.; Rosen, BK; Wegman, MN; Zadeck, FK (1989-01-01). 「静的単一代入形式の効率的な計算方法」. Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 . New York, NY, USA: ACM. pp. 25– 35. doi :10.1145/75277.75280. ISBN 0897912942. S2CID 8301431。