Gráfico acíclico dirigido en Compiler Design (con ejemplos)

Gráfico acíclico dirigido:
el gráfico acíclico dirigido (DAG) se utiliza para representar la estructura de bloques básicos , para visualizar el flujo de valores entre bloques básicos y para proporcionar técnicas de optimización en el bloque básico. Para aplicar una técnica de optimización a un bloque básico, un DAG es un código de tres direcciones que se genera como resultado de una generación de código intermedio.

• Los gráficos acíclicos dirigidos son un tipo de estructura de datos y se utilizan para aplicar transformaciones a bloques básicos.
• El gráfico acíclico dirigido (DAG) facilita la transformación de bloques básicos.
• DAG es un método eficiente para identificar subexpresiones comunes.
• Demuestra cómo se utiliza el valor calculado de la declaración en declaraciones posteriores.

Ejemplos de gráfico acíclico dirigido:

Características del gráfico acíclico dirigido:
un gráfico acíclico dirigido para bloque básico es un gráfico acíclico dirigido con las siguientes etiquetas en los Nodes.

• Cada una de las hojas del gráfico tiene un identificador único, que puede ser nombres de variables o constantes.
• Los Nodes interiores del gráfico están etiquetados con un símbolo de operador.
• Además, los Nodes reciben una string de identificadores para usar como etiquetas para almacenar el valor calculado.
• Los gráficos acíclicos dirigidos tienen sus propias definiciones de cierre transitivo y reducción transitiva.
• Los gráficos acíclicos dirigidos tienen órdenes topológicos definidos.

Algoritmo para la construcción de gráficos acíclicos dirigidos:
hay tres escenarios posibles para construir un DAG en tres códigos de dirección:

Caso 1 –  x = y op z
Caso 2 – x = op y
Caso 3 –  x = y

El gráfico acíclico dirigido para los casos anteriores se puede construir de la siguiente manera:

Paso 1 –

• Si el operando y no está definido, cree un Node (y).
• Si el operando z no está definido, cree un Node para el caso (1) como Node (z).

Paso 2 –

• Cree el Node (OP) para el caso (1), con el Node (z) como su hijo derecho y el Node (OP) como su hijo izquierdo (y).
• Para el caso (2), vea si hay un operador de Node (OP) con un Node hijo (y).
• El Node n será el Node (y) en el caso (3).

Paso 3:
elimine x de la lista de identificadores de Node. Paso 2: agregue x a la lista de identificadores adjuntos para el Node n.

Ejemplo :

T ₀ = a + b —Expresión 1
T ₁ = T ₀ + c —-Expresión 2
d = T ₀ + T ₁         —–Expresión 3

Expresión 1 : T ₀ = a + b

Expresión 2: T ₁ = T ₀ + c

 Expresión 3: d = T ₀ + T ₁    

Ejemplo :

T ₁ = un +       segundo
T ₂ = T1 + c     
T ₃ = T1 x T2    

Ejemplo :

T ₁ = un + segundo
T ₂ = un – segundo
T ₃ = T ₁ * T ₂
T ₄ = T ₁ – T ₃
T ₅ = T ₄ + T ₃

Ejemplo :

una = bxc
re =
segundo mi = dxc segundo = mi
f = segundo
+ c
gramo = f + re

Ejemplo :

 T ₁ := 4*I ₀

T ₂ := un[T ₁ ]

T ₃ := 4*I ₀

T ₄ := b[T ₃ ]

T ₅ := T ₂ * T ₄

T ₆ := prod + T ₅

producción:= T ₆

T ₇ := yo ₀ + 1

yo ₀ := T ₇

si yo ₀ <= 20 pasa a 1

Aplicación del gráfico acíclico dirigido:

• El gráfico acíclico dirigido determina las subexpresiones que se usan comúnmente.
• El gráfico acíclico dirigido determina los nombres utilizados dentro del bloque, así como los nombres calculados fuera del bloque.
• Determina qué declaraciones en el bloque pueden tener su valor calculado fuera del bloque.
• El código se puede representar mediante un gráfico acíclico dirigido que describe las entradas y salidas de cada una de las operaciones aritméticas realizadas dentro del código; esta representación permite que el compilador realice la eliminación de subexpresiones comunes de manera eficiente.
• Varios lenguajes de programación describen sistemas de valores que están vinculados entre sí por un gráfico acíclico dirigido. Cuando cambia un valor, se recalculan sus sucesores; cada valor en el DAG se evalúa como una función de sus predecesores.