Contents

Control dependency

Control dependency(制御依存)とは

Post-dominator

Post-dominance frontier

定義
ノードxのPost-dominance frontierは，以下を満たすノードyの集合である:
  • xはyの次ノードのpost-dominatorである
  • xはyのpost-dominatorでない
直感的理解
ノードyはノードxのPost-dominance frontierである
⇔ yがxを実行するかどうかを決定する
  • yの次ノードは，必ずxを通る
  • yは，必ずxを通るわけではない
具体例
意味
ノードxのPost-dominance frontier
⇔ ノードxが制御依存するノードの集合

Data dependency

アルゴリズム

Given: CFG, Points-to関係
  1. CFGから，Def-Useに関わる命令のみで構成されたサブグラフを作成
    • e.g., store, load, call, return, malloc
  2. サブグラフ上でReaching definitions解析
    1. 各ノード毎に以下の集合を用意
      • Def-set: そのノードで定義される変数の集合
      • Kill-set: そのノードで上書きされる変数の集合
        • もし命令がどの変数を更新するか一つに特定できない場合(Weak-update)，Kill-set = φ
    2. EntryノードからTransfer functionを適用
    3. Fix-pointに到達するまで繰り返す
  3. Def-Useを結ぶ
    • 変数を使用する命令 ← 到達した変数の定義命令