Dominador (teoría de grafos)

En informática , un nodo d de un grafo de flujo de control domina a un nodo n si todo camino desde el nodo de entrada hasta n debe pasar por d . Notacionalmente, esto se escribe como d dom n (o a veces d ≫ n ). Por definición, cada nodo se domina a sí mismo.

Existen varios conceptos relacionados:

• Un nodo d domina estrictamente a un nodo n si d domina a n y d no es igual a n .
• El dominador inmediato o idom de un nodo n es el único nodo que domina estrictamente a n pero no domina estrictamente a ningún otro nodo que domine estrictamente a n . Cada nodo alcanzable desde el nodo de entrada tiene un dominador inmediato (excepto el nodo de entrada). ^{[ 1 ]}
• La frontera de dominancia de un nodo d es el conjunto de todos los nodos n _i tales que d domina a un predecesor inmediato de n _i , pero d no domina estrictamente a n _i . Es el conjunto de nodos donde termina la dominancia de d .
• Un árbol dominador es un árbol donde los hijos de cada nodo son aquellos nodos a los que domina inmediatamente. El nodo inicial es la raíz del árbol.

El concepto de dominancia fue introducido por primera vez por Reese T. Prosser en un artículo de 1959 sobre el análisis de diagramas de flujo. ^{[ 2 ]} Prosser no presentó un algoritmo para calcular la dominancia, lo cual tuvo que esperar diez años hasta que Edward S. Lowry y CW Medlock lo hicieran. ^{[ 3 ]} Ron Cytron et al. reavivaron el interés en la dominancia en 1989 cuando la aplicaron al problema de calcular eficientemente la ubicación de las funciones φ, que se utilizan en forma de asignación única estática . ^{[ 4 ]}

Los dominadores, y en particular las fronteras de dominancia, tienen aplicaciones en compiladores para calcular la forma de asignación única estática . Varias optimizaciones de compiladores también pueden beneficiarse de los dominadores. El grafo de flujo en este caso comprende bloques básicos .

Los dominadores desempeñan un papel crucial en el análisis del flujo de control al identificar los comportamientos del programa que son relevantes para una instrucción u operación específica, lo que ayuda a optimizar y simplificar el flujo de control de los programas para su análisis. ^{[ 5 ]}

La paralelización automática se beneficia de las fronteras de postdominancia. Este es un método eficiente para calcular la dependencia de control, lo cual es fundamental para el análisis.

El análisis del uso de memoria puede beneficiarse del árbol de dominancia para encontrar fácilmente fugas e identificar un alto uso de memoria. ^{[ 6 ]}

En sistemas de hardware, los dominadores se utilizan para calcular probabilidades de señal para la generación de pruebas, estimar actividades de conmutación para el análisis de potencia y ruido, y seleccionar puntos de corte en la verificación de equivalencia. ^{[ 7 ]} En sistemas de software, se utilizan para reducir el tamaño del conjunto de pruebas en técnicas de prueba estructural como la cobertura de sentencias y ramas. ^{[ 8 ]}

Dejar${\displaystyle n_{0}}$ser el nodo fuente en el grafo de flujo de control . Los dominadores de un nodo${\displaystyle n}$se obtienen mediante la solución máxima de las siguientes ecuaciones de flujo de datos:

${\displaystyle \operatorname {Dom} (n)={\begin{cases}\left\{n\right\}&{\mbox{ si }}n=n_{0}\\\left\{n\right\}\cup \left(\bigcap _{p\in {\text{preds}}(n)}^{}\operatorname {Dom} (p)\right)&{\mbox{ si }}n\neq n_{0}\end{cases}}}$

El dominador del nodo inicial es el propio nodo inicial. El conjunto de dominadores para cualquier otro nodo${\displaystyle n}$es la intersección del conjunto de dominadores para todos los predecesores${\displaystyle p}$de${\displaystyle n}$. El nodo${\displaystyle n}$también está en el conjunto de dominadores para${\displaystyle n}$.

Un algoritmo para la solución directa es:

// El dominador del nodo de inicio es el propio inicio. Dom(n 0 ) = {n 0 } // Para todos los demás nodos, establezca todos los nodos como dominadores. para cada n en N - {n 0 } Dom(n) = N; // Eliminar iterativamente los nodos que no son dominadores mientras haya cambios en cualquier Dom(n) para cada n en N - {n 0 }: Dom(n) = {n} unión con intersección sobre Dom(p) para todo p en pred(n)

La solución directa es cuadrática en el número de nodos, o O( n² ). Lengauer y Tarjan desarrollaron un algoritmo que es casi lineal, ^{[ 1 ] y en la} práctica, salvo para algunos grafos artificiales, el algoritmo y una versión simplificada del mismo son tan rápidos o más rápidos que cualquier otro algoritmo conocido para grafos de todos los tamaños, y su ventaja aumenta con el tamaño del grafo. ^{[ 9 ]}

Keith D. Cooper , Timothy J. Harvey y Ken Kennedy de la Universidad Rice describen un algoritmo que esencialmente resuelve las ecuaciones de flujo de datos anteriores, pero utiliza estructuras de datos bien diseñadas para mejorar el rendimiento. ^{[ 10 ]}

De forma análoga a la definición de dominancia anterior, se dice que un nodo z postdomina a un nodo n si todos los caminos hacia el nodo de salida del grafo que parten de n deben pasar por z . Del mismo modo, el postdominador inmediato de un nodo n es el postdominador de n que no postdomina estrictamente a ningún otro postdominador estricto de n .

• Gráfico de flujo de control
• Intervalo (teoría de grafos)
• Formulario de asignación única estática

• Biblioteca de análisis de flujo de control Machine-SUIF
• Algoritmos para calcular dominadores explicados visualmente