Qu'est-ce qu'un nœud dominateur et un arbre dominateur?

Question

J'ai essayé de lire la Wikipedia sur Dominator (graphique théorie) , qui donne La définition suivante d'un nœud dominateur:

Un noeud D domine un nœud N si chaque chemin du nœud d'entrée à n doit passer par d.

J'ai besoin de comprendre le concept d'un nœud dominateur, mais je n'ai pas besoin d'aller au fond des graphiques, alors j'essaie de donner un sens à ces définitions. J'essaie de regarder dans les images de l'article:

Ceci est un graphique:

Ceci devrait être un arbre dominateur pour le graphique ci-dessus:

basé sur la définition ci-dessus, je pense

Le nœud 2 domine le nœud 3 car chaque chemin de 3 doit passer à travers 2. Pourquoi? Pourquoi? Pour aller de 3 à lui-même, je dois passer à 2. C'est pourquoi 2 va à 3 dans l'arbre dominateur.

Est-ce que je pense bien?

Puis-je savoir aussi pourquoi cela est utile dans les compilateurs?

Answer 1

La raison pour laquelle vous donnez n'est pas parfaitement correcte; La définition d'un nœud de dominateur fonctionne à partir d'un nœud de départ ( 1 $ $ dans l'exemple). Le seul moyen d'atteindre $ 3 $ de $ 1 $ est de passer par $ 2 $ $ Comme il s'agit du nœud Sole successeur de $ 1 $ dans le graphique donné. Par conséquent 2 $ domine $ 3 $ . Pour la même raison, les nœuds $ 4 $ via $ 6 $ sont également dominés par $ 2 $ et plus loin, $ 2 $ est le immédiat dominateur de ces nœuds (comme $ 1 $ domine $ 2 $ ) et ces nœuds ne sont également pas dominés par aucun autre noeud que $ 1 $ et $ 2 $ :

• 3 $, 4 $ et $ 6 $ peut être immédiatement atteint de $ 1 $ via $ 2 $ .
• 5 $ peut être atteint à partir de $ 2 $ via $ 3 $ ou 4 $ et donc les seuls nœuds courants de ces chemins à $ 5 $ sont 1 $ $ et $ 2 $ .

En ce qui concerne l'application de ces concepts aux compilateurs, envisagez un graphe de contrôle de contrôle de bloc (ou la BFG pour la brièveté) d'un programme. Si certains bloquent $ B $ domine un bloc $ B '$ dans le CFG, puis $ B $ doit avoir été exécuté au moment où le programme atteint $ B '$ . Ces connaissances peuvent être utilisées pour supprimer des morceaux de code redondants: Considérez le programme

a = (something)
b = True

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

Ici, le bloc constitué des deux premières lignes domine le bloc IF ainsi que le bloc d'éléments. Par conséquent, nous savons qu'au moment où nous allons passer au bloc IF où nous serions définis par true, il est déjà défini sur TRUE par le bloc Fist et que le compilateur pourrait ainsi optimiser le code en supprimant l'affectation dans le bloc IF.

Vous pouvez également détecter des boucles dans le code en analysant si le CFG a des bords de la forme $ b '\ to b $ d'où $ B $ domine $ B '$ . Un tel chemin indique l'existence d'une boucle où $ B $ représenterait alors l'en-tête de boucle pendant $ B '$ est (la dernière) partie du corps de la boucle.