¿Qué es un nodo dominador y un árbol dominador?

Question

Intenté leer la Wikipedia sobre Dominator (teoría del gráfico) , que da La siguiente definición de un nodo de dominador:

Un nodo D domina un nodo n si cada ruta del nodo de entrada a n debe pasar por d.

Necesito entender el concepto de un nodo dominador, pero no necesito profundizar en gráficos, así que estoy tratando de darle sentido a estas definiciones. Estoy tratando de mirar en las imágenes en el artículo:

Este es un gráfico:

Este debe ser un árbol dominador para el gráfico anterior:

Basado en la definición anterior, creo

El nodo 2 domina el nodo 3 porque cada ruta de 3 debe pasar por 2. ¿Por qué? Para pasar de 3 a sí mismo, debo pasar a 2. Es por eso que 2 va a 3 en el árbol Dominador.

¿Estoy pensando bien?

¿Puedo saber también por qué esto es útil en los compiladores?

Answer 1

La razón por la que usted da no es exactamente correcto; La definición de un nodo dominador funciona desde un nodo de inicio ( $ 1 $ en el ejemplo). La única forma de llegar a $ 3 $ de $ 1 $ es ir a través de $ 2 $ , ya que es el único nodo sucesor de $ 1 $ en el gráfico dado. Por lo tanto, $ 2 $ domina $ 3 $ . Por la misma razón, los nodos $ 4 $ a través de $ 6 $ también están dominados por $ 2 $ y más, $ 2 $ es el inmediato Dominador de estos nodos (como $ 1 $ domina $ 2 $ ) y estos nodos tampoco están dominados por ningún otro nodificador que $ 1 $ y $ 2 $ :

• $ 3, 4 $ y $ 6 $ se puede llegar de inmediato desde $ 1 $ a través de $ 2 $ .
• $ 5 $ se puede llegar desde $ 2 $ ya sea a través de $ 3 $ o $ 4 $ y, por lo tanto, los únicos nodos comunes en estas rutas a $ 5 $ son $ 1 $ y $ 2 $ .

En cuanto a la aplicación de estos conceptos a los compiladores, considere un gráfico de flujo de control de nivel de bloque (o CFG para la brevedad) de un programa. Si algunos bloques $ b $ dominan un bloque $ b '$ en el CFG, luego $ b $ debe haber sido ejecutado cuando el programa llega a $ b '$ . Este conocimiento se puede utilizar para eliminar piezas redundantes de código: Considerar el programa

a = (something)
b = True

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

Aquí, el bloque que consiste en las dos primeras líneas domina el bloqueo if directamente como el bloqueo. Por lo tanto, sabemos que, cuando saltamos a la Bloque IF, donde estableceríamos B en VERDADERO, ya está establecido en el bloqueo del puño y, por lo tanto, el compilador podría optimizar el código al eliminar la asignación en el bloqueo if-Block.

También puede detectar bucles en el código al analizar si el CFG tiene bordes del formulario $ b '\ a b $ donde otra vez $ b $ domina $ b '$ . Dicha ruta indica la existencia de un bucle donde $ b $ representaría el encabezado de bucle mientras $ b '$ es (la última) parte del cuerpo de bucle.