12.85 util.dominator - 支配木 ¶

Module: util.dominator ¶

支配木(dominator tree)は制御フローグラフで補助的に使われる構造です。 コンパイラのフロー解析によく使われることが多いですが、一般の有向グラフでも有用です。

Function: calculate-dominators start upstreams downstreams node-comparator ¶

{util.dominator} 4つの引数で有向グラフが表現されます。循環があっても構いません。 以下ではグラフのノードがNodeという型を持つとして説明します。 実際にはノードの型は何であっても構いません。 アルゴリズムはノードの実際の型とは無関係に動作します。

start :: Node

フローの起点となるノード。startノードとかenterノードとも呼ばれます。

upstreams :: Node -> (Node …)

ノードを取り、その直接の上流ノードのリストを返す関数。

downstreams :: Node -> (Node …)

ノードを取り、その直接の下流ノードのリストを返す関数。

node-comparator

二つのノードが等しいかどうかを決定する比較器。大小比較関数を持っている必要はありませんが、 アルゴリズム内部でハッシュテーブルを使うので、ハッシュ関数は持っている必要があります。 比較器について詳しくは基本的な比較器を参照してください。

返り値は(node1 node2)を要素に持つリストです。ここで、 node2はnode1の直接支配ノード(immediate dominator)です。

与えられたグラフの中にstartから到達不可能なノードがあった場合、 それは単に無視され、結果に含まれません。

(ちょっとした説明: startからノードXに行きたいとします。 複数の経路がありえますが、どの経路を取っても必ずノードYを通らないと Xに行けない場合、YをXの支配ノード(dominator)と呼びます。 支配ノードは複数ありえますが、その中で一つだけ、他のXの支配ノード全てが そのノードの支配ノードでもあるようなノードがあります(言い換えれば、 Xに一番「近い」支配ノードです)。それをXの直接支配ノードと呼びます。)

例を見てみましょう。こんな有向グラフがあるとします。

          A (start)
          |
          v
          B <-------+
          |         |
    ------+-----    |
    |          |    |
    v          v    |
    C -------> D ---+
    |          |
    v          v
    E <------- F

このグラフをリストのリストで表現してみましょう。 ここで、内側のリスト(x y z ...)は、xからはyやzに 直接行ける、ということを表します。

(define *graph* '((A B)
                  (B C D)
                  (C D E)
                  (D F B)
                  (F E)))

すると、各ノードの直接支配ノードが次の通り計算できます。

(calculate-dominators 'A
  (^n (filter-map (^g (and (memq n (cdr g)) (car g))) *graph*))
  (^n (assoc-ref *graph* n '()))
  eq-comparator)
  ⇒ ((E B) (F D) (D B) (C B) (B A))

つまり、Eの直接支配ノードはBであり、 FのはDである、という具合です。

この結果自体を木と解釈することができます。これを支配木(dominator tree)と呼びます。

              F
              |
              v
        E     D     C
        |     |     |
        |     v     |
        +---> B <---+
              |
              v
              A