Estoy tratando de comprender con precisión la noción de un gráfico de dependencia de control. Supongamos que tengo el siguiente gráfico de flujo de control (en notación DOT):¿Puede un gráfico de dependencia de control tener bucles?
graph g {
1 -> 2;
2 -> 3;
3 -> 2;
2 -> 4;
1 -> 4
}
Tiene un nodo único de entrada (1) y un nodo único de salida (4), y un bucle de 2 -> 3 -> 2.
Mi pregunta es: ¿el gráfico de dependencia de control para este CFG contiene un borde de bucle de 2 a sí mismo?
Allen & "Compiladores de optimización para arquitecturas modernas" de Kennedy tiene un algoritmo que produce un borde de bucle. Sin embargo, el algoritmo de Muchnick "Compilación de diseño &" para la dependencia del control no produce dicha ventaja. Además, no pude encontrar ningún ejemplo en la literatura donde se dibuje un CDG con un borde de bucle. Tiendo a creer que no hay tal ventaja, pero de acuerdo con la definición formal de dependencia de control y según el algoritmo de Kennedy &, ¡debería!
Si puede indicarme un ejemplo donde hay un bucle en un CDG (preferiblemente en un artículo revisado por pares, o notas de conferencias de algún profesor, etc.), o si puede argumentar por qué Allen & algoritmo de Kennedy debería ser incorrecto, me alegraría saberlo.
La utilidad de tal gráfico de dependencia es determinar cómo ordenar las operaciones, ¿no? En ese sentido, no es útil saber que un elemento depende de sí mismo. Puede dibujar los bucles si lo desea, pero lo que es realmente importante son todos los otros bordes. – mitchus
Sí, creo que esperaba una "definición canónica" que podría usarse como oráculo para probar múltiples implementaciones, pero es verdad que ambas versiones son equivalentes para todos los propósitos prácticos ... ¡gracias! – anol
@mitchus Debe mover su comentario a una respuesta para que pueda aceptarse como la respuesta. –