支配ノードと支配ツリーとは何ですか？

Question

私は、これが与えるDominatorノードの次の定義：

エントリノードからnへのパスごとにノードDを支配する dを通過する必要があります。

支配ノードの概念を理解する必要がありますが、グラフに深くなる必要はありませんので、これらの定義を理解しようとしています。記事の画像を見ようとしています。

これはグラフです：

これは上記のグラフの支配ツリーであるべきです：

href="https://i.stack.imgur.com/fkvnz.png" rel="nofollownoreferrer">

上記の定義に基づいて、

だと思います

ノード2は、3からのすべてのパスが通過しなければならないため、ノード3を支配します。 3から自分自身へ行くには、2に渡さなければなりません。

私は正しいことを考えていますか？

これがコンパイラで役立つ理由も知っていますか？

Answer 1

あなたが与える理由は正確には正しくありません。ドミネータノードの定義は、例では、開始ノード（ $ 1 $ >から機能します）。 $ 1 $ からに到達する唯一の方法は $ 1 $ の唯一の後継ノードです。したがって、 $ 2 $ は $ 3 $ を支配します。同じ理由で、ノード $ 4 $ $ 6 $ も $ 2 $ 、さらに、 $ 2 $ は、これらのノードの即時ドミネータです（ $ 1 $ $ 2 $ ）およびこれらのノードも $ 1 $ と $ 2 $ ：

• $ 3,4 $ と $ 6 $ は $ 2 $ 。
• $ 5 $ から $ 2 $ から到達することができます。 > $ 3 $ または $ 4 $ 、したがって $ 5 $ への唯一の一般的なノード $ 1 $ と $ 2 $ 。

これらの概念をコンパイラに適用する場合は、プログラムのブロックレベルの制御フローグラフ（または簡潔さのためのCFG）を考えてみましょう。 いくつかのブロック $ b $ が、cfg内のblock $ b '$ を支配してから $ B $ は、プログラムが $ b '$ に到達する時までに実行されていなければなりません。 この知識は、冗長なコードを削除するために使用できます。 プログラム

を検討してください

a = (something)
b = True

if a == True:
   b = True
else:
   b = False
   

.

ここで、最初の2つの線からなるブロックは、else-blockと同様にIFブロックを支配します。 したがって、BをTRUEに設定するIFブロックにジャンプする時点では、FISTブロックによってすでにTRUEに設定されているので、コンパイラはIFブロック内の割り当てを削除することによってコードを最適化することができます。

CFGが $ B '$ B' $ のエッジを持っているかどうかを分析することによって、コード内のループを検出することもできます。 -container "> $ b $ は、 $ b '$ を支配します。そのようなパスは、 $ b $ がループヘッダーを表すループの存在を示します。 $ b '$ ループ本体の（最後の）部分。