Was ist ein Dominator-Knoten und ein Dominator-Baum?

Question

Ich habe versucht, die Wikipedia über Dominator (Graph Theory) Die folgende Definition eines Dominator-Knotens:

A-Knoten d dominiert einen Knoten n, wenn jeder Pfad vom Eingabeknoten auf n Muss durchlaufen d.

Ich muss das Konzept eines Dominator-Knotens verstehen, aber ich muss nicht tief in Grafiken gehen, also versuche ich, diese Definitionen zu spüren. Ich versuche, in den Bildern des Artikels zu schauen:

Dies ist ein Diagramm:

Dies sollte ein Dominator-Baum für das obige Diagramm sein:

Basierend auf der oben genannten Definition, denke ich

Node 2 dominiert Knoten 3, da jeder Pfad von 3 durchlaufen muss 2. Warum? Um von 3 an sich selbst zu gehen, muss ich an 2 weitergeben. Deshalb geht 2 in den Dominatorbaum auf 3.

Ich denke an das Recht?

kann ich auch wissen, warum dies in den Compilern nützlich ist?

Answer 1

der Grund, warum Sie geben, ist nicht genau richtig; Die Definition eines Dominator-Knotens arbeitet von einem Startknoten ( $ 1 $ im Beispiel). Der einzige Weg, um $ 3 $ von $ 1 $ $ durch $ 2 $ Da ist der einzige Nachfolgerknoten von $ 1 $ in der angegebenen Grafik. Daher $ 2 $ dominiert $ 3 $ . Aus demselben Grund werden die Knoten $ 4 $ über $ 6 $ auch von $ 2 $ und weiter, $ 2 $ ist der sofortige -Dominator dieser Knoten (als $ 1 $ dominiert $ 2 $ ) und diese Knoten werden auch nicht von anderen Knoten dominiert als $ 1 $ und $ 2 $ :

.
• $ 3, 4 $ und $ 6 $ kann von $ 1 $ über $ 2 $ .
• $ 5 $ kann von $ 2 $ entweder über $ 3 $ oder $ 4 $ und somit die einzigen gängigen Knoten in diesen Pfaden zu $ 5 $ sind $ 1 $ und $ 2 $ .

Wenn Sie diese Konzepte an Compiler anwenden, berücksichtigen Sie ein Block-Level-Steuerungsflußdiagramm (oder CFG für Kürze) eines Programms. Wenn einige Blocks $ B $ einen Block $ B '$ in der CFG dominiert, dann $ B $ muss mit der Zeit ausgeführt worden sein, zu der das Programm $ B '$ erreicht. Dieses Wissen kann verwendet werden, um redundante Code-Teile zu entfernen: Betrachten Sie das Programm

generasacodicetagpre.

Hier dominiert der Block, der aus den ersten beiden Zeilen besteht, den IF-BLOCK sowie den anderen Block. Daher wissen wir, dass, wenn wir zum IF-BLOCK, an dem b auf True springen würden, von dem Faustblock auf b eingestellt werden, und somit der Compiler den Code optimieren kann, indem er die Zuordnung in dem IF-BLOCK löscht.

Sie können auch Schleifen in dem Code erkennen, indem Sie analysieren, wenn die CFG Kanten des Formulars $ B '\ bis B $ aufweist, wo wieder $ B $ dominiert $ B '$ . Ein solcher Pfad zeigt die Existenz einer Schleife an, in der $ B $ dann den Schleifenkopf darstellen würde, während $ B '$ ist (der letzte) Teil des Schleifenkörpers.